37 ms·
This 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 -
by kutkloon7 11y ago
This 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 array, and the arrays are 0-indexed).
- codehotter 11y agoHow do you implement swap if deck is too large to hold in memory?
- philsnow 11y agommap the deck
- Vitaly 11y agoYour solution requires space to hold all items from the pool
- acqq 11y agoI 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: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling )
- acqq 11y agoHowever note that in the Vitter's paper all discussed algorithms are O(k) as per previous notation, or O(n) using paper's notation where n elements are selected from the set of N: http://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf http://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf In short, it's worth reading Vitter's paper, the original post is just a post containing the C code, but the discussion of the algorithm and the comparison with the alternatives is in the paper. (Edit: corrected the notation of O() as robrenaud suggested)
- robrenaud 11y agoNot o (little oh), but rather O (big oh). There is a difference between them. Little oh roughly means "grows strictly slower than, in the limit", where as big oh roughly means "grows no faster than, in the limit". http://stackoverflow.com/questions/1364444/difference-between-big-o-and-little-o-notation http://stackoverflow.com/questions/1364444/difference-betwee...
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- IshKebab 11y agoI think you aren't allowed to mutate the deck.