So to work through this, looping through some lettered items.
We encounter A, and unconditionally set winner = A.
We encounter B, and set winner = B with 50% probability. We now have a 50% probability of winner=A and a 50% probability of winner=B.
We encounter C, and set winner = C with 33% probability. In the other 66% of cases, it remains as it was, so we have winner=C with 33% probability and winner=A or winner=B with 66% * 50% = 33% probability.
IIRC, Knuth's book on algorithms had a less optimal way of doing this, and Waterman wrote him and said why not do it this way. The book was updated for this more efficient way of doing it!
I hardly ever remember the names of the people that discover these things, but the fact the guy who improved the reservoir algorithm was named Waterman has always stuck with me.
In SQL you might assign each item a random value then take the top K (and it should do a constant space scan, maintaining a heap of K best elements). It seems like physically that ends up being very similar! Each new element has some chance to evict a previous element, and that gets less likely as you go (as the expected best-seen scores increase).
If they’re so similar I wonder what advantages/disadvantages each approach has.
assigning each item a random value is already O(n), and assumes you can store the whole sequence or at least consume it more than once. reservoir sampling explicitly assumes you get the sequence as a stream you can only iterate once.
Interesting - I remember reading up on reservoir sampling while trying to solve the problem of plotting a static-sized chart of an unknown-in-advance-length signal on an MCU in Rust at O(N).
Gaelan | 17 hours ago
So to work through this, looping through some lettered items.
And so on.
Really clever!
ryan-duve | 14 hours ago
IIRC, Knuth's book on algorithms had a less optimal way of doing this, and Waterman wrote him and said why not do it this way. The book was updated for this more efficient way of doing it!
I hardly ever remember the names of the people that discover these things, but the fact the guy who improved the reservoir algorithm was named Waterman has always stuck with me.
LesleyLai | 17 hours ago
This is a good visualization of reservoir sampling: https://samwho.dev/reservoir-sampling
dpercy | 9 hours ago
In SQL you might assign each item a random value then take the top K (and it should do a constant space scan, maintaining a heap of K best elements). It seems like physically that ends up being very similar! Each new element has some chance to evict a previous element, and that gets less likely as you go (as the expected best-seen scores increase).
If they’re so similar I wonder what advantages/disadvantages each approach has.
zem | 7 hours ago
assigning each item a random value is already O(n), and assumes you can store the whole sequence or at least consume it more than once. reservoir sampling explicitly assumes you get the sequence as a stream you can only iterate once.
dpercy | 7 hours ago
I would expect the DB to assign them in one pass:
The query plan would have one iterator reading items, then a mapped / lazy iterator generating random keys, then a consumer that maintains the heap.
zem | 7 hours ago
reservoir sampling is such a gorgeous algorithm. one of those problems where it is not at all intuitively obvious that a solution is even possible.
eugeny | 13 hours ago
Interesting - I remember reading up on reservoir sampling while trying to solve the problem of plotting a static-sized chart of an unknown-in-advance-length signal on an MCU in Rust at O(N).
Turned out reservoir sampling can be nicely adapted to solve that: https://docs.rs/infinity-sampler/0.3.0/infinity_sampler/