如何从文件中选择随机行

Question

我有一个包含10百行不同长度的文本文件.现在我想随机选择N行,将它们保存在另一个文件中,然后从原始文件中删除它们.我已经找到了这个问题的一些答案,但是大多数都使用了一个简单的想法:对文件进行排序并选择第一行或最后N行.不幸的是,这个想法对我不起作用,因为我想保留线的顺序.我尝试了这段代码,但它非常慢并需要数小时.

FILEsrc=$1;
FILEtrg=$2;
MaxLines=$3;
let LineIndex=1;
while [ "$LineIndex" -le "$MaxLines" ]
do
# count number of lines
NUM=$(wc -l $FILEsrc | sed 's/[ \r\t].*$//g');
let X=(${RANDOM} % ${NUM} + 1);
echo $X;
sed -n ${X}p ${FILEsrc}>>$FILEtrg; #write selected line into target file
sed -i -e  ${X}d ${FILEsrc};       #remove selected line from source file
LineIndex=`expr $LineIndex + 1`;
done

我在代码中发现这行是最耗时的一行:

sed -i -e  ${X}d ${FILEsrc};

有没有办法克服这个问题,使代码更快？由于我很着急,我可以请你发给我完整的c/c ++代码吗？

Answer 1

一个简单的O(n)算法描述如下:

http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done