Hacker News Reader

Wouldn't it be even more random (and randomly faster) to break out of the while loop when a winner is found? That way you are not always iterating over the entire list.

Perhaps a math/statistics expert can tell me why that is a bad idea.

View on HN

If you break early, then you haven't given items later in the list the chance to be selected. You need to go through the entire list in order for every item to have an equal probability of selection.

I didn't get it at first, either, and the Wikipedia article didn't do it for me. This explanation finally got me there: https://florian.github.io/reservoir-sampling/

But wouldn't changing the probability be even more random?

If you read the "Adapting Probabilities" section of the link above, there's a nice explanation of why changing the probability works.

The first iteration has a 100% chance of being marked as a winner. It only balances out to the same odds as a random selection because of the chances of it getting overwritten by the succeeding files.

Reply on news.ycombinator.com