random k-sample of a file

[Kirk McDonald]

Andrei Alexandrescu wrote:
> Kirk McDonald wrote:
>> Andrei Alexandrescu wrote:
>>> I just ran across a nice little problem that I wanted to share as an 
>>> exercise for the interested in futile pastimes.
>>>
>>> The challenge, should you accept it, is to write a program that given 
>>> a number k and a file, outputs k lines picked uniformly at random 
>>> from the file. (If the file has less than k lines, it should all be 
>>> output.) The file's size is unbounded so loading it in memory is not 
>>> an option. How'd you go about it?
>>>
>>>
>>> Andrei
>>
>> This is a classic interview question. The solution for k == 1 is easy:
>>
>> from random import randint
>>
>> chosen_line = None
>>
>> for i, line in enumerate(open('filename')):
>>     if randint(0, i) == 0:
>>         chosen_line = line
>>
>> print chosen_line
>>
>> (It is worth noting that randint() operates over an inclusive range.)
>>
>> If you do the math, this works out to a uniform distribution. For 
>> instance, say the file has three lines. Once we read in the third 
>> line, there is a 1 out of 3 chance that it will be picked as the 
>> chosen_line. Of the remaining 2 out of 3 chances, there is a 50% 
>> chance the second line will be chosen, and a 50% chance of the first 
>> line.
>>
>> Doing this for k > 1 becomes more complicated. We start by reading in 
>> the first k lines of the file. (And if we run out of lines before 
>> that, we're done.)
>>
>> import itertools
>> from random import randint
>>
>> f = open('filename')
>>
>> k_lines = list(itertools.islice(f, k))
>>
>> # Next we just iterate over the rest of the file. If we have exhausted
>> # the file, then the loop terminates immediately.
>> for i, line in enumerate(f, start=k):
>>     if randint(0, i) == 0:
>>         k_lines[randint(0, k-1)] = line
>>
>> for line in k_lines:
>>     print line
>>
>> This is my first crack at a solution. I am not sure how close to a 
>> uniform distribution this works out to.
>>
> 
> Oh forgot to mention this is superior numerically to bearophile's
> because it's not affected by floating point quantization vagaries. But 
> it came later too...
> 
> Andrei
> 

To be fair, I started writing it before bearophile posted his, and 
indeed did not see his solution until after I had posted it. :-)

-- 
Kirk McDonald