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

Post by mcherm » Mon, Apr 04, 2016, 12:38 PM UTC

vrfcodf wrote: post #65

ridiculous_fish wrote: post #48

Earlier quoted context omitted.

This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations. There are "N choose k" combinations, which in the worst case (k = N/2) grows as ~ 2^N. The number of combinations quickly outstrips the number of possible states of the LCG, and most combinations will never be found. For example, we have a list of length 16 and wish to choose 8. We have a choic…

Good point. You would get different sequences by choosing different constants for the generator though, but you couldn't cover all of them by a longshot.

Post by [deleted] » Mon, Apr 04, 2016, 12:59 PM UTC

Jabbles wrote: post #72

The key to why the obvious algorithm of "half a Fisher-Yates shuffle" isn't enough is that it uses O(k) memory, whereas Vitter's algorithm is constant. http://play.golang.org/p/UqC6XWrPLB

Post by keypusher » Mon, Apr 04, 2016, 2:10 PM UTC

dantiberian wrote: post #10

franciscop wrote: post #5

Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?

I had the same thought. However thinking about it more, the requirement is that this algorithm is O(k). As k gets closer and closer to the size of the list, you will spend more and more time looking for unique items. You also need to pay the costs of checking for uniqueness which also grows with k.

Post by pps43 » Mon, Apr 04, 2016, 4:51 PM UTC

sika_grr wrote: post #62

pmiller2 wrote: post #6

IMO the Wikipedia article on this is better than this article: https://en.wikipedia.org/wiki/Reservoir_sampling

I only see an O(n) algorithm there, there is no O(k). Am I missing something?

Post by retbull » Mon, Apr 04, 2016, 5:37 PM UTC

chipsambos wrote: post #66

dfabulich wrote: post #12

The C code in this article is a mirror of the code from Appendix 2 in Vitter's paper, which I guess explains/excuses the abbreviated variable names. The paper says things like, "use an exponentially distributed random variate Y," and uses variable names like n, N, U, S, X, y1, and y2 in the appendix. Nonetheless, I find this coding style unreadable. "Y" is not a very good name for an exponentially distributed random…

var naming aside, the whitespacing is perplexing: U = random_double(); negSreal=-S; y1=exp(log(U*Nreal/qu1real)*nmin1inv); Vprime = y1 * (-X/Nreal+1.0)*(qu1real/(negSreal+qu1real)); if(Vprime S){bottom=-nreal+Nreal;limit=-S+N;} else{bottom=-1.0+negSreal+Nreal; limit=qu1;} Sometimes two statements per line, sometimes one. Sometimes spaces before and after equals, sometimes none. Sometimes multiple ifs, breaks and stat…