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

91–100 of 107 posts

Re: Reservoir Sampling

#91

Post by jononor »

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…

Skipping like that is very interesting in battery-powered sensor systems, where you can put the system to sleep until it is time to sample.

Re: Reservoir Sampling

#94

Post by samwho »

tuzemec wrote: post #90

Nice! This is almost in the same league with Bartosz Ciechanowski's articles - https://ciechanow.ski/

Bartosz is a huge inspiration to me, you can likely tell that there are plenty of things he does in his post that I'm emulating in mine. It's maybe the best compliment you can give me to compare my work to his. Thank you.

Re: Reservoir Sampling

#95

Post by stefs »

swiftcoder wrote: post #89
amw-zero wrote: post #87

Earlier quoted context omitted.

You’re confusing statistics with forecasting. We can and should trust statistics. We should just never trust their relation to future behavior.

Fairly sure the previous poster is describing statistics that were made up, rather than measured/sampled. Those are, for hopefully obvious reasons, not very trustworthy

so, the actual lesson to be learned was more along the lines of "never trust lies".

Re: Reservoir Sampling

#96

Post by dekhn »

wood_spirit wrote: post #72
dekhn wrote: post #22

Earlier quoted context omitted.

I guess the question in my mind is: would you expect a smart person who did not previously know this problem (or really much random sampling at all) to come up with the algorithm on the fly in an interview? And if the person had seen it before and memorized the answer, does that provide any signal of their ability to code?

They wanted to see your analytical thinking skills at work. To pass you only needed to be sensible. You didn’t fail the interview if you couldn’t invent reservoir sampling!

uh, no, people would get a fail on the question if they didn't correctly identify both the initial selection and sample acceptance criteria.

Re: Reservoir Sampling

#97

Post by smusamashah »

eru wrote: post #56
samwho wrote: post #50

Earlier quoted context omitted.

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.

I have a few more topics we could cooperate on, if you are interested. https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d... has a 'very static' visualisation of sorting algorithms. Basically, we have a 2d plane, and we colour a pixel (x, y) black iff the sorting algorithm compares x with y when it runs. It's a resurrection (with AI) of an older project I was coding up manually at https://github.com/matthia…

I made a tool to visualize sorting algos https://xosh.org/VisualizingSorts/sorting.html where you can put your own algo too if you like.

Re: Reservoir Sampling

#98

Post by dan-robertson »

eru wrote: post #80
dan-robertson wrote: post #77

Earlier quoted context omitted.

Alias tables are neat and not super well known. We used to have an interview question around sampling from a weighted distribution (typical answer: prefix sum -> binary search) and I don’t think anyone produced this. I like the explanation in that blog. The way it was explained to me was first ‘imagine drawing a bar chart and throwing a dart at it, retrying if you miss. This simulates the distribution but runs in exp…

I'm not actually sure this makes for a good interview question. Doesn't it mostly just test whether you've heard of the alias method? Btw, a slightly related question: Supposed you have a really long text file, how would you randomly sample a line? Such that all lines in the text file have the exactly same probability. Ideally, you want to do this without spending O(size of file) time preprocessing. (I don't think th…

It’s a retired question (so I’m not really disagreeing that it wasn’t very good), and no one was expected to get the alias tables (if they did, just ask for updateable weights) and in fact there isn’t even much point in telling people about them as they can then get the impression they failed the interview. The point is more to get some kind of binary search and understanding of probability.

The Monte Carlo method you propose probably works for files where there are many short lines but totally fails in the degenerate case of one very long line. It also may not really work that well in practice because most of the cost of reading a random byte is reading a big block from disk, and you could likely scan such a block in ram faster than you could do the random read of the block from disk.

Re: Reservoir Sampling

#99

Post by DonHopkins »

samwho wrote: post #86
DonHopkins wrote: post #75

Earlier quoted context omitted.

So many nice touches that combine to be much more than the sum of the parts. Doe's bandana is cool, your dogs must worship you for your commitment to them! My only suggestion is a way to slow down or ^S the log to read the funny messages, since they were flying by so fast I could only get a glimpse, even with reservoir sampling. something something "needs more emojis"! ;)

Doe’s bandana is my attempt at tasteful solidarity and support. Glad you noticed it! I did consider a pause button for the logs but it felt too unsubtle, and distracts from the content of the post. You could argue the log messages are already distracting, but I really wanted my own take on “reticulating splines.” You can read how the messages are constructed here: https://github.com/samwho/visualisations/blob/main/re…

I THOUGHT I saw a a Herman-Miller chair fly by! So I'm not going crazy. whew

Re: Reservoir Sampling

#100

Post by BobaFloutist »

eru wrote: post #49
samwho wrote: post #42

Earlier quoted context omitted.

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 sa…

I would expect any way to get a truly fair sample from a truly fair sample would necessarily result in a truly fair sample. I can't imagine how it could possibly not.
Post reply on HN