> 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.
I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements.
> More generally, reservoir sampling is appropriate when you don't know the size of the set beforehand. 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.
Last time I had to solve this, I came up with the following solution[1] which doesn't generate any duplicates and runs in O(k) where k is the size of result set.
I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements.
> More generally, reservoir sampling is appropriate when you don't know the size of the set beforehand. 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.
Last time I had to solve this, I came up with the following solution[1] which doesn't generate any duplicates and runs in O(k) where k is the size of result set.
[1] http://ideone.com/CAwuxW