Vitter's reservoir sampling algorithm D: randomly selecting unique items
getkerf.wordpress.com
Vitter's reservoir sampling algorithm D: randomly selecting unique items
1–10 of 83 posts
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#2[deleted]
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#3A much cleaner, GPL-ed implementation is provided here: https://github.com/WebDrake/GrSL/blob/master/sampling/vitter...
(I personally find Kevin's code very hard to follow)
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#4Could someone explain how this works? I feel like unique shuffling given a random seed is very useful algorithm, but I can't follow this code because of the variable naming and stuff.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#5Why cannot you just create random numbers and discard duplicates?
For practical purposes when list.length << total.lenght shouldn't that be good enough?
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#6IMO the Wikipedia article on this is better than this article: https://en.wikipedia.org/wiki/Reservoir_sampling
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#7> Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory.
So if N is really large and doesn't fit into main memory, how does one iterate over such large list in a reasonable amount of time? When I am taught algorithm my sample input is relatively small, from 10,000 elements to 1M integer numbers. Big deal. But I am not sure how to really think when N is really huge and whether we'd ever really have to deal with 10B integers in one pass. In that case, it's more likely I am paging through my database cursor... someone please shine light.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#8> Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory. So if N is really large and doesn't fit into main memory, how does one iterate over such large list in a reasonable amount of time? When I am taught algorithm my sa…
Seems like the solution is to employ MapReduce http://had00b.blogspot.com/2013/07/random-subset-in-mapreduc...
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#9Vitter's algorithm is for when you need to generate a random list of unique items with sequential reads. If you drop that requirement, you can just use a substitution-permutation network: https://en.wikipedia.org/wiki/Substitution-permutation_netwo...
A SPN will generate a unique random permutation, from which you can draw your random list of unique items. With a little of post-ptocessing, you can generate random permutations of arbitrary size.
I have implemented it in matlab and python:
http://nl.mathworks.com/matlabcentral/fileexchange/36626-alg...
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#10Why 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.