北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

Perlの正規表現のパフォーマンス上の弱点

Perl使いと言えば正規表現ではありますが。


こんな記事を見つけたわけです。

Notice that Perl requires over sixty seconds to match a 29-character string.
Regular Expression Matching Can Be Simple And Fast

たかだか29文字のマッチで1分もかかるだって!? 今までの自分の常識にはなかったので愕然としました。早速実際にやってみて調査。

% date; perl -e '"nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn" =~ /n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?n?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn/;'; date
200849日 水曜日 122357秒 JST
200849日 水曜日 122617秒 JST

うあ、30文字で3分かかってる。書いてあることはほんとだったみたいですね。


ちなみに、これはあくまでも特殊ケースです。左辺のマッチング対象の文字列を60文字にしてあげれば、この評価は一瞬で終わります*1

*1:「?」の可能性を検証する回数が減るからでしょう。これが増えれば指数関数的に時間が増加するんじゃないかと。