Re: [PATCH] shuf: use reservoir-sampling when possible
From:
Assaf Gordon
Subject:
Re: [PATCH] shuf: use reservoir-sampling when possible
Date:
Mon, 25 Mar 2013 12:30:17 -0400
User-agent:
Mozilla/5.0 (X11; Linux x86_64; rv:10.0.4) Gecko/20120510 Icedove/10.0.4
Hello PƔdraig,
PƔdraig Brady wrote, On 03/24/2013 11:45 PM:
>>>>> On 03/06/2013 11:50 PM, Assaf Gordon wrote:
>>>>>> Attached is a suggestion to implement reservoir-sampling in shuf:
>>>>>> When the expected output of lines is known, it will not load the entire
>>>>>> file into memory - allowing shuffling very large inputs.
>
> I've attached 9 patches to adjust things a bit.
>
Looks great, thank you very much.
One minor improvement: the comment in the test file is wrong (in early stages
of the patch I thought I could use a fixed random-source and pre-calculate the
expected output).
Attached is a fix.
-gordon