使用Perl计算两个数组的差异

Question

我有两个数组，需要检查其中一个数组的元素是否出现在另一个数组中。

除了嵌套循环，有没有更有效率的方法呢？由于每个数组都有几千个元素，并且需要经常运行该程序。

- Buzkie

---

也许你可以发布一下你已经拥有的嵌套循环代码，这将帮助我们找到更好的方法来帮助你（如果有的话）。 - Greg Hewgill

如果我是你，我会从CPAN开始。看一下List::Compare - 特别是底部的部分 "If You Like List::Compare, You'll Love ..."。听起来你可能想要寻找一些用C实现而不是纯Perl的东西。http://search.cpan.org/perldoc/List::Compare - Telemachus

你的意思是需要知道一个数组是否为另一个数组的子集？还是它们完全相等？或者它们具有相同的元素，但顺序不同？你需要知道缺失哪些元素，还是只需要知道它们不相同？ - Schwern

Answer 1

另一种方法是使用 Array::Utils

use Array::Utils qw(:all);

my @a = qw( a b c d );
my @b = qw( c d e f );

# symmetric difference
my @diff = array_diff(@a, @b);

# intersection
my @isect = intersect(@a, @b);

# unique union
my @unique = unique(@a, @b);

# check if arrays contain same members
if ( !array_diff(@a, @b) ) {
        # do something
}

# get items from array @a that are not in array @b
my @minus = array_minus( @a, @b );

- Nifle

---

内部 Array::Utils 也使用 HASH 来比较数组元素。https://metacpan.org/source/ZMIJ/Array-Utils-0.5/Utils.pm - Bharat Pahalwani

很高兴看到如何检查两个数组是否相等。 - Eugen Konkov

Answer 2

perlfaq4 来帮忙:

如何计算两个数组的差异？如何计算两个数组的交集？

使用哈希表。以下代码可完成这些操作及更多。假设在给定的数组中每个元素都是唯一的：

   @union = @intersection = @difference = ();
    %count = ();
    foreach $element (@array1, @array2) { $count{$element}++ }
    foreach $element (keys %count) {
            push @union, $element;
            push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element;
    }

如果你正确声明变量，代码将更像以下内容：

my %count;
for my $element (@array1, @array2) { $count{$element}++ }

my ( @union, @intersection, @difference );
for my $element (keys %count) {
    push @union, $element;
    push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element;
}

- mob

---

代码示例可能并不完全是您问题的答案，但建议是正确的：使用哈希表。 - mob

你为什么链接到CPAN文档而不是perldoc文档？ - Zaid

1. http://search.cpan.org/perldoc/ 包含了整个CPAN的内容，不仅仅是核心文档和模块。
2. 我个人更喜欢CPAN网站的外观和感觉，而不是perldoc.perl.org。如果您更喜欢perl.org，那也可以。

- mob

Answer 3

您需要提供更多的上下文信息。有一些更高效的方法可以实现，包括：

• 从Perl中出来，使用shell命令（sort + comm）

• 将一个数组映射成一个Perl哈希表，然后循环遍历另一个数组检查哈希表成员身份。这种方法具有线性复杂度（"M+N" - 基本上只需对每个数组进行一次循环），而不是嵌套循环的"M*N"复杂度。

  例如：

my %second = map {$_=>1} @second;
my @only_in_first = grep { !$second{$_} } @first; 
# use a foreach loop with `last` instead of "grep" 
# if you only want yes/no answer instead of full list

使用一个Perl模块来代替最后一个任务点（评论中提到了List::Compare）

如果数据量很大且需要经常重新比较，则可以基于元素添加时间戳进行操作。几千个元素并不是真正的大数据，但我最近需要比较100k大小的列表。

- DVK

---

检查一个数组的元素是否存在于另一个数组中，我们可以使用两个map函数吗？我们代码中使用的两个map函数是否意味着它们应该是嵌套映射？ - P_Z

@DVK，没有“离开Perl并使用shell”比使用Perl本身更有效。 Perl是一种高度复杂、全功能但简洁的通用编程语言。通常情况下，除非标准UN*X / GNU-Linux实用程序绝对不作为Perl内置函数提供，否则应避免外壳运行它们，因为这些函数几乎总是更快且更强大。 - Medlock Perlman

Answer 4

你可以尝试使用Arrays::Utils，这使得代码看起来简洁明了，但它并没有在后台执行任何强大的魔法。下面是array_diffs代码：

sub array_diff(\@\@) {
    my %e = map { $_ => undef } @{$_[1]};
    return @{[ ( grep { (exists $e{$_}) ? ( delete $e{$_} ) : ( 1 ) } @{ $_[0] } ), keys %e ] };
}

自从Arrays::Utils不是标准模块，你需要考虑是否值得安装和维护这个模块。否则，这与DVK的答案相当接近。

有一些事情你必须注意，并且你必须定义你想在这种情况下做什么。比如说：

@array1 = qw(1 1 2 2 3 3 4 4 5 5);
@array2 = qw(1 2 3 4 5);

这些数组相同吗？或者说它们是不同的？它们具有相同的值，但是@array1中有重复值而@array2没有。

那么这个呢？

@array1 = qw( 1 1 2 3 4 5 );
@array2 = qw( 1 1 2 3 4 5 );

我认为这些数组是相同的，但是Array::Utils::arrays_diff不这么认为。这是因为Array::Utils假定没有重复的条目。

即使是由mob指出的Perl FAQ也说，它假设给定数组中的每个元素都是唯一的。这是一个你可以接受的假设吗？

无论如何，哈希表是答案。查找哈希表很容易和快速。问题是你想对唯一值做什么。

下面是一个假定重复项无关紧要的可靠解决方案：

sub array_diff {
    my @array1 = @{ shift() };
    my @array2 = @{ shift() }; 

    my %array1_hash;
    my %array2_hash;

    # Create a hash entry for each element in @array1
    for my $element ( @array1 ) {
       $array1_hash{$element} = @array1;
    }

    # Same for @array2: This time, use map instead of a loop
    map { $array_2{$_} = 1 } @array2;

    for my $entry ( @array2 ) {
        if ( not $array1_hash{$entry} ) {
            return 1;  #Entry in @array2 but not @array1: Differ
        }
    }
    if ( keys %array_hash1 != keys %array_hash2 ) {
       return 1;   #Arrays differ
    }
    else {
       return 0;   #Arrays contain the same elements
    }
}

如果重复项很重要，您需要一种计数的方式。以下是使用map不仅创建由数组中每个元素键入的哈希表，还计算数组中重复项的方法：

my %array1_hash;
my %array2_hash;
map { $array1_hash{$_} += 1 } @array1;
map { $array2_hash{$_} += 2 } @array2;

现在，您可以遍历每个哈希表并验证不仅存在键，而且它们的条目匹配。

for my $key ( keys %array1_hash ) {
    if ( not exists $array2_hash{$key} 
       or $array1_hash{$key} != $array2_hash{$key} ) {
       return 1;   #Arrays differ
    }
 }

只有在%array1_hash中的所有条目与其对应的%array2_hash中的所有条目匹配时，您才会退出for循环。现在，您需要展示%array2_hash中的所有条目也与其在%array1_hash中的条目相匹配，并且%array2_hash没有更多的条目。幸运的是，我们可以像之前一样做到这一点:

if ( keys %array2_hash != keys %array1_hash ) {
     return 1;  #Arrays have a different number of keys: Don't match
}
else {
     return;    #Arrays have the same keys: They do match
}

- David W.

Answer 5

您可以使用这个方法来获取两个数组之间的差异。

#!/usr/bin/perl -w
use strict;

my @list1 = (1, 2, 3, 4, 5);
my @list2 = (2, 3, 4);

my %diff;

@diff{ @list1 } = undef;
delete @diff{ @list2 };

- Pradeep Gupta

---

这只能找到list1中不在list2中的元素，但不能反过来。例如：list1 = (1, 2, 3)，list2 = (1, 2, 4, 5)。它们之间的差异应该是(3, 4, 5)，但这个方法只找到了一个差异(3)。 - ComputersAreNeat

Answer 6

你想要将@x的每个元素与@y相同索引的元素进行比较，对吗？这样就可以实现。

print "Index: $_ => \@x: $x[$_], \@y: $y[$_]\n" 
    for grep { $x[$_] != $y[$_] } 0 .. $#x;

...or...

foreach( 0 .. $#x ) {
    print "Index: $_ => \@x: $x[$_], \@y: $y[$_]\n" if $x[$_] != $y[$_];
}

你选择哪种方式，有点取决于你更关心的是保留不同元素的索引列表还是只是逐一处理不匹配的元素。grep版本很方便获取不匹配列表。（原文链接）

- Eugen Konkov

Answer 7

n + n log n算法，如果每个数组中的元素都是唯一的（作为哈希键）

my %count = (); 
foreach my $element (@array1, @array2) { 
    $count{$element}++;
}
my @difference = grep { $count{$_} == 1 } keys %count;
my @intersect  = grep { $count{$_} == 2 } keys %count;
my @union      = keys %count;

如果我不确定Unity并想检查array1中的元素是否存在于array2中，

my %count = (); 
foreach (@array1) {
    $count{$_} = 1 ;
};
foreach (@array2) {
    $count{$_} = 2 if $count{$_};
};
# N log N
if (grep { $_ == 1 } values %count) {
    return 'Some element of array1 does not appears in array2'
} else {
    return 'All elements of array1 are in array2'.
} 
# N + N log N

- MUY Belgium

Answer 8

my @a = (1,2,3); 
my @b=(2,3,1); 
print "Equal" if grep { $_ ~~ @b } @a == @b;

- rlib

---

在我看来，如果@b中包含"1"，这段代码似乎会打印出"Equal"。也许可以尝试say "Equal" if grep { $_ ~~ @b } @a && @a == @b ;...但是感觉还是有点靠不住。 - G. Cito

Answer 9

不够优雅，但易于理解：

#!/usr/local/bin/perl 
use strict;
my $file1 = shift or die("need file1");
my $file2 = shift or die("need file2");;
my @file1lines = split/\n/,`cat $file1`;
my @file2lines = split/\n/,`cat $file2`;
my %lines;
foreach my $file1line(@file1lines){
    $lines{$file1line}+=1;
}
foreach my $file2line(@file2lines){
    $lines{$file2line}+=2;
}
while(my($key,$value)=each%lines){
    if($value == 1){
        print "$key is in only $file1\n";
    }elsif($value == 2){
        print "$key is in only $file2\n";
    }elsif($value == 3){
        print "$key is in both $file1 and $file2\n";
    }
}
exit;
__END__

- skiddy1454576

Answer 10

尝试使用List::Compare。它提供了可以在数组上执行的所有操作的解决方案。

- Newbie