如何在perl中对数组进行快速比较

Question

可能重复： 在Perl中，是否有一个内置的方法来比较两个数组的相等性？

我需要将数组与应该返回的函数进行比较：

• 如果所有元素成对比较时都相等，则为true。
• 如果所有元素相等，或者第一个数组中的元素在成对比较时为未定义的，则为true。
• 在所有其他情况下为假

换句话说，如果潜艇被称为"comp"：

@a = ('a', 'b', undef, 'c');
@b = ('a', 'b', 'f', 'c');
comp(@a, @b); # should return true
comp(@b, @a); # should return false

@a = ('a', 'b');
@b = ('a', 'b', 'f', 'c');
comp(@a, @b); # should return true

显而易见的解决方案是对两个数组进行成对比较，但我希望它比这更快，因为比较是在一组数组上多次运行的，所以和数组可能有许多元素。

另一方面，要比较的数组的内容(即:所有可能的@b)是预先确定的，不会改变。数组的元素没有固定的长度，也不能保证它们可能包含哪些字符(制表符、逗号、名称)。

有比两两比较更快的方法吗？智能匹配不会削减它，因为如果所有元素都相等(因此如果一个元素是undef，则不会返回true )。

包装和按位进行比较是否是一种策略？当我浏览文档中的pack/unpack和vec时，它看起来很有希望，但我有点超出了我的深度。

谢谢。

Answer 1

Perl可以比较我的Macbook上大约100 is中10,000个成对元素的列表，所以我首先要说的是分析您的代码，以确保这确实是问题所在。

做一些基准测试，你可以做一些事情来加快速度。

• 确保在第一次不匹配的情况下保释。

假设您有许多不匹配的比较，这将节省大量时间。

• 前面检查数组的长度是否相同。

如果它们的数组不是相同的长度，它们就永远无法匹配。比较它们的大小，如果它们不同的话尽早返回。这避免了在循环中反复检查这种情况。

• 使用迭代器而不是C风格的循环.

按对迭代，您通常会执行类似于for( my $idx = 0; $idx <= $#a; $idx += 2 )的操作，但是遍历数组比使用C样式的for循环更快。这是Perl的一个优化技巧，用优化的C语言在perl中完成工作比在Perl代码中完成更有效。这将使你获得大约20%-30%的收益，这取决于你如何对它进行微观优化。

for my $mark (0..$#{$a}/2) {
    my $idx = $mark * 2;
    next if !defined $a->[$idx] || !defined $b->[$idx];
    return 0 if $a->[$idx] ne $b->[$idx] || $a->[$idx+1] ne $b->[$idx+1];
}
return 1;

• 预先计算有趣的索引。

由于一组对是固定的，所以可以生成定义对的索引。这使得迭代器更简单、更快。

state $indexes = precompute_indexes($b);

for my $idx ( @$indexes ) {
    next if !defined $a->[$idx];
    return 0 if $a->[$idx] ne $b->[$idx] || $a->[$idx+1] ne $b->[$idx+1];
}

return 1;

在没有无效的情况下，这是40%的性能提升。你得到的越多，你的固定集中的空数就越多。

use strict;
use warnings;
use v5.10;  # for state

# Compute the indexes of a list of pairs which are interesting for
# comparison: those with defined keys.
sub precompute_indexes {
    my $pairs = shift;

    die "Unbalanced pairs" if @$pairs % 2 != 0;

    my @indexes;
    for( my $idx = 0; $idx <= $#$pairs; $idx += 2 ) {
         push @indexes, $idx if defined $pairs->[$idx];
     }

    return \@indexes;
}

sub cmp_pairs_ignore_null_keys {
    my($a, $b) = @_;

    # state is like my but it will only evaluate once ever.
    # It acts like a cache which initializes the first time the
    # program is run.
    state $indexes = precompute_indexes($b);

    # If they don't have the same # of elements, they can never match.
    return 0 if @$a != @$b;

    for my $idx ( @$indexes ) {
        next if !defined $a->[$idx];
        return 0 if $a->[$idx] ne $b->[$idx] || $a->[$idx+1] ne $b->[$idx+1];
    }

    return 1;
}

我仍然相信，在SQL中使用自联接更好，但还没有解决这个问题。