3

重複の可能性:
Perl では、2 つの配列が等しいかどうかを比較する方法が組み込まれていますか?

配列を返す関数と比較する必要があります。

  • ペアごとに比較したときにすべての要素が等しい場合は true
  • ペアごとに比較したときに、すべての要素が等しいか、最初の配列の要素が未定義の場合は true
  • その他の場合はすべて false

つまり、サブが「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

明らかな解決策は、2 つの配列間でペア単位の比較を行うことですが、比較は配列の大規模なセットに対して複数回実行されるため、配列には多くの要素が含まれる可能性があるため、それよりも高速にしたいと考えています。

一方、比較される配列の内容 (つまり、可能なすべての @b) は事前に決定されており、変更されません。配列の要素には固定長がなく、含まれる可能性のある文字 (タブ、コンマなど) に関する保証はありません。

ペアごとの比較よりもこれを行うためのより速い方法はありますか? スマート マッチは、すべての要素が等しい場合に true を返すため、それをカットしません (したがって、1 つが undef の場合はそうではありません)。

パッキングしてビットごとの比較を行うことは戦略になるでしょうか? pack/unpack と vec のドキュメントを参照すると有望に見えますが、私はそこに少し深みがあります。

ありがとう。

4

1 に答える 1

2

Perl は、私の Macbook で約 100 ミリ秒で 10,000 個のペアワイズ要素のリストを比較できるので、最初に言うことは、コードをプロファイリングして、これが実際に問題であることを確認することです。

いくつかのベンチマークを実行すると、速度を上げるためにできることがいくつかあります。

  • 一致する最初の失敗で保釈するようにしてください。

一致しない比較がたくさんあると仮定すると、これにより時間が大幅に節約されます。

  • 配列が同じ長さであることを事前に確認してください。

それらの配列が同じ長さでない場合、一致することはありません。サイズを比較し、異なる場合は早めに返品してください。これにより、ループ内でこのケースを何度もチェックする必要がなくなります。

  • C スタイルの for ループの代わりに反復子を使用します。

ペアごとに反復すると、通常は次のようになりますfor( my $idx = 0; $idx <= $#a; $idx += 2 )が、配列の反復は、C スタイルの for ループを使用するよりも高速です。これは Perl の最適化トリックであり、Perl コードで行うよりも最適化された C で 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;
  • 興味深いインデックスを事前に計算します。

ペアの 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;

Null がない場合、パフォーマンスが 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 で行う方がよいと確信していますが、うまくいきませんでした。

于 2012-11-02T18:00:04.860 に答える