Algorithms Every Programmer Should Know: Reservoir Sampling
This algorithm was introduced with the premise<p>> <i>"I have a database table with #{17.kajillion} records, and I want to take a random sample of #{X} of them. How can I do this efficently?"</i><p>And goes on to say that something like `YourBigTable.all.sample(X)` is bad in time and space. And the link that explains why doing `ORDER BY RANDOM()` is bad lists one reason being that generation of random numbers is relatively expensive.<p>But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. It still beats `ORDER BY RANDOM()` because it doesn't have to sort the numbers (or even keep them all in memory at the same time). But that doesn't make it a good choice.<p>More generally, reservoir sampling is appropriate when you <i>don't know the size of the set beforehand</i>. But in the premise, we do know the size of the set. And if you know the size of the set (and have some way to address arbitrary elements), then randomly generating a set of X indices is going to be much simpler and faster. Yeah, you have to deal with duplicate indices, but that's an easy problem to solve.