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 で行う方がよいと確信していますが、うまくいきませんでした。