Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by kutkloon7 on Monday April 04, 2016 @03:22AM
(#11419997)
This may be a stupid question, but what exactly is wrong with (using the dealing random cards analogy):
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).
[ Parent
| on HN ]
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by codehotter on Monday April 04, 2016 @03:28AM
(#11420027)
How do you implement swap if deck is too large to hold in memory?
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by philsnow on Monday April 04, 2016 @01:22PM
(#11423627)
mmap the deck
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by Vitaly on Monday April 04, 2016 @03:33AM
(#11420050)
Your solution requires space to hold all items from the pool
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by acqq on Monday April 04, 2016 @03:47AM
(#11420089)
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:
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by acqq on Monday April 04, 2016 @07:19AM
(#11420925)
However 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
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)
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by robrenaud on Monday April 04, 2016 @07:58AM
(#11421151)
Not 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-betwee...