6 ms·
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 enti
by majorchord 8d ago
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.
- tyrust 8d agoIf 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/ https://florian.github.io/reservoir-sampling/
- majorchord 8d agoBut wouldn't changing the probability be even more random?
- bspammer 8d agoIf you read the "Adapting Probabilities" section of the link above, there's a nice explanation of why changing the probability works.
- Crestwave 8d agoThe 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.