4 ms·

My favorite perl -ne '$l=$_ if rand()<(1/$.); END{print $l}' To pick a random line from a stream of unknown length in a single pass while only storing one

My favorite perl -ne '$l=$_ if rand()<(1/$.); END{print $l}' To pick a random line from a stream of unknown length in a single pass while only storing one line. With some more options it will handle a fortune file (or any stream of things that you can go through by record).

Donckele 6y ago
Can anyone explain how that works?
- gurkendoktor 6y ago
  Without knowing much Perl, I guess that $_ is the current line, and $. the number of lines read. This will pick the first input line with a 100% chance, overwrite it with the second line with a 50% chance, then overwrite it with the third line with a 33% chance, etc. Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise.
  - yesenadam 6y ago
    Well, the second line replaces the first line 50% of the time. 3 lines: The 3rd line has the correct 1/3 chance of being written, otherwise (with probability 2/3) one of the first 2 lines remain, and they had an equal 50% chance of being stored just prior to the 3rd line appearing, which now is 50% x 2/3 = 1/3. 4 lines: The 4th line has the correct 1/4 chance of being written, otherwise (with probability 3/4) one of the first 3 lines remain, and they had an equal 1/3 chance of being stored just prior to the 4th line appearing, now 1/3 x 3/4 = 1/4. Same argument applies all the way down. That's very neat! ... n lines: The nth line has the correct 1/n chance of being written, otherwise (with probability (n-1)/n) one of the first n-1 lines remain, and they had an equal 1/(n-1) chance of being stored just prior to the nth line appearing, now 1/(n-1) x (n-1)/n = 1/n.
  - tijsvd 6y ago
    > Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise. Quick try with recursive proof: Assume all preceding n-1 lines have equal probability of having been picked (p = 1/(n-1)). This is clearly true for the baseline n=2. Then for line n, it will replace the picked line with probability p=1/n, since that is in the algo. Any previous line will now have p=[1/(n-1)] * (1 - 1/n) = 1/n and the assumption holds.
- yoz-y 6y ago
  I can try. -ne modifiers are just to say to execute the script on every line of input. The body that will be executed in pseudo code is while get_input: if rand() < 1 / current_line_number: # $. contains the line number of input l := current_line_content # $_ always contains "what you want", in this case the current line # when using -n flat you can use BEGIN {} and END {} blocks # to execute code before and after the loop print(l) Now, as to why the random selection works, this is a simplified version of Reservoir Sampling[1] [1]: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
- kqr 6y ago
  It seems like nobody else mentioned this, so for completeness: the algorithm is called reservoir sampling. It allows you to sample n elements from a potentially very big stream with exactly n elements of storage. Incredibly neat technique. Lots written about it a web search away once you know its name! (If the sequence is in primary memory with fast random access, it's more efficient to run n iterations of a Fisher-Yates shuffle and pick the first n elements.) Edit: I forgot to refresh the comments page. Someone had mentioned it now. Good!

Donckele 6y ago

Can anyone explain how that works?

gurkendoktor 6y ago
Without knowing much Perl, I guess that $_ is the current line, and $. the number of lines read. This will pick the first input line with a 100% chance, overwrite it with the second line with a 50% chance, then overwrite it with the third line with a 33% chance, etc. Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise.
- yesenadam 6y ago
  Well, the second line replaces the first line 50% of the time. 3 lines: The 3rd line has the correct 1/3 chance of being written, otherwise (with probability 2/3) one of the first 2 lines remain, and they had an equal 50% chance of being stored just prior to the 3rd line appearing, which now is 50% x 2/3 = 1/3. 4 lines: The 4th line has the correct 1/4 chance of being written, otherwise (with probability 3/4) one of the first 3 lines remain, and they had an equal 1/3 chance of being stored just prior to the 4th line appearing, now 1/3 x 3/4 = 1/4. Same argument applies all the way down. That's very neat! ... n lines: The nth line has the correct 1/n chance of being written, otherwise (with probability (n-1)/n) one of the first n-1 lines remain, and they had an equal 1/(n-1) chance of being stored just prior to the nth line appearing, now 1/(n-1) x (n-1)/n = 1/n.
- tijsvd 6y ago
  > Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise. Quick try with recursive proof: Assume all preceding n-1 lines have equal probability of having been picked (p = 1/(n-1)). This is clearly true for the baseline n=2. Then for line n, it will replace the picked line with probability p=1/n, since that is in the algo. Any previous line will now have p=[1/(n-1)] * (1 - 1/n) = 1/n and the assumption holds.
yoz-y 6y ago
I can try. -ne modifiers are just to say to execute the script on every line of input. The body that will be executed in pseudo code is while get_input: if rand() < 1 / current_line_number: # $. contains the line number of input l := current_line_content # $_ always contains "what you want", in this case the current line # when using -n flat you can use BEGIN {} and END {} blocks # to execute code before and after the loop print(l) Now, as to why the random selection works, this is a simplified version of Reservoir Sampling[1] [1]: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
kqr 6y ago
It seems like nobody else mentioned this, so for completeness: the algorithm is called reservoir sampling. It allows you to sample n elements from a potentially very big stream with exactly n elements of storage. Incredibly neat technique. Lots written about it a web search away once you know its name! (If the sequence is in primary memory with fast random access, it's more efficient to run n iterations of a Fisher-Yates shuffle and pick the first n elements.) Edit: I forgot to refresh the comments page. Someone had mentioned it now. Good!