linux - 如何从文件中选择随机行

Question

我有一个包含 10 百行不同长度的文本文件。现在我想随机选择N行，将它们保存在另一个文件中，并从原始文件中删除它们。我已经找到了这个问题的一些答案，但大多数都使用一个简单的想法:对文件进行排序并选择前 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