Perl Hackers Hub

第55回Perlコードの高速化―文字列処理の時間短縮とデータ構造の効率化(2)

前回の(1)こちらから。

文字列

まず紹介するのは文字列処理です。

文字列処理には、Perlの武器である正規表現が欠かせません。正規表現の記述ルールが手に馴染んでくると、文字列の照合や取り出し、書き換えにはまず正規表現を使うでしょう。しかし、正規表現で書いた処理には、組込み関数や演算子を使って書き換えられるものがいくつかあります。そして、多くの場合では関数や演算子を使った処理のほうが高速です。

本節では、正規表現を使った処理を関数や演算子で置き換える例を紹介します。

特定文字の削除にはy///を使う

不要な文字や、行末の改行コード\n⁠、タブ文字\tなどを空白文字に置き換える処理(削除)は、頻繁に行うものでしょう。特定文字を削除するときに最も使うのが置換演算子です。

たとえばメールアドレスは<neko@nyaan.jp>のように<>で囲まれた形式で現れることがあります。SMTPSimple Mail Transfer Protocolでは必要な<>ですが、メールアドレスだけが欲しいときは不要です。

次のコードは、これらを削除(空文字に置換)する方法を、正規表現の文字クラスを使う置換演算子s///と、同じく置換演算子y///とで比べた例です。

s-vs-y.pl
my $Email = '<neko@nyaan.jp>'; # < と > を削除したい
sub ss {
    my $v = $Email;
    $v =~ s/[<>]//g; # 正規表現の文字クラス
    return $v;
}
sub yy {
    my $v = $Email;
    $v =~ y/<>//d; # 置換対象を1文字単位で列挙
    return $v;
}

考察:y///s///に圧勝

表1に示すとおり、そしてperlperf - Perlの性能と最適化のテクニック - perldoc.jpでも言及されているとおり、y///置換演算子が圧倒的に速い結果となりました。保守性につながる読みやすさも損なわれていませんし、4.6倍も速いなら、y///を使った文字単位での置換が処理時間の短縮となります。

表1 特定文字の削除の比較
比較項目秒間実行回数速度比
s///895,5221.00
y///4,137,9314.62

先頭文字の確認にはindex()を使う

HTTPと同様にSMTPでもステータスコードの200番台は成功を、400番台と500番台はエラーを表します。接続先の応答が成功か失敗かは、まずステータスコードの先頭1文字を見てエラー判定を行い、そのあとでステータスコードの残り2桁やエラーメッセージの詳細を確認します。

次のコードは、SMTP応答コードの先頭1文字が45であることを、正規表現の文字クラスを使った方法と、index()関数を使った方法で比較したものです。

check-the-first-character.pl
my $Status = '550';
sub regexp { return 1 if $Status =~ /\A[45]/ }
sub index2 {
    # 4が文字列の先頭なら位置が0になる
    return 1 if index($Status, '4') == 0;

    # 5が文字列の先頭なら位置が0になる
    return 1 if index($Status, '5') == 0;
}

考察:index()が正規表現に辛勝

index()関数は2回も実行されていますが、表2に示すとおりindex2サブルーチンのほうがやや高速に動作します。逆に考えると、関数に比べて正規表現は実行時間が長くなります。1.1倍程度の差ですが、ループ内で何度も呼ばれるコードであれば、このわずかな差が大きな差となってくるでしょう。

表2 先頭1文字の確認の比較
比較項目秒間実行回数速度比
\A[45]4,411,7651.00
index( )5,000,0001.13

文字列の先頭/末尾の確認にはindex()とsubstr()を使う

メールアドレスをユーザー名やログインIDとして使っているWebサービスでは、入力された文字列がメールアドレスであることを確認するコードが動いていることでしょう。ここでは、ある文字列をメールアドレスと判定する簡易なコードを比較します。

次のコードは、ベンチマークを目的とした簡易なメールアドレス判定コードです。各サブルーチンは、<で始まり@を含み>で終わる文字列をメールアドレスとみなします。これを、正規表現と、2回のindex()関数、substr()関数の併用で比べます。

is-email-address-or-not.pl
my $Email = '<neko@nyaan.jp>';
sub regexp { return 1 if $Email =~ /\A<.*@.*>\z/ }
sub indexs {
    # index()とsubstr()
    if( index($Email, '<') == 0 && # 先頭文字が<
        index($Email, '@') > -1 && # 文字列に@を含む
        substr($Email, -1, 1) eq '>' ) { # 末尾文字が>
        return 1
    }
}

考察:index()とsubstr()組が正規表現に快勝

表3に示すとおり、1つの正規表現よりも、2回のindex()関数と1回のsubstr()関数のほうが1.8倍ほど高速でした。しかし、サブルーチンindexsのコードは少し長くて読みにくいように思えます。

「速いは正義」と先述しましたが、読みにくくなる場合は一考の余地があります。一度しか実行されないコードであれば読みやすさを優先、何千回も実行されるコードであれば速度を優先するといった、背景に合わせた判断が必要でしょう。

表3 文字列の先頭/末尾の確認の比較
比較項目秒間実行回数速度比
正規表現2,068,9661.00
index( )、substr( )3,658,5371.77

文字列の比較にはlc()を使う

大文字と小文字が入り混じった文字列を比較するとき、みなさんはどのようなコードを書いているでしょうか。筆者は、lc()関数で小文字に変換してから比較する方法と、正規表現を使う方法の2通りが真っ先に思い浮かびます。正規表現を使う場合も、大文字と小文字を区別しないi修飾子を用いるか、大文字か小文字かを断定できない箇所だけを文字クラスで記述するかの2通りがあります。

実例で挙げるのはメールアドレスです。ほとんどのメール関連ソフトウェアの実装は、メールアドレスの大文字と小文字を区別しません。バウンスメールでは、ローカルパート[1]Mailer-Daemonmailer-daemonのような表記をよく見かけるでしょう。

次のコードは、ローカルパートがmailer-daemon(大文字が混在する表記も含む)であるかどうかの確認を行う方法を、i修飾子を指定した正規表現、文字クラスを使った正規表現、小文字に変換するlc()関数とで比べた例です。

lc-vs-i-modifier-vs-char-class.pl
my $Text = 'Mailer-Daemon';
sub regex1 {
    # /正規表現/i(大文字/小文字の区別なし)
    return 1 if $Text =~ /\Amailer-daemon\z/i;
}
sub regex2 {
    # 文字クラスを使う正規表現(MとDだけ大文字を考慮)
    return 1 if $Text =~ /\A[Mm]ailer-[Dd]aemon\z/;
}
sub lcfunc {
    # lc()関数 (小文字にしてから比較)
    return 1 if lc $Text eq 'mailer-daemon';
}

考察:lc()が正規表現に圧勝

表4に示すとおり、i修飾子を使う正規表現と、文字クラスを使う正規表現は僅差でしたが、いったんlc()関数で小文字に変換してから比較するlcfuncサブルーチンは、正規表現双方の2.3倍も速く動作しました。読みやすさも向上しており、速度と保守性が両立する例です。

表4 文字列の比較の比較
比較項目秒間実行回数速度比
/正規表現/i2,752,2941.00
文字クラス2,857,1431.04
lc( )6,451,6132.34

そして、先頭文字の確認でindex()関数が正規表現よりも速かったのと同様、関数は正規表現よりも速く動作します。逆に、いま関数を使っているコードを正規表現に書き換えると、遅くなる可能性が高いでしょう。

メタ文字を含む正規表現は読みやすいものを使う

.+などの正規表現で特別な意味を持つメタ文字を、文字そのものとして一致させたい場合に考えられる書き方の比較です。たとえばURLやメールアドレスに現れるホスト名やドメイン名の照合で.を扱うときにどう書くか、です。

次のコードでは、メールアドレスのドメイン部分に含まれるメタ文字を\.とエスケープするか、文字クラスを使って[.]と表現するか、あるいは/\Q...\E/とメタ文字を無効にするエスケープシーケンスを使うか、を比べます。

escape-vs-char-class-vs-qe.pl
my $Email = 'kijitora@neko.nyaan.jp';
sub bs { return 1 if $Email =~ /neko\.nyaan\.jp/ }
sub cc { return 1 if $Email =~ /neko[.]nyaan[.]jp/ }
sub qe { return 1 if $Email =~ /\Qneko.nyaan.jp\E/ }

考察:実力伯仲

表5に示すとおり、正規表現の書き方としては、それぞれのコードに大差はありませんでした。ただし、大差がなかったからベンチマークが無駄であったとは言えません。差がないことも結果の一つで、どれを選択してもよいから読みやすいコードを採用する、と判断ができます。

表5 メタ文字のエスケープの比較
比較項目秒間実行回数速度比
\エスケープ5,042,0171.00
文字クラス5,217,3911.03
\Q\E5,263,1581.04

読みやすさには多少の個人差がありますが、\でメタ文字をエスケープする表記を好まない筆者は、文字列全体を\Q\Eで挟むのが最も読みやすいと思います。

データ構造

本節では、主に複数の文字列を保持するデータ構造について、配列を中心に比較します。前節では文字列単体の照合や書き換えを行っていましたが、複数の文字列を扱う場合は、どのようなデータ構造を使うのが高速か、効率的かについてベンチマークを取ります。

ある値が一覧に含まれるかはexists()を使う

ある文字列が一覧で定義した文字列と一致するかどうかを確認することは多いでしょう。たとえば、ドロップダウンリストから選択された値が有効であることや、URLやメールアドレスのドメイン部分が自社保有のドメイン名であることを検査する、などです。

次のコードでは、メールのReply-Toヘッダが一覧に含まれることの確認方法を、メールヘッダ名を要素として持つ配列に対するgrep()関数と、キーとして持つハッシュに対するexists()関数で比べたものです。

grep-list-vs-exists-hash.pl
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に示すとおり、ハッシュのキーとしてデータを持つほうが1.8倍も高速でした。

表6 ある値が一覧に含まれるかの確認の比較
比較項目秒間実行回数速度比
grep()2,166,0651.00
exists()4,137,9311.80

では、要素数がもっと多い場合はどうでしょうか。誌面には掲載していませんが、本誌サポートサイトで配布するサンプルコードのgrep-list-vs-exists-hash-100.plに、要素数を100個にした場合のベンチマークを載せています。100要素の場合はさらに大差となり、exists()関数でハッシュのキーを調べる方法が20倍ほど高速でした。

このように大きな差が生まれる理由は、計算量の違いによるものです。ソートされていない配列に対するgrep()関数[2]計算量はO(n)です。つまり、入力データnの量に比例して計算時間が増えます。一方、exists()関数でハッシュのキーを確認する方法は計算量がO(1)です。つまり、ハッシュのサイズに関係なく計算量は一定です。よって、データ量が多ければ多いほど、要素の一覧をハッシュのキーとして持つほうが高速になります。

さて、配列とハッシュで異なるデータ構造の比較ですので、それぞれのメモリ使用量も確認しましょう。メモリ使用量は、変数が使用しているメモリサイズを調べるDevel::Sizeモジュールを使うと、バイト単位で得られます。同モジュールのtotal_sizeで計測したメモリサイズは、配列$Aが214バイト、ハッシュ$Hが380バイトでした。表7に示すとおり、ハッシュは配列に比べメモリ使用量が1.3倍程度です。このくらいの増加であれば、ハッシュを使うほうが速度面での利点が大きく、効率的でしょう。

表7 配列とハッシュの大きさの比較
要素数配列ハッシュサイズ比(ハッシュ/配列)
1007.8KB10.3KB1.32
10,000781.2KB1.07MB1.38
1,000,00076.3MB102.3MB1.34

要素数の少ないデータには配列を使う

前項のベンチマークでは配列よりもハッシュのキーが圧倒的に速かったため、配列は使いどころがない印象を持つかもしれませんが、そうではありません。適材適所です。

たとえばPerlのコアモジュールであるTime::Pieceは内部で日付データを配列として保持[3]しているとおり、要素数が少ないデータを保持するには配列のほうが高速です。

次のコードは、バウンスメールに現れる、送信できなかった宛先を示す項目Final-Recipient:の3要素を配列とハッシュで定義し、戻り値がFinal-Recipient:neko@nyaan.jpとなるコードを、それぞれ比べたものです。

array-vs-hash.pl
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に示すとおり、配列が1.3倍高速でした。いずれの計算量もO(1)なので大差はつきませんが、要素数が少なく、ほとんど変更がなく、何度も参照される変数ならば、配列として保持する選択は効率面からしても十分検討に値するでしょう。

表8 少ない要素数の配列とハッシュの比較
比較項目秒間実行回数速度比
ハッシュ4,761,9051.00
配列6,185,5671.30

エラーメッセージの照合には配列を使う

バウンスメールに現れるエラーメッセージは多種多様です。メールサーバソフトウェアごと、メールサービスごと、そしてエラーの種類ごとに、エラーメッセージのパターンが種々雑多に存在します。

次のコードは、あるエラーメッセージがSMTP接続時に拒否されたものであるかどうかを、配列とx修飾子[4]指定の正規表現で比較したものです。前者は複数のエラーメッセージを文字列として保持する配列に対するgrep()関数とindex()関数で、後者はパターンとして保持する正規表現に対する照合で比べています。

check-smtp-error-message.pl
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()関数で照合するほうが、正規表現より2.7倍も高速でした。ただし、これは多くが固定文字列で構成される正規表現であったからこそ、配列に書き換えられた一例です。数値や文字を範囲としてとらえる必要があるなら、正規表現を使わないのは非効率的です。

表9 エラーメッセージの照合の比較
比較項目秒間実行回数速度比
正規表現545,4551.00
配列に対するgrep( )1,463,4152.68

正規表現と配列、まったく違うデータ構造を比較していますので、メモリの使用量も見てみましょう。Devel::Sizeモジュールのtotal_sizeで計測したメモリサイズは、正規表現$Reは216バイト、配列$Arは457バイトでした。メモリ使用量は2倍以上の差ですが、定数のように扱われる変数であり、プログラム全体が使うメモリ量からすると誤差の範囲です。そして読みやすさも向上しています。この例は、速度と保守性が両立する有用な書き換えだと筆者は考えます。

配列の末尾を参照するには負の添え字を使う

本項は、本節の主題であるデータ構造の比較ではありませんが、すべてのベンチマークで登場した配列について触れます。配列の末尾の要素を参照する方法は、配列の最後の添え字を得る$#配列名よりも、負の添え字を使うほうが速いと広く知られていますが、どの程度の差があるのかを確認するためにも紹介します。

次のコードは、$#配列名を使った例と負の添え字を使った例で、1から100までの数字を入れた配列に対して、それぞれ配列の末尾の値100と、末尾から2番目の値99を足して返すサブルーチンで比較します。

dollar-sharp-vs-negative-index.pl
my @A = (1..100);
sub ds { return ($A[$#A] + $A[$#A - 1]) }
sub ni { return ($A[-1] + $A[-2]) }

考察:負の添え字が$#に楽勝

表10のように、やはり負の添え字を使ったほうが高速でした。2倍以上の差がありますし、記号の連続よりも読みやすい表記であることから、配列の末尾を参照するには負の添え字で$v[-1]と書きましょう。

表10 負の添え字と$#配列名の比較
比較項目秒間実行回数速度比
$v[$#]4,838,7101.00
$v[-1]10,909,0912.25

ループ処理にはforeachを使う

本項も前項と同じく、配列を扱います。配列をループで回す方法として、forforeachとwhileの3つの選択肢を比べましょう。

次のコードでは、1から256までの数字を要素に持つ配列から、偶数である要素数を数えるコードを例に、C形式のfor[5]とイテレータとして動作するforeachwhileを比較します。

for-vs-foreach-vs-while.pl
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;
}

考察:foreachwhileとC形式のforに快勝

表11に示すとおり、結果はforeachの一強となりました。whileはイテレータが返す値を取り回すのにも使用しますが、C形式のforはめったに必要となりませんので、1.6倍も速いforeachの一択でしょう。

表11 ループの比較
比較項目秒間実行回数速度比
while23,2021.00
for29,3261.26
foreach37,5941.62

しかし、高速化を理由として常にwhileforeachに書き換えられるとは限りません。whileではshift()関数で代入時に偽となっていたコードが、foreachでは偽とならないケースがあります。詳しくは、本誌サポートサイトで配布するサンプルコードfails-onforeach-loop.plで確認してください。このような落とし穴もありますので、ループを書き換える場合は周辺のロジックも含めて確認、測定、変更が必要です。

<続きの(3)こちら。>

WEB+DB PRESS

本誌最新号をチェック!
WEB+DB PRESS Vol.130

2022年8月24日発売
B5判/168ページ
定価1,628円
(本体1,480円+税10%)
ISBN978-4-297-13000-8

  • 特集1
    イミュータブルデータモデルで始める
    実践データモデリング
  • 特集2
    いまはじめるFlutter
    iOS/Android両対応アプリを開発してみよう
  • 特集3
    ブロックチェーン、スマートコントラクト、NFT
    作って学ぶWeb3

おすすめ記事

記事・ニュース一覧