Hacker News Reader

Comment by kutkloon7 | Hacker News Reader

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

View on HN

How do you implement swap if deck is too large to hold in memory?

mmap the deck

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:

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

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)

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

I think you aren't allowed to mutate the deck.

Reply on news.ycombinator.com