News for hackers. Stuff that matters.
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):

  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).
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:

https://en.wikipedia.org/wiki/Reservoir_sampling )

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...

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by IshKebab on Monday April 04, 2016 @03:50AM (#11420102)
I think you aren't allowed to mutate the deck.