Based on your list size, try a reasonably designed hash function here.
Vitter's reservoir sampling algorithm D: randomly selecting unique items
21–30 of 83 posts
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#22Here is an alternative:
Use a multiplicative linear congruential generator with a period 2^n , where n is ceil(log2(m)), where m is the size of the list.
Seed the generator, start generating values and drop all values that are larger than m. In the worst case you will have to drop half of the values, in the best case you will drop none. This depends on how close to a power of 2 m is.
The generator is very short, one line of code, and very fast: one multiplication, one addition, and one bitshift. Space complexity is O(1).
If your tweets are generated out from an integer value, then you can use this value to generate them. The tweets will be unique (assuming the tweet generator will generate unique tweets from unique values), and you will have m of them.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#23>>> random.sample(xrange(0, 1000000000), 5) [5258132, 23096612, 43529214, 91062733, 4912658] This ran in a few milliseconds on my old macbook in python. It is an iterator over 1 billion element list. Looking at the source, they seem to track previous selections for large populations in a set, for which lookup of "x in y" is avg O(1). https://svn.python.org/projects/python/tags/r32/Lib/random.p...
Actually, due to seeding, no matter how many times you run this you will never generate all combinations of tweet orders. Of course that doesn't really matter since for large values of N there isn't enough time in the universe to do so.
[deleted]
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#24This may be a stupid question, but what exactly is wrong with (using the dealing random cards analogy): for i = 1 to k pickedCardIndex = randomInt(n - i) hand[i - 1] = deck[pickedCardIndex] swap(deck[pickedCardIndex], deck[n - i]) As far as I can see this satisfies all conditions stated by the author (assuming that randomInt(x) produces a uniformly random integer in the range [0, x], there are n cards in the deck arr…
How do you implement swap if deck is too large to hold in memory?
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#25This may be a stupid question, but why not store cards/tweets in a hashmap and add a .contains() check before adding?
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#26This may be a stupid question, but what exactly is wrong with (using the dealing random cards analogy): for i = 1 to k pickedCardIndex = randomInt(n - i) hand[i - 1] = deck[pickedCardIndex] swap(deck[pickedCardIndex], deck[n - i]) As far as I can see this satisfies all conditions stated by the author (assuming that randomInt(x) produces a uniformly random integer in the range [0, x], there are n cards in the deck arr…
Your solution requires space to hold all items from the pool
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#27> The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. If you draw (with replacement) over and over again, ignoring cards you’ve already picked, you can simulate a deal, but you run into problems. The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem).
I don't think this is true!
First note that if you want to pick 98 values from 100, it is much simpler to instead decide which 2 to skip. Similarly when picking 75 out of 100 - better to just cross out 25. The hardest case is picking half: N/2 out of N, without replacement.
This is the Coupon Collector's problem, except we're stopping at half the coupons. We can use the analysis given in the Wikipedia page [1], except we only take the second half of the series.
This gives an expected time of
N * (H(N) - H(N/2))
In the asymptote this yields:
N * (γ + ln(N) - γ - ln(N/2))
= N * (ln 2)
edit: To complete the analysis, the requirement is that the answer be linear in k, the number of items selected. But we have k [1] https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#28Maybe the reason only .X‰ of programmers knows about this algorithm is that only that amount of programmers even need it?
It would be nice to see a page about obscure algorithms that would benefit most programmers instesad of just a small percentile.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#29The C code in this article is a mirror of the code from Appendix 2 in Vitter's paper, which I guess explains/excuses the abbreviated variable names. The paper says things like, "use an exponentially distributed random variate Y," and uses variable names like n, N, U, S, X, y1, and y2 in the appendix. Nonetheless, I find this coding style unreadable. "Y" is not a very good name for an exponentially distributed random…
On the other hand, you need the original names in order to reference back to the paper.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#30This may be a stupid question, but what exactly is wrong with (using the dealing random cards analogy): for i = 1 to k pickedCardIndex = randomInt(n - i) hand[i - 1] = deck[pickedCardIndex] swap(deck[pickedCardIndex], deck[n - i]) As far as I can see this satisfies all conditions stated by the author (assuming that randomInt(x) produces a uniformly random integer in the range [0, x], there are n cards in the deck arr…
Your solution requires space to hold all items from the pool
I believe it would be easy to modify it to have only k chosen indexes in memory, and for k significantly smaller than n and n an order of 2 to 64 it would still be much faster than iterating through all n (which is the first algorithm presented here: