3 ms·
Pick a random line from a file / stream without knowing how many lines there are to choose from in one pass without storing the lines that have been seen. pe
by zengargoyle 7y ago
Pick a random line from a file / stream without knowing how many lines there are to choose from in one pass without storing the lines that have been seen.
perl -e 'while(<>){$x=$_ if rand()<=(1/$.)}print $x'
For each line, pick that line as your random line if a random number (0<=n<1) is less than the reciprocal of the number of lines read so far ($.).
It hits my elegant bone. Only one line... rand < 1/1, pick it. Two lines, same as one, but the second line has a 1/2 change of replacing line one. Third line same as before but gets a 1/3 chance of taking the place of whichever line has survived the first two picks. At the end... you have your random line.
- visarga 7y agoDoes 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.)
- microtherion 7y agoSame number of keystrokes, but IMHO more idiomatic & readable: perl -ne '$x=$_ if rand()<=(1/$.); END { print $x }'
- zengargoyle 7y agoHa, that's how I originally wrote it, but I thought I should get rid of -n and END{} in an attempt to ward of the eww Perl comments. Sigh. But at least now I know that it's called Reservoir Sampling. I had wondered how to generalize it to wanting N lines.