如何从Perl文件中获取n个随机行？

Question

关注这个问题,我需要n从文件(或stdin)中随机获取完整的行.这将类似于head或tail,除了我想从中间的一些.

现在,除了使用链接问题的解决方案循环文件之外,n在一次运行中获得精确线条的最佳方法是什么？

作为参考,我试过这个:

#!/usr/bin/perl -w
use strict;
my $ratio = shift;
print $ratio, "\n";
while () {
    print if ((int rand $ratio) == 1); 
}

$ratio我想要的线的粗略百分比在哪里.例如,如果我想要10行中的1个:

random_select 10 a.list

但是,这并没有给我一个确切的数额:

aaa> foreach i ( 0 1 2 3 4 5 6 7 8 9 )
foreach? random_select 10 a.list | wc -l
foreach? end
4739
4865
4739
4889
4934
4809
4712
4842
4814
4817

另一个想法是啜饮输入文件,然后n从数组中随机选择,但如果我有一个非常大的文件,这是一个问题.

有任何想法吗？

编辑:这是这个问题的完全重复.

Answer 1

这是我刚刚提出的一个很好的一次通过算法,具有O(N)时间复杂度和O(M)空间复杂度,用于从N行文件中读取M行.

假设M <= N.

1. 让我们S选择一行.初始化S为M文件的第一行.如果最终结果的排序很重要,请立即进行随机播放S.
2. 请阅读下一行l.到目前为止,我们已经读过n = M + 1总行数.因此,我们想要选择l作为最终线之一的概率M/n.
3. 接受l概率M/n; 使用RNG来决定是接受还是拒绝l.
4. 如果l已被接受,则随机选择其中一行S并替换为l.
5. 重复步骤2-4,直到文件已用完行,n每读取一行新行都会递增.
6. 返回S所选行的集合.