使用Perl的两个数组的差异

Question

我有两个数组.我需要检查并查看其中一个元素是否出现在另一个元素中.

有没有比嵌套循环更有效的方法呢？我每个都有几千个元素,需要经常运行程序.

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 );

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;
}

Answer 3

您需要提供更多上下文.有更有效的方法可以做到:

• 走出Perl并使用shell(sort+ comm)

• map将一个数组转换为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大小的列表.

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假设没有重复的条目.

而且,即使是暴民指出的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与其对应的条目匹配,则只会退出for循环%array2_hash.现在,您必须显示所有条目%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
}

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 };