Perlコードを最適化する

投稿日:2019年04月14日 18時25分58秒

やっと修羅場が終わったので覚えているうちに投稿します。
今回Perlのお仕事をしたのですがインタープリター故に強烈にボトルネックを生成する事があります。アルゴリズムで劇的に早くなることがあるのです。今回注目するのはpush,popです。配列に対して要素を追加、削除するのですがこれが強烈に遅い事に気が付きました。下記のソースはある2つの配列について差分を取るものですが書き方で速度がずいぶん違います。

#!C:/Perl/bin/perl
use strict ;
use Data::Dumper;
use DateTime;
my @array_a;
my @array_b;
my @array_c;
my $t_before;
my $t_after;
my $t_offset;

#set array
for( my $i = 0 ; $i < 50000 ; $i++ ){
 push( @array_a , $i);
 push( @array_b , $i);
 }
 splice( @array_b, 1500, 1 );
 #push array version print "start\n";
 $t_before = time;
 @array_c = get_uniqItems1(\@array_a, \@array_b);
 print Dumper(@array_c);
 $t_after = time;
 $t_offset = $t_after - $t_before;
 my ($b_ss, $b_MM, $b_hh, $b_dd, $b_mm, $b_yy) = (localtime($t_before))[0..5];
 my ($a_ss, $a_MM, $a_hh, $a_dd, $a_mm, $a_yy) = (localtime($t_after))[0..5];
 $b_yy += 1900;
 $b_mm++;
 $a_yy += 1900;
 $a_mm++;
 print "$b_yy/$b_mm/$b_dd $b_hh:$b_MM:$b_ss\n";
 print "$a_yy/$a_mm/$a_dd $a_hh:$a_MM:$a_ss\n";
 print "$t_offset sec\n";
 #splice array version $t_before = time;
 @array_c = get_uniqItems2(\@array_a, \@array_b);
 print Dumper(@array_c);
 $t_after = time;
 $t_offset = $t_after - $t_before;
 ($b_ss, $b_MM, $b_hh, $b_dd, $b_mm, $b_yy) = (localtime($t_before))[0..5];
 ($a_ss, $a_MM, $a_hh, $a_dd, $a_mm, $a_yy) = (localtime($t_after))[0..5];
 $b_yy += 1900;
 $b_mm++;
 $a_yy += 1900;
 $a_mm++;
 print "$b_yy/$b_mm/$b_dd $b_hh:$b_MM:$b_ss\n";
 print "$a_yy/$a_mm/$a_dd $a_hh:$a_MM:$a_ss\n";
 print "$t_offset sec\n";
 print "end\n";
#----------------------------------------------------------------------- 
# Get list off deleted( or create) file 
#----------------------------------------------------------------------- 
sub get_uniqItems1{ my ($array, $arryB) = @_; my @arry = (); foreach my $a (@$array){ push @arry, $a; foreach my $b (@$arryB){ if( $a eq $b ){ pop @arry; } } } return @arry; } #----------------------------------------------------------------------- # Get list off deleted( or create) file #----------------------------------------------------------------------- sub get_uniqItems2 { my ($array, $arryB) = @_; my @arrayA = @$array; my @arryBB = @$arryB; my $i; my $j; for( $i = $#arrayA ; $i >= 0 ; $i-- ){
for( $j = $#arryBB ; $j >= 0 ; $j-- ){
if( $arrayA[$i] eq $arryBB[$j] ){
splice( @arrayA, $i, 1 );
splice( @arryBB, $j, 1 );
last;
}
}
}
return @arrayA ;
}

3_20131008_stack_push0

get_uniqItems1は空の結果用配列を用意して比較元配列から要素を一つ結果用配列にpushし、比較先配列を検索しその要素があればpopします。オーダーとしてはn*nの自乗の時間がかかるはずです。
get_uniqItems2は最初に比較元配列、比較先配列をコピーします。比較先配列と比較元配列から要素を2重ループで取り出し同じものがあれば両方の配列から削除します。それぞれの配列がユニークでなければうまく動きませんが、結果が恐ろしく違いがあります。
結果:

start
$VAR1 = 1500;
2014/6/14 15:24:28
2014/6/14 15:28:55
267 sec
$VAR1 = 1500;
2014/6/14 15:28:55
2014/6/14 15:28:55
0 sec
end

前者が4分以上かかってるのに後者は1秒もかかりません。おそらく500倍くらいは違うのではないかと思います。今回はほぼ同一のデータを元にしているので違いが大きくなりましたが、アルゴリズムで100倍以上違うというのは採用の価値があります。おそらく配列のコピーはシステムコールで実施され、spliceについてはデータ上に削除情報を記載するだけで実際の動的なデータ移動を伴わないのでしょう。
今回はPerlという言語での動作でしたがインタープリターでは実装によって大きく速度が違います。ループの中身を検討して最適化してみてはいかがでしょうか。

[<< ファイルの更新完了を検知する]

[Perlでデータを永続化する >>]