6 ms·
Does this algorithm guarantee uniform probability for all lines? Seems like the original ordering of the lines is a factor.
by visarga 7y ago
Does this algorithm guarantee uniform probability for all lines? Seems like the original ordering of the lines is a factor.
- smilekzs 7y agoIt does. It's a special case of reservoir sampling. https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
- chubot 7y agoThe OP should have mentioned that it's this algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling IMO it's a lot clearer if it's not in Perl ... The pseudocode in Wikipedia also avoids division.
- ChristianGeek 7y agoIMO it’s a lot clearer if it’s not in Perl What isn’t?
- IngoBlechschmid 7y agoPerhaps surprisingly, yes, it does! This is called "reservoir sampling", and a blog post with some more details is available at https://blog.plover.com/prog/weighted-reservoir-sampling.html https://blog.plover.com/prog/weighted-reservoir-sampling.htm....
- patio11 7y agoIf you want to monte carlo it, https://gist.github.com/patio11/546c64c927c749c69964b18527fabe30 https://gist.github.com/patio11/546c64c927c749c69964b18527fa... ; feel free to adjust the constants upwards and/or do a chi squared test after doing so. It didn't sound plausible to me (because I misunderstood what the algorithm was; yay perl), hence quickly testing it, but it seems to work, and after appreciating what the algorithm actually is (see sibling replies), it not only works but it _should_ work. (There is a CS versus engineering joke in here, somewhere.)