Reservoir Sampling
samwho.dev
Reservoir Sampling
1–10 of 107 posts
Re: Reservoir Sampling
#2I remember this turning up in a google interview back in the day. The interview was really expecting me not to know the algorithm and to flounder about trying to solve the problem from first principles. Was fun to just shortcut things by knowing the answer that time.
Re: Reservoir Sampling
#3Hello! 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 :)
Re: Reservoir Sampling
#4Great 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
Re: Reservoir Sampling
#5great article!
Re: Reservoir Sampling
#6This is a great post that also illustrates the tradeoffs inherent in telemetry collection (traces, logs, metrics) for analysis. It's a capital-H Hard space to operate in that a lot of developers either don't know about, or take for granted.
Re: Reservoir Sampling
#7I remember this turning up in a google interview back in the day. The interview was really expecting me not to know the algorithm and to flounder about trying to solve the problem from first principles. Was fun to just shortcut things by knowing the answer that time.
Yeah, this was a google interview question for me too. I didn't know the algorithm and floundered around trying to solve the problem. I came up with the 1/n and k/n selection strategy but still didn't get the job lol. I think the guy who interviewed me was just killing time until lunch.
I like the visualizations in this article, really good explanation.
Re: Reservoir Sampling
#8This is a really nicely written and illustrated post.
An advanced extension to this is that there are algorithms which calculate the number of records to skip rather than doing a trial per record. This has a good write-up of them: https://richardstartin.github.io/posts/reservoir-sampling
Re: Reservoir Sampling
#9We lived in a rural area when I was a kid. My dad told me once that his buddy had to measure the ptarmigan[1] population in the mountains each year as part of his job.
He did this by hiking a fixed route, and at fixed intervals scare the birds so they would fly and count.
The total count was submitted to some office which used it to estimate the population.
One year he had to travel abroad when the counting had to be done, so he recruited a friend and explained in detail how to do it.
However when the day of the counting arrived his friend forgot, and it was a huge hassle anyway so he just submitted a number he figured was about right, and that was that.
Then one day the following year, the local newspaper had a frontpage headline stating "record increase in ptarmigan population".
The reason it was big news was that the population estimate was used to set the hunting quotas, something his friend had not considered...
Re: Reservoir Sampling
#10Hello! 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 :)
Love your website’s design, I find all of interactivity, the dog character as an “audience”, and even the font/color/layout wonderful. Loved the article too!