perl - 比较单个文件中的行

Question

我想知道是否有更有效的方法来完成我正在尝试的事情。我需要读取一个文件并将文件的每一行与它后面的所有行进行比较。 (即比较第 1 行与第 2、3、4、5 行，...；第 2 行与 3、4、5，...；第 3 行与 4,5...等)。我觉得有些文件太大而无法完全读入@lists，所以我现在通过打开同一个文件的两个文件句柄并使用 tell 和 seek 来获取一个文件的位置并设置另一个文件的位置来做到这一点像这样:

open FH1, '/arf/test.txt';
open FH2, '/arf/test.txt';

while ($outer = <FH1>){
    chomp($outer);
    $fh1Posn = tell FH1;
    seek FH2, $fh1Posn, 0;
    while ($inner = <FH2>){
        [code to compare line];
    }
}

这在小文件中工作得很好，但是对于我需要处理的一些较大文件来说是一个拖累(即使我用虚拟代码代替比较部分)。也许这是意料之中的，但我想知道是否有什么我可以尝试加快文件读取速度的方法？我正在考虑只使用一个文件句柄，消除第二个并在 while 循环的底部使用 $fh1Posn 将光标重置回它在顶部的位置，例如:

open FH1, '/arf/test.txt';

while ($outer = <FH1>){
    chomp($outer);
    $fh1Posn = tell FH1;
    while ($inner = <FH1>){
        [code to compare line];
    }
    seek FH1, $fh1Posn, 0;
}

还没有尝试过 - 会尝试 - 但感觉它可能不会做任何值得麻烦的事。

Answer 1

最快的解决方案是完全在内存中完成，将磁盘读取限制为一次。如果您没有足够的内存来执行此操作，那么我建议将其分成几 block 。

您当前的解决方案是读取文件 O(n^2) 次是内存不足的最坏情况解决方案。如果以 1000 行为一组执行此操作，则可以大大减少磁盘操作。当然，您必须通过试验才能找到真正的内存限制。

my $buffersize = 1000;

open FH1, '/arf/test.txt';
open FH2, '/arf/test.txt';

while (! eof(FH1)) {
    my @buffer = ();
    for (1..$buffersize) {
        my $outer = <FH1>;
        chomp $outer;
        push @buffer, $outer;
        last if eof(FH1);
    }

    # Seek code here

    while ($inner = <FH2>){
        for (@buffer) {
            [code to compare line];
        }
    }
}

2 月 25 日星期五的附录 - 更详细的代码解决方案

我在一天结束时还有一些额外的时间，所以我编写了一个版本，该版本适用于名为 test.txt 的文件，该文件每行包含数字 1-10。因此，我将缓冲区大小配置为仅 4，以便脚本执行 4 次文件传递而不是 11 次，就像您的原始方法那样。

use strict;
use warnings;
use autodie;

my $buffersize = 4; # 1000;
my $file = 'test.txt'; # '/arf/test.txt';

open my $fh1, '<', $file;
open my $fh2, '<', $file;

while (! eof($fh1)) {

    # Move fh2 to start of buffer
    my $startofbuffer = tell($fh1);
    seek($fh2, $startofbuffer, 0);

    # Build Buffer of entries to compare
    my @buffer = ();
    for (1..$buffersize) {
        chomp(my $outer = <$fh1>);
        print "buffer, $.\n";
        push @buffer, $outer;
        last if eof($fh1);
    }

    # Keep track of relative offset to start of buffer
    for (my $offset = 0; !eof($fh2); $offset++) {
        chomp(my $inner = <$fh2>);

        for my $i (0..$#buffer) {
            last if $i >= $offset;
            my $outer = $buffer[$i];
            print "Compare outer $outer to inner $inner\n";
        }
    }
}

输出结果如下

buffer, 1
buffer, 2
buffer, 3
buffer, 4
Compare outer 1 to inner 2
Compare outer 1 to inner 3
Compare outer 2 to inner 3
Compare outer 1 to inner 4
Compare outer 2 to inner 4
Compare outer 3 to inner 4
Compare outer 1 to inner 5
Compare outer 2 to inner 5
Compare outer 3 to inner 5
Compare outer 4 to inner 5
Compare outer 1 to inner 6
Compare outer 2 to inner 6
Compare outer 3 to inner 6
Compare outer 4 to inner 6
Compare outer 1 to inner 7
Compare outer 2 to inner 7
Compare outer 3 to inner 7
Compare outer 4 to inner 7
Compare outer 1 to inner 8
Compare outer 2 to inner 8
Compare outer 3 to inner 8
Compare outer 4 to inner 8
Compare outer 1 to inner 9
Compare outer 2 to inner 9
Compare outer 3 to inner 9
Compare outer 4 to inner 9
Compare outer 1 to inner 10
Compare outer 2 to inner 10
Compare outer 3 to inner 10
Compare outer 4 to inner 10
buffer, 5
buffer, 6
buffer, 7
buffer, 8
Compare outer 5 to inner 6
Compare outer 5 to inner 7
Compare outer 6 to inner 7
Compare outer 5 to inner 8
Compare outer 6 to inner 8
Compare outer 7 to inner 8
Compare outer 5 to inner 9
Compare outer 6 to inner 9
Compare outer 7 to inner 9
Compare outer 8 to inner 9
Compare outer 5 to inner 10
Compare outer 6 to inner 10
Compare outer 7 to inner 10
Compare outer 8 to inner 10
buffer, 9
buffer, 10
Compare outer 9 to inner 10

3 月 2 日星期日的附录 - 基准

您关于速度没有提高的报告让我有点好奇，所以我创建了一个小脚本来制作一些假数据:

use strict;
use warnings;
use autodie;

my $lines = shift or die "Missing line count\n";
die "Lines outside of range 1 - 1,000,000" if $lines < 1 or $lines > 1_000_000;

my $fakedata = 70;

my $filename = 'fd' . sprintf("%06d", $lines) . '.txt';

open my $fh, '>', $filename;

for my $i (1..$lines) {
    my $fake = join '', map {('a'..'z')[int rand 26]} (1..$fakedata);

    $fh->print("$i fake${fake}fake\n");
}

close $fh;

print "Created $filename\n";

1;

__END__

然后我编辑了上面提供的详细代码，使其不输出任何调试语句，而是进行了非常基础的比较。对于行数为 1_000、10_000 和 20_000 的文件，这导致了以下结果。

                For Buffer size, show Time in sec and (# of File Reads)                --------------------------------------------------------File by lines   b = 1        b = 10      b = 100     b = 1k      b = 10k  -------------   -----        ------      -------     ------      -------  Lines = 1k      t = 1.54s    t = 0.35s   t = 0.22s   t = 0.21             Size = 88k      r = (1001)   r = (101)   r = (11)    r = (2)              Tests = 500k                                                              Lines = 10k     t = 185s     t = 35s     t = 23s     t = 21.7s   t = 21.5sSize = 899k     r = (10k)    r = (1k)    r = (101)   r = (11)    r = (2)  Tests = 50m                                                               Lines = 20k     t = 593s     t = 136s    t = 90s     t = 86s     t = 85.5sSize = 1.8m     r = (20k)    r = (2k)    r = (201)   r = (21)    r = (3)  Tests = 200m                                                              

如您所见，即使只有 100 个缓冲，脚本时间也会减少 5 个或更多个数量级。这些脚本仍然需要很长时间，因为比较的次数等于 N * N/2。对于 20k 文件，这是 2 亿次测试，这就是为什么你可以看到执行该文件所需的时间是 4 倍只要10k文件。

如果这些值成立，您的 250k 长度文件将比 20k 文件花费 156.25 倍的时间。在有缓冲的最佳情况下，这相当于 3.71 小时，或者根本没有缓冲的情况下为 25.7 小时。这些数字甚至假定了用于比较的绝对最短时间，我认为您的数字可能比简单的旧/偶数测试更复杂。

不幸的是，您没有说明项目的性质和这些比较，所以我无法真正推测其他可能的速度改进。如果我假设您的目标更多是排序的性质，那么可以将您的比较减少到 O(n log n) 而不是 O(N**2)。对于排序，我建议您将文件分成能够放入内存的组，使用 perl sort 对它们进行排序，然后使用合并排序来合并排序的组。不过，我不会费心提供更详细的代码，因为这只是推测，这就是您的目的。

无论如何，祝你的项目好运。