An elegant and simple random line selection algorithm
If you could read in a file only once and had to select one random line from it and put it to the screen, how would you implement that?
I wouldn't be able to tell you if hadn't been for one of my mentors, Jeremy Fleischman. A short side note: I met Jeremy and my other Mentor, Phil Aquilina, two days ago during the Mentor Introduction Night here at Dev Bootcamp. Both are amazing people and I am excited to have the chance to code with both of them.
Back to the question: If you could only read a file once, could you pick a random line from that file and print it? Imagine the file is so huge, you couldn't store all of it memory. How could you FAIRLY (give each line a fair chance) pick a random line?
I wouldn't be able to give you this answer without a little guidance from Jeremy, so thank you Jeremy. Check out this code snippet:
https://gist.github.com/3870423
Let's use some math to prove that this is truly random for \(\large n\) lines.
Consider the case when there is only one line to read...
count = 1
if Random.rand(count) == 0 #==> true
motd = file_reader.readline #==> "first line"
The first line will always be chosen into the array so the chances to save the first line is 100%
count = 2
if Random.rand(count) == 0 #==> 0=true 1=false
motd = file_reader.readline #==>
If random returns 0 then save the second line. There is a \(\large\frac{1}{2}\) or \(\large\frac{1}{n}\) chance to keep the previously saved line.
Now for a three line file...
count = 3
if Random.rand(count) == 0 #==> 0=true 1=false 2=false
motd = file_reader.readline #==>
If random returns 1, then save the third line. There is a \(\large\frac{2}{3}\) chance to keep the previously saved line. In a four line file there is a \(\large\frac{3}{4}\) to keep the previous line, \(\large\frac{4}{5}\) in a five line file and so on...
If we know that the probability to choose \(\large n\) is \(\large\frac{1}{n}\) and the probability to choose the next line is \(\large\frac{1}{n+1}\). If all lines should be chosen fairly then \(\large\frac{1}{n}\) \(\cdot P() = \large\frac{1}{n+1}\), \(P() = \large\frac{n}{n+1}\)
Let's test it. For 2 lines, there is a (\(\large\frac{1}{n}\)) or \(\large\frac{1}{2}\) chance to keep the first line. If we add one more line the chance to pick that would be (\(\large\frac{1}{n+1}\)) or\(\large\frac{1}{3}\) and the chance to keep the previous line would be (\(\large\frac{n}{n+1}\)) or \(\large\frac{2}{3}\).
3 line file: \(\large\frac{1}{n}\) \(\large\cdot\frac{n}{n+1} = \frac{1}{n+1}\) => \(\large\frac{1}{2}\cdot\frac{2}{3} = \frac{1}{3}\)
6 line file: \(\large\frac{1}{n}\)\(\large\cdot\frac{n}{n+1} = \frac{1}{n+1}\) => \(\large\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{3}{4}\cdot\frac{4}{5}\cdot\frac{5}{6} = \frac{1}{6}\)
YES! You can read a file only once and choose a random line fairly without knowing the number of lines or storing the entire file. I can't wait to go over cool algorithms with Jeremy on mentor days!