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

11–20 of 107 posts

Re: Reservoir Sampling

#11

Post by samwho »

malwrar wrote: post #10
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 :)

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!

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. :)

Re: Reservoir Sampling

#12

Post by dekhn »

owyn wrote: post #7
wood_spirit wrote: post #2

I 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.

I didn't know about the algorithm until after I got hired there. It's actually really useful in a number of contexts, but my favorite was using it to find optimal split points for sharding lexicographically sorted string keys for mapping. Often you will have a sorted table, but the underlying distribution of keys isn't known, so uniform sharding will often cause imbalances where some mappers end up doing far more work than others. I don't know if there is a convenient open source class to do this.

Re: Reservoir Sampling

#13

Post by rdtsc »

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 :)

Well done, I really like the animations and the explanation. Especially the case where it's a graph and we can drag ahead or click "shuffle 100 times"

One thing that threw me for a bit is when it switched from the intro of picking 3 cards at random from a deck of 10 or 436,234 to picking just one card. It's seems as if it almost needs a section heading before "Now let me throw you a curveball: what if I were to show you 1 card at a time, and you had to pick 1 at random?" indicating that now we're switching to a simplifying assumption that we're holding only 1 card not 3, but we also don't know the size of the deck.

Re: Reservoir Sampling

#14

Post by pandaxtc »

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 :)

This is awesome, I loved the interactivity!

Re: Reservoir Sampling

#16

Post by istjohn »

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 :)

Does your blog have an RSS feed?

Re: Reservoir Sampling

#17

Post by hinkley »

This reminds me that I need to spend more time thinking about the algorithm the allies used to count German tanks by serial number. The people in the field estimated about 5x as many tanks as were actually produced but the serial number trick was over 90% accurate.

Re: Reservoir Sampling

#18

Post by wood_spirit »

dekhn wrote: post #12
owyn wrote: post #7

Earlier quoted context omitted.

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.

I didn't know about the algorithm until after I got hired there. It's actually really useful in a number of contexts, but my favorite was using it to find optimal split points for sharding lexicographically sorted string keys for mapping. Often you will have a sorted table, but the underlying distribution of keys isn't known, so uniform sharding will often cause imbalances where some mappers end up doing far more wor…

Interesting idea, hadn’t that about that way to apply it.

I knew it from before my interview from a turbo pascal program I had seen that sampled dat tape backups of patient records from a hospital system. These samples were used for studies. That was a textbook example of it’s utility.

Re: Reservoir Sampling

#19

Post by fiddlerwoaroof »

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 :)

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?
Post reply on HN