Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reservoir Sampling

samwho.dev

Post reply on HN
Print view View original

41–50 of 107 posts

Re: Reservoir Sampling

#41

Post by samwho »

lol768 wrote: post #23
samwho wrote: post #11

Earlier quoted context omitted.

Thank you so much! The dogs on the playing cards were commissioned just for this post. They’re all made by the wonderful https://www.andycarolan.com/ . The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ . Oh, and you can pet the dogs. :)

It would've been easy to just use green for the held card and red for the discard pile. Thank you for using a colour-blind friendly palette; as someone with deuteranopia :)

You're welcome! I think it's a beautiful palette, and I think people have come to associate me with it now so I don't think I'll ever change.

I view all of my posts using the various colour blindness filters in the Chrome dev tools during development, to make sure I'm not using any ambiguous pairings. I'm glad that effort made you feel welcome and able to enjoy the content fully.

Re: Reservoir Sampling

#42

Post by samwho »

NoahZuniga wrote: post #33
fiddlerwoaroof wrote: post #19

Earlier quoted context omitted.

Does this method compose with itself? E.g. if I implement reservoir sampling in my service and then the log collector service implements reservoir sampling, is the result the same as if only the log collector implemented it?

Yes

I hadn’t considered this, cool to know it works!

Re: Reservoir Sampling

#43

Post by gregable »

Very well put together. If you are curious about the weighted version, I tried to explain it some here: https://gregable.com/2007/10/reservoir-sampling.html

There's also a distributed version, easy with a map reduce.

Or the very simple algorithm: generate a random paired for each item in the stream and keep the top N ordered by that random.

Re: Reservoir Sampling

#44

Post by lordnacho »

I discovered this in one of those coding quizzes they give you to get a job. I was reviewing questions and one of them was this exact thing. I had no idea how to do it until I read the answer, and then it was obvious.

Re: Reservoir Sampling

#45

Post by TheAlchemist »

samwho wrote: post #3

Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)

Very nice post - thank you. This is how maths and stats should be taught.

Reminds me a bit about https://distill.pub/

Re: Reservoir Sampling

#46

Post by samwho »

TheAlchemist wrote: post #45
samwho wrote: post #3

Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)

Very nice post - thank you. This is how maths and stats should be taught. Reminds me a bit about https://distill.pub/

I loved distill.pub. Usually didn’t fully grasp what the papers were about but they were beautiful and I usually got _something_ out of them.

Was very sad when they announced their hiatus. Made me nervous about the viability of this sort of content.

You may also enjoy https://pudding.cool.

Re: Reservoir Sampling

#47

Post by fanf2 »

stygiansonic wrote: post #4

Great article and nice explanation. I believe this describes “Algorithm R” in this paper from Vitter, who was probably the first to describe it: https://www.cs.umd.edu/~samir/498/vitter.pdf

That paper says “Algorithm R (which is a reservoir algorithm due to Alan Waterman)” but it doesn’t have a citation. Vitter’s previous paper https://dl.acm.org/doi/10.1145/358105.893 cites Knuth TAOCP vol 2. Knuth doesn’t have a citation.

Re: Reservoir Sampling

#48

Post by eru »

samwho wrote: post #3

Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)

Very nice post!

Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement.

That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on your tape drive (but you don't know up front how long your tape is), or because you send almost your whole system to sleep during skips.

For n items to sample from, this system does about O(k * log (n/k)) samples and skips.

Conceptually, I prefer the version of reservoir sampling that has you generate a fixed random 'priority' for each card as it arrives, and then you keep the top k items by priority around. That brings me to another related interesting algorithmic problem: selecting the top k items out of a stream of elements of unknown length in O(n) time and O(k) space. Naive approaches to reaching O(k) space will give you O(n log k) time, eg if you keep a min heap around.

What you can do instead is keep an unordered buffer of capacity up to 2k. As each item arrives, you add it to the buffer. When your buffer is full, you prune it to the top k element in O(k) with eg randomised quickselect or via median-of-medians. You do that O(2k) work every k elements for n elements total, given you the required O(n) = O(n * 2*k / k) runtime.

Another related topic is rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing

Tangentially related: https://www.keithschwarz.com/darts-dice-coins/ is a great write-up on the alias method for sampling from a discrete random distribution.

Re: Reservoir Sampling

#49

Post by eru »

samwho wrote: post #42
NoahZuniga wrote: post #33

Earlier quoted context omitted.

Yes

I hadn’t considered this, cool to know it works!

Though I think it's only strictly true, if the intervals you sample over are the same. Eg they both sample some messages every second, and the all start their second-long intervals on the same nanosecond (or close enough).

I find it easier to reason about reservoir sampling in an alternative formulation: the article talks about flipping a random (biased) coin for each arrival. Instead we can re-interpret reservoir sampling as assigning a random priority to each item, and then keeping the items with the top k priority.

It's fairly easy to see in this reformulation whether specific combinations of algorithms would compose: you only need to think about whether they would still select the top k items by priority.

Re: Reservoir Sampling

#50

Post by samwho »

eru wrote: post #48
samwho wrote: post #3

Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)

Very nice post! Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement. That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on…

I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible.
Post reply on HN