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
2008年 4月 9日 水曜日 12時23分57秒 JST
2008年 4月 9日 水曜日 12時26分17秒 JST

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

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

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