【php】正規表現ってそんなに負荷が高いの？（その３）

Tweet

Category php 2009/12/14

前回の恐ろしい正規表現をphpで試してみようとしたところ、予想した結果にならなかった。

phpの正規表現に関して、ある設定項目があって、デフォルトでは無茶な処理をさせないようになっていた（php5.2から）。php4でも、何かしらの制限に引っかかるようだ。

では、phpで無茶な正規表現を試す。

(.*)*^

最後に^（行頭）と書いてあるので、結果としてはどんな文字列にもマッチしないでマッチするのは行頭のみなのだが、マッチするまでにあらゆる組み合わせにトライするので、恐ろしく負荷が高い。

10文字から初めて、1文字ずつ増やしながら30文字まで、所要時間の計測と付随する情報の表示をする。

$t = time();
$s = '123456789012345678901234567890';
for ($i = 10; $i <= 30; ++$i) {
	$m = microtime(1) - $t;
	$c = preg_match('/(.*)*^/', substr($s, 0, $i));
	echo $i . '文字のとき： ';
	echo '所要時間 ' . (microtime(1) - $t - $m) . '秒、';
	echo 'マッチ回数 ' . $c . '回、';
	echo 'エラーコード ' . preg_last_error() . "\n";
}

結果

10文字のとき： 所要時間 0.000289916992188秒、マッチ回数 1回、エラーコード 0
11文字のとき： 所要時間 0.000504016876221秒、マッチ回数 1回、エラーコード 0
12文字のとき： 所要時間 0.00098705291748秒、マッチ回数 1回、エラーコード 0
13文字のとき： 所要時間 0.00196981430054秒、マッチ回数 1回、エラーコード 0
14文字のとき： 所要時間 0.00396609306335秒、マッチ回数 1回、エラーコード 0
15文字のとき： 所要時間 0.00479388237秒、マッチ回数 0回、エラーコード 2
16文字のとき： 所要時間 0.00493693351746秒、マッチ回数 0回、エラーコード 2
17文字のとき： 所要時間 0.00460386276245秒、マッチ回数 0回、エラーコード 2
………
……

順調に所要時間が倍々になっていると思ったら、15文字以降はすぐエラーで終了している。

エラーコード 2 は PREG_BACKTRACK_LIMIT_ERROR。バックトラック処理の回数制限に引っかかっている。
http://jp2.php.net/manual/ja/pcre.configuration.php#ini.pcre.backtrack-limit

バックトラック処理とは、「.* 」に該当する文字列を選び直して改めてマッチを試すという感じの処理のことのようです。preg_match(‘/1+19/’, ‘111119’)の1+を最初は1を5個とするとまずマッチせず、ではちょっとあきらめて1+を1を4個としたら、1が4個と1と9でマッチするといったぐあいです。

さて、偶然にも、しんどい試行錯誤的処理（バックトラック処理）に回数制限の安全装置が設けてあったわけですが、

ここで、わざと制限を大きくしてみます。次のコードを先頭に追加します。1億回まで試行錯誤を許可します。

ini_set('pcre.backtrack_limit', 100000000);

10文字のとき： 所要時間 0.000563144683838秒、マッチ回数 1回、エラーコード 0
11文字のとき： 所要時間 0.000984191894531秒、マッチ回数 1回、エラーコード 0
12文字のとき： 所要時間 0.00200200080872秒、マッチ回数 1回、エラーコード 0
13文字のとき： 所要時間 0.00407099723816秒、マッチ回数 1回、エラーコード 0
14文字のとき： 所要時間 0.00752210617065秒、マッチ回数 1回、エラーコード 0
15文字のとき： 所要時間 0.0153770446777秒、マッチ回数 1回、エラーコード 0
16文字のとき： 所要時間 0.0261600017548秒、マッチ回数 1回、エラーコード 0
17文字のとき： 所要時間 0.0308909416199秒、マッチ回数 1回、エラーコード 0
18文字のとき： 所要時間 0.0624001026154秒、マッチ回数 1回、エラーコード 0
19文字のとき： 所要時間 0.0882720947266秒、マッチ回数 1回、エラーコード 0
20文字のとき： 所要時間 0.164336919785秒、マッチ回数 1回、エラーコード 0
21文字のとき： 所要時間 0.325383901596秒、マッチ回数 1回、エラーコード 0
22文字のとき： 所要時間 0.65526509285秒、マッチ回数 1回、エラーコード 0
23文字のとき： 所要時間 1.30248498917秒、マッチ回数 1回、エラーコード 0
24文字のとき： 所要時間 2.55930399895秒、マッチ回数 1回、エラーコード 0
25文字のとき： 所要時間 3.08578515053秒、マッチ回数 0回、エラーコード 2
26文字のとき： 所要時間 3.04856085777秒、マッチ回数 0回、エラーコード 2
27文字のとき： 所要時間 3.05856990814秒、マッチ回数 0回、エラーコード 2
28文字のとき： 所要時間 3.04467487335秒、マッチ回数 0回、エラーコード 2
29文字のとき： 所要時間 3.050137043秒、マッチ回数 0回、エラーコード 2
30文字のとき： 所要時間 3.05758309364秒、マッチ回数 0回、エラーコード 2

何とか24文字まで処理できた。

処理できたのはいいですが、制限を大きくしてもいいことはないですね……やはりそもそもの問題として、こんな無茶な正規表現はやめるのが正しいと思います。

デフォルトで制限があるので、期待したのと違う結果が得られたら（途中でコケているようなら）、preg_last_error() などで原因を調査して、エラーが起きていたら、正規表現の方を見直すのがいいと思います。

おまけ）
phpのマニュアルには何か書いてないか探してみたら、あまり目立たないところにパフォーマンスについて書いてあって、同じような正規表現の例が出ていました。
http://jp2.php.net/manual/ja/regexp.reference.performances.php