algorithm question: does anyone have a good link to a weighted random sampling algorithm (choose k items without replacement using weights) that _isn't_ WRS (2005; Efraimidis, Spirakis) ?
Could you do the alias method and maintain a set of previously-sampled items so that you can reject those choices and retry? Degrades to O(n) as the set approaches size n but I assume if you were expecting to get there you’d just shuffle.
-
-
Yeah I had previously implemented it this way but as I was documenting the caveats I realized I was unhappy with it.
-
One nice thing about WRS is that if you sample for the size of the input data, you get a weighted shuffle implementation in O(n log n) time, which is pretty great. (I think the retry option is much worse than O(n) in that case.)
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.