在Perl中获取file2中没有出现的所有行的最快方法是什么？

Question

我有两个(非常大的)文本文件.在运行时方面,最快的方法是创建第三个文件,其中包含未出现在file2中的所有file1行？

所以如果file1包含:

Sally  
Joe  
Tom  
Suzie

而file2包含:

Sally  
Suzie  
Harry  
Tom

然后输出文件应包含:

Joe

Answer 1

创建一个包含文件2中每一行的hashmap.然后,对于文件1中的每一行,如果它不在hashmap中,则输出它.这将是O(N),这是您可以实现的最佳效率等级,因为您必须阅读输入.

Perl实现:

#!/usr/bin/env perl
use warnings;
use strict;
use Carp ();

my $file1 = 'file1.txt';
my $file2 = 'file2.txt';

my %map;
{
    open my $in, '<',$file2 or Carp::croak("Cant open $file2");
    while (<$in>) {
      $map{$_} = 1;
    }
    close($in) or Carp::carp("error closing $file2");
}
{
   open my $in,'<', $file1 or Carp::croak("Cant open $file1");
   while (<$in>) {
    if (!$map{$_}) {
      print $_;
    }
   }
   close $in or Carp::carp("error closing $file1");
}

如果文件2太大以至于hashmap不适合内存,那么我们手头就有了不同的问题.然后可能的解决方案是在文件2的块上使用上述解决方案(小到足以装入内存),将结果输出到临时文件.如果文件1和文件2之间有足够的匹配,那么总输出应该是合理的大小.为了计算最终结果,我们在临时文件中执行行的交集,即对于在最终结果中的行,它必须在每个临时文件中出现.

Answer 2

不是Perl但有效:

diff <(sort file1) <(sort file2)

Answer 3

我很惊讶没有人提出了最节省内存的方法,即分别对两个文件进行排序,然后执行列表合并.如果您使用的是Unix,则以下3个简单命令可以快速执行您所需的操作:

sort < file1 > file1.sorted
sort < file2 > file2.sorted
comm -2 -3 file1.sorted file2.sorted > differences

如果文件是如此之大,Perl有页面VM加载的所有行到一个哈希表,该技术将是多快. 否则,基于散列表的方法应该更快.

如果您使用的是Unix,最好使用系统的外部sort命令,因为它对内存使用情况很sort()敏感- 使用Perl 需要将文件的全部内容读入内存.

如果您使用的是Windows,请注意提供的sort命令不区分大小写,并且无法关闭!commWindows上 也没有命令,所以你需要自己动手 - 用上面的第三行替换:

perl subtract_sets.pl file1.sorted file2.sorted > differences.txt

subtract_sets.pl

#!/usr/bin/perl
open my $f1, '<', $ARGV[0] or die;
open my $f2, '<', $ARGV[1] or die;

my $x = <$f1>;
my $y = <$f2>;

while (defined $x && defined $y) {
    if ($x lt $y) {
        print $x;
        $x = <$f1>;
    } elsif ($y lt $x) {
        print $y;
        $y = <$f2>;
    } else {
        # Lines match
        $x = <$f1>;
        $y = <$f2>;
    }
}

while (defined $x) {
    print $x;
    $x = <$f1>;
}

while (defined $y) {
    print $y;
    $y = <$f2>;
}