61–70 of 83 posts
Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?
It's not O(k) then. As he mentioned, he's writing this as a language feature, so he can't make simplifying assumptions about k or n. It must handle large n, and can't assume k << n.
IMO the Wikipedia article on this is better than this article: https://en.wikipedia.org/wiki/Reservoir_sampling
Earlier quoted context omitted.
This is not correct as written: "But we have k < N, so if we are O(N) we are also O(k) or better."
That's right. We can fix it up though. The E(t_i) we care about are bounded above by a constant (2), so the sum of k such expectations is linear in k. For the cases where k > n/2, the "full table scan" portion is of course also linear in k.
We only need to consider values in the range 0 N/2, we "pick the losers instead of winners" and that reduces k to that range.
The expected time E to pick k out of N, is N times the last k terms of H(N):
E(k) = N * (H(N) - H(N-k))
E(k) ~ N * (γ + ln(N) - γ - ln(N-k))
= N * (ln(N) - ln(N-k))
dE/dk ~ N/(N - k)
dE/dk E(k) 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 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…
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 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…
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…
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;}
It looks like it was copy-pasted from a pdf. Maybe it was.
Earlier quoted context omitted.
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 )
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)
> 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…
There are several steps where your method could (will) fail. Since you don't introduce any machinery for the hand, you imply an O(k^2) checking algorithm. You also imply an unsorted hand. If you generate the hand in random order, then you fall to an O(k*lg(k)) sort. "Sorted" is an implicit requirement that we initially omit, but revisit later, because introducing it early makes the discussion harder to follow.
If you try to introduce machinery like a hashtable, the next thing you might suggest, you violate an implicit O(1) additional space requirement, which I've grudgingly reintroduced to the more-formal description ("why is this here?"). This conversation keeps going, but other failure paths we leave unexamined.
Earlier quoted context omitted.
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…
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...
Earlier quoted context omitted.
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…
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...