Vitter's reservoir sampling algorithm D: randomly selecting unique items

Post by vrfcodf » Mon, Apr 04, 2016, 8:07 AM UTC

throwaway_yy2Di wrote: post #37

vrfcodf wrote: post #22

Here 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…

This works, and is so much simpler. It's not quite the same problem though; the algorithm described returns samples in sequential order . They mention performance reasons for this (C-f "tape sampling"). It also has the limitation that you need to know the sample size in advance.

Post by asldaslkksdj » Mon, Apr 04, 2016, 8:14 AM UTC

ridiculous_fish wrote: post #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…

Post by yelnatz » Mon, Apr 04, 2016, 8:16 AM UTC

forrestthewoods wrote: post #36

I can't believe this article doesn't explain how it works. Especially after stating "after reaching Vitter’s papers it again takes a concentrated effort to figure out what you need".

Post by ridiculous_fish » Mon, Apr 04, 2016, 8:22 AM UTC

vrfcodf wrote: post #22

Here 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…

Post by kutkloon7 » Mon, Apr 04, 2016, 8:31 AM UTC

  void increasingRandomSequence(arrayptr, base, k, n)
  {
      if (k == 0) return;
      int i = randInt(n - k);
      *(arrayptr) = base + i;
      increasingRandomSequence(arrayptr + 1, base + i + 1, k - 1, n - (i + 1));
  }