如何使用Perl从文件中获取恰好n行随机行？

Question

在这个问题的基础上，我需要从文件（或stdin）中随机获取恰好n行。这类似于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个元素，但如果文件过大就会出现问题。

有什么其他的想法吗？

编辑：这与此问题完全相同。

- Nathan Fellman

---

这不是 https://dev59.com/kXRB5IYBdhLWcg3wLk1M 的完全重复吗？该如何在不读取整个文件的情况下随机选择文件中的行？ - Matthew Flaschen

是的，没错。对不起。我会将它们链接在一起并投票关闭它。 - Nathan Fellman

不，另一个问题允许示例不准确 - 这个问题需要一个确切的数字。 - Alnitak

请不要关闭此内容 - 它 不是 重复的 - Alnitak

Answer 1

这是一个很好的一遍算法，可以从N行文件中读取M行，并具有O(N)时间复杂度和O(M)空间复杂度。

假设M <= N。

1. 让S成为所选行的集合。将S初始化为文件的前M行。如果最终结果的排序很重要，请现在随机排列S。
2. 读取下一行l。到目前为止，我们已经读取了n = M + 1总行数。我们想要选择l作为我们最终行之一的概率因此是M/n。
3. 以M/n的概率接受l；使用RNG决定是否接受或拒绝l。
4. 如果l被接受，则随机选择S中的一行并用l替换它。
5. 重复步骤2-4，直到文件耗尽行，每读取一行就增加n。
6. 返回所选行的集合S。

- kquinn

---

不错，但我认为你的意思是 M <= N。 - Alnitak

翻转的符号是数学家永恒的敌人。带着叹息，修复它。 - kquinn

此外，除非N >> M，否则是否存在对原始M行的偏见？ - Alnitak

据我所知，不是这样的；考虑从一个6行文件中选择5行。其中一行将被排除；以5/6的概率它将是前5行之一，以1/6的概率它将是最后一行；这正是你想要的。这个算法的棘手之处在于，随着读入更多的行，n以及拒绝概率也会发生变化。 - kquinn

在基于流的文件系统上（包括Windows和Unix等大多数现代系统），查找“行”是一项昂贵的操作。（需要进行大量比较以查找行终止符）。我下面提供的解决方案通过使用seek在文件中随机定位，然后向前搜索以获取下一行完整内容来解决了这个问题。 - rmeden

Answer 2

这个程序需要一个命令行参数，即你想要的行数N。前N行会被记录下来，因为你可能不会再看到更多。之后，你会随机决定是否接受下一行，并且如果你接受了，你会随机决定在当前N行列表中覆盖哪一行。

#!/usr/bin/perl
my $bufsize = shift;
my @list = ();

srand();
while (<>)
{
    push(@list, $_), next if (@list < $bufsize);
    $list[ rand(@list) ] = $_ if (rand($. / $bufsize) < 1);
}
print foreach @list;

- Elbin

Answer 3

@result = ();

$k = 0;
while(<>) {
    $k++;
    if (scalar @result < $n) {
        push @result, $_;
    } else {
        if (rand <= $n/$k) {
            $result[int rand $n] = $_;
        }
    }
}

print for @result;

- kcwu

---

你的随机测试有误 - 应该是$n / $k，而不是1.0 / $k； - Alnitak

Answer 4

可能的解决方案：

1. 扫描一次以计算行数
2. 决定随机选择的行号
3. 再次扫描，选取该行

- kcwu

---

在标准输入上，扫描两次可能会出现问题。 - Eyal

Answer 5

不需要知道文件中实际的行号。只需随机跳转到某个位置并保留下一行。（当前行很可能是部分行。）

对于大文件，这种方法应该非常快，但对于STDIN无效。除了将整个文件缓存到内存中，否则什么都不起作用。因此，如果必须使用STDIN，则我不知道如何在处理大文件时做到快速/廉价。

您可以检测STDIN并切换到缓存方法，否则要快。

#!perl
use strict;
my $file='file.txt';
my $count=shift || 10;
my $size=-s $file;
open(FILE,$file) || die "Can't open $file\n";
while ($count--) {
   seek(FILE,int(rand($size)),0);
   $_=readline(FILE);                         # ignore partial line
   redo unless defined ($_ = readline(FILE)); # catch EOF
   print $_;
}

- rmeden

---

请注意，这种方法不会均匀地从文件中选择行。选择某一行的概率将根据前一行的长度加权；如果所有行的长度相同，则没有问题。但是，如果您需要从具有不同长度行的文件中严格均匀地分布行，则需要采用不同的方法。 - kquinn

你说得对... 哦，好吧... 它确实很快 :) 但如果记录长度是静态的或者非常接近静态的话，它还是很有用的。 - rmeden

Answer 6

在伪代码中：

use List::Util qw[shuffle];

# read and shuffle the whole file
@list = shuffle(<>);

# take the first 'n' from the list
splice(@list, ...);

这是最简单的实现方式，但您必须先读取整个文件，这将需要足够的可用内存。

- Alnitak

---

这正是我遇到的问题。我正在处理的文件大小为63MB，需要很长时间。 - Nathan Fellman

文件大小63MB？你有多少MB的内存？我认为这个大小不应该是个问题。 - kcwu

确定文件中的行数，创建一个与行数相等长度的数组，对该数组进行乱序处理，切割出所需的行数，对列表进行排序，然后在文件中循环迭代输出指定的行号。这种方法与读取整个文件所需时间大致相同。 - jrockway

Answer 7

这里有一些冗长的Perl代码，适用于大文件。

这段代码的核心是它不会将整个文件存储在内存中，而只会存储文件中的偏移量。

使用tell获取偏移量。然后使用seek到适当的位置来恢复行。

更好地指定目标文件和要获取的行数留给那些比我不那么懒的人作为练习。这些问题已经得到了很好的解决。

#!/usr/bin/perl

use strict;
use warnings;

use List::Util qw(shuffle);

my $GET_LINES = 10; 

my @line_starts;
open( my $fh, '<', 'big_text_file' )
    or die "Oh, fudge: $!\n";

do {
    push @line_starts, tell $fh
} while ( <$fh> );

my $count = @line_starts;
print "Got $count lines\n";

my @shuffled_starts = (shuffle @line_starts)[0..$GET_LINES-1];

for my $start ( @shuffled_starts ) {

    seek $fh, $start, 0
        or die "Unable to seek to line - $!\n";

    print scalar <$fh>;
}

- daotoad