5 ms·

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

by yeukhon 11y ago

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

doh 11y ago
Seems like the solution is to employ MapReduce http://had00b.blogspot.com/2013/07/random-subset-in-mapreduce.html http://had00b.blogspot.com/2013/07/random-subset-in-mapreduc...
knz42 11y ago
The algorithm accesses each element in the input only once, and in order. It's like reading a big file. Just call read() repeatedly, and discard old data each time you call read() again.
lsiebert 11y ago
Basically you do a reverse fisher yates shuffle. You are selecting n of N items, where N is unknown, in one pass, where every item is treated as unique, and where n is your sample size. First get n items from N in an array of size n of candidates, which we'll call C. Then, for each item k in N until you reach the end you know the current highest count, so select a random integer representing a location in an array of that count. If it's 0 to n - 1 (assuming a zero indexed array) replace the item in C with the current item k. This means that each item will have an equal chance of being a final candidate when you reach N. If you care about order of the random sample, you can always shuffle n after you reach N.

by yeukhon 11y ago

doh 11y ago

Seems like the solution is to employ MapReduce http://had00b.blogspot.com/2013/07/random-subset-in-mapreduce.html http://had00b.blogspot.com/2013/07/random-subset-in-mapreduc...

knz42 11y ago

The algorithm accesses each element in the input only once, and in order. It's like reading a big file. Just call read() repeatedly, and discard old data each time you call read() again.

lsiebert 11y ago

Basically you do a reverse fisher yates shuffle. You are selecting n of N items, where N is unknown, in one pass, where every item is treated as unique, and where n is your sample size. First get n items from N in an array of size n of candidates, which we'll call C. Then, for each item k in N until you reach the end you know the current highest count, so select a random integer representing a location in an array of that count. If it's 0 to n - 1 (assuming a zero indexed array) replace the item in C with the current item k. This means that each item will have an equal chance of being a final candidate when you reach N. If you care about order of the random sample, you can always shuffle n after you reach N.