perl - 如何使用 Perl 从文件中准确获取 n 行随机行？

Question

关注 this问题，我需要准确地得到 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从数组中随机，但如果我有一个非常大的文件，这是一个问题。

有任何想法吗？

编辑:这是 this 的完全重复题。

Answer 1

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

假设 M <= N。

让 S是所选行的集合。初始化 S到第一 M文件的行。如果最终结果的排序很重要，请 shuffle S现在。

阅读下一行 l .到目前为止，我们已经阅读了 n = M + 1总行。我们要选择的概率l因此，我们的最后一行是 M/n .

接受 l概率M/n ;使用 RNG 来决定是接受还是拒绝 l .

如 l已被接受，随机选择S中的一行并将其替换为 l .

重复步骤 2-4 直到文件用完行，递增 n每读取一个新行。

返回套装 S选定的行。