What algorithm did Windows XP use to choose your initial user picture?
26 points by hoistbypetard
26 points by hoistbypetard
So to work through this, looping through some lettered items.
And so on.
Really clever!
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.
I would expect the DB to assign them in one pass:
heap = new heap
for x in stream:
key = rand()
heap.insert(key, x)
if len(heap) > K:
heap.pop()
The query plan would have one iterator reading items, then a mapped / lazy iterator generating random keys, then a consumer that maintains the heap.
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.
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/