Perl Hackers Hub
第55回 Perlコードの高速化―文字列処理の時間短縮とデータ構造の効率化(3)
データ構造
本節では,
ある値が一覧に含まれるかはexists()を使う
ある文字列が一覧で定義した文字列と一致するかどうかを確認することは多いでしょう。たとえば,
次のコードでは,Reply-To
ヘッダが一覧に含まれることの確認方法を,grep()
関数と,exists()
関数で比べたものです。
grep-list-vs-exists-hash.
my $A = ['From', 'Reply-To', 'To'];
my $H = {'From' => 1, 'Reply-To' => 1, 'To' => 1};
sub usegrep {
my $v = 'Reply-To';
return 1 if grep { $v eq $_ } @$A;
}
sub hashkey {
my $v = 'Reply-To';
return 1 if exists $H->{ $v };
}
考察:exists()がgrep()に快勝
表6に示すとおり,
表6 ある値が一覧に含まれるかの確認の比較
比較項目 | 秒間実行回数 | 速度比 |
---|---|---|
grep() | 2,166,065 | 1. |
exists() | 4,137,931 | 1. |
では,grep-list-vs-exists-hash-100.
に,exists()
関数でハッシュのキーを調べる方法が20倍ほど高速でした。
このように大きな差が生まれる理由は,grep()
関数exists()
関数でハッシュのキーを確認する方法は計算量がO(1)です。つまり,
さて,Devel::Size
モジュールを使うと,total_
で計測したメモリサイズは,$A
が214バイト,$H
が380バイトでした。表7に示すとおり,
表7 配列とハッシュの大きさの比較
要素数 | 配列 | ハッシュ | サイズ比 |
---|---|---|---|
100 | 7. | 10. | 1. |
10,000 | 781. | 1. | 1. |
1,000,000 | 76. | 102. | 1. |
- 注2)
foreach
で丁寧に回しても同じです。
要素数の少ないデータには配列を使う
前項のベンチマークでは配列よりもハッシュのキーが圧倒的に速かったため,
たとえばPerlのコアモジュールであるTime::Piece
は内部で日付データを配列として保持
次のコードは,Final-Recipient:
の3要素を配列とハッシュで定義し,Final-Recipient:neko@nyaan.
となるコードを,
array-vs-hash.
my $A = ['final-recipient', 'rfc822', 'neko@nyaan.jp'];
my $H = {
'field' => 'final-recipient',
'type' => 'rfc822',
'value' => 'neko@nyaan.jp'
};
sub ar { return $A->[0].': '.$A->[2] }
sub hs { return $H->{'field'}.': '.$H->{'value'} }
考察:配列がハッシュに快勝
表8に示すとおり,
表8 少ない要素数の配列とハッシュの比較
比較項目 | 秒間実行回数 | 速度比 |
---|---|---|
ハッシュ | 4,761,905 | 1. |
配列 | 6,185,567 | 1. |
- 注3)
- 配列の最初は秒,
2番目は分, 3番目は時の順序で, そしてn番目が何であるかを別の定数で保持しています。
エラーメッセージの照合には配列を使う
バウンスメールに現れるエラーメッセージは多種多様です。メールサーバソフトウェアごと,
次のコードは,x
修飾子grep()
関数とindex()
関数で,
check-smtp-error-message.
my $Fa = 'Delivery failed, blacklisted by rbl';
my $Re = qr{(?>
access[ ]denied[.][ ]ip[ ]name[ ]lookup[ ]failed
|... # エラーメッセージパターンの正規表現がいくつか
|blacklisted[ ]by
)
}x;
my $Ar = [
'access denied. ip name lookup failed',
..., # エラーメッセージ文字列がいくつか
'blacklisted by',
];
sub regex { return 1 if $Fa =~ $Re } # 正規表現で照合
sub grep1 {
# 配列に対するgrep()で照合
return 1 if grep { index($Fa, $_) > -1 } @$Ar;
}
考察:配列に対するgrep()が正規表現に圧勝
表9に示すとおり,grep()
関数で回してindex()
関数で照合するほうが,
表9 エラーメッセージの照合の比較
比較項目 | 秒間実行回数 | 速度比 |
---|---|---|
正規表現 | 545,455 | 1. |
配列に対するgrep( ) | 1,463,415 | 2. |
正規表現と配列,Devel::Size
モジュールのtotal_
で計測したメモリサイズは,$Re
は216バイト,$Ar
は457バイトでした。メモリ使用量は2倍以上の差ですが,
- 注4)
- 正規表現内の空白や改行を無視する動作になり,
列挙したパターンが読みやすくなります。
配列の末尾を参照するには負の添え字を使う
本項は,$#
配列名よりも,
次のコードは,$#
配列名を使った例と負の添え字を使った例で,1
から100
までの数字を入れた配列に対して,100
)99
)
dollar-sharp-vs-negative-index.
my @A = (1..100);
sub ds { return ($A[$#A] + $A[$#A - 1]) }
sub ni { return ($A[-1] + $A[-2]) }
考察:負の添え字が$#
に楽勝
表10のように,$v[-1]
と書きましょう。
表10 負の添え字と$#配列名の比較
比較項目 | 秒間実行回数 | 速度比 |
---|---|---|
$v[$#] | 4,838,710 | 1. |
$v[-1] | 10,909,091 | 2. |
ループ処理にはforeachを使う
本項も前項と同じく,for
とforeac
hとwhile
の3つの選択肢を比べましょう。
次のコードでは,1
から256
までの数字を要素に持つ配列から,for
foreach
とwhile
を比較します。
for-vs-foreach-vs-while.
sub loop1f {
my $v = 0;
my @p = (1..256);
for( my $e = 0; $e < 256; $e++ ) {
$v++ if $p[$e] % 2 == 0;
}
return $v;
}
sub loop2e {
my $v = 0;
my @p = (1..256);
foreach my $e ( @p ) {
$v++ if $e % 2 == 0;
}
return $v;
}
sub loop3w {
my $v = 0;
my @p = (1..256);
while( my $e = shift @p ) {
$v++ if $e % 2 == 0;
}
return $v;
}
考察:foreach
がwhile
とC形式のfor
に快勝
表11に示すとおり,foreach
の一強となりました。while
はイテレータが返す値を取り回すのにも使用しますが,for
はめったに必要となりませんので,foreach
の一択でしょう。
表11 ループの比較
比較項目 | 秒間実行回数 | 速度比 |
---|---|---|
while | 23,202 | 1. |
for | 29,326 | 1. |
foreach | 37,594 | 1. |
しかし,while
をforeach
に書き換えられるとは限りません。while
ではshift()
関数で代入時に偽となっていたコードが,foreach
では偽とならないケースがあります。詳しくは,fails-onforeach-loop.
で確認してください。このような落とし穴もありますので,
- 注5)
- 添え字を伴うfor文です。
全体の性能を測るプロファイリング
ここまで紹介した例のとおり,Benchmark
モジュールでのベンチマークは部分としてのコードを競わせるものです。部分的に高速であるからと言って,
筆者は,Devel::NYTProf
モジュールを使ってプロファイリングをしたうえで,
nytprofhtmlで結果を見やすくする
Devel::NYTProf
モジュールが出力するnytprof.
はバイナリファイルですので,nytprofhtml
コマンドを実行すると作られるnytprof/
をブラウザで開き,
プロファイリング用Makefile
とはいえ,profile
ターゲットを定義して,makeprofile
を実行するだけで完了するようにしています。
プロファイリング用のMakefile
CODE := 'Sisimai->make(shift, delivered => 1)'
MAIL := tmp/emails-for-speed-test
profile:
perl -d:NYTProf -Ilib -MSisimai -lE $(CODE) $(MAIL)
nytprofhtml
プロファイリング結果の検証
図1はwhile
を,for
for
while
部分でも全体でもfor
がwhile
に勝るので,
- 注1)
- C形式ではないforはforeachと同じ動作をします。
まとめ
インフラを触るときの戒め
実際,master
ブランチで,
ただし,
なお,
さて,
本誌最新号をチェック!
WEB+DB PRESS Vol.122
2021年4月24日発売
B5判/168ページ
定価1,628円
(本体1,480円+税10%)
ISBN978-4-297-12119-8
- 特集1
上から下まで全レイヤ解説! 複雑化した世界を体系的に学ぶ
Web技術総整理 - 特集2
新バージョン登場! PythonによるWeb開発の基本
はじめてのDjango - 特集3
Rustで実装!
作って学ぶRDBMSのしくみ
バックナンバー
Perl Hackers Hub
- 第66回 モジュールによる時間の多様な取り扱い(2)
- 第66回 モジュールによる時間の多様な取り扱い(1)
- 第65回 依存モジュールの更新 ―update-cpanfile,GitHub Actionsで実現!(2)
- 第65回 依存モジュールの更新 ―update-cpanfile,GitHub Actionsで実現!(1)
- 第64回 少しマニアックなPerlのテクニック―特殊変数,低レベルの標準関数を使いこなす(2)
- 第64回 少しマニアックなPerlのテクニック―特殊変数,低レベルの標準関数を使いこなす(1)
- 第63回 PPIとPerl::Tidyを組み合わせて作るコード整形ツール(2)
- 第63回 PPIとPerl::Tidyを組み合わせて作るコード整形ツール(1)
- 第62回 Perl歴史散策 ―インタプリタの実装と,構文の進化をたどる(3)
- 第62回 Perl歴史散策 ―インタプリタの実装と,構文の進化をたどる(2)