はじめに
言語別：パスワード向けの正規表現 で議論をしているうちに、バックトラックについての疑問がわいてきたので、ここで実際に調査してみることにします。
ベンチマーク
「文字列 ~ 正規表現 (最長一致の基本形)」の見出しとします。
Case 1: "aaa...aaa" ~ /\Aa+a\z/
最短一致と最長一致を比較する際に用いられる典型的な例です。このケースはマッチ成功を期待します。
予想
- 最短一致は、1回ごとに後ろとマッチするかどうかを検証するので遅い。
- 最長一致は、末尾まで消費した後1回のバックトラックでマッチするので速い。
- 独占的量指定子付き最長一致は、最長一致と速度は同等だがマッチしない。
結果
<?php
$try = 10000;
$length = 100000;
$patterns = [
'最短一致' => '/\Aa+?a\z/',
'最長一致' => '/\Aa+a\z/',
'独占的量指定子付き最長一致' => '/\Aa++a\z/',
];
$string = str_repeat('a', $length);
$sum = array_fill_keys(array_keys($patterns), 0.0);
for ($i = 0; $i < $try; ++$i) {
foreach ($patterns as $key => $pattern) {
$a = microtime(true);
preg_match($pattern, $string);
$b = microtime(true);
$sum[$key] += $b - $a;
}
}
print_r(array_map(
function ($i) use ($try) { return sprintf('%.5f sec', $i); },
$sum
));
/*
Array
(
[最短一致] => 2.77713 sec
[最長一致] => 0.72023 sec
[独占的量指定子付き最長一致] => 0.71401 sec
)
*/
予想通りです。
Case 2: "aaa...aaa" ~ /\Aa+a\A/
\zを\Aに変えてみました。このケースはマッチ失敗を期待します。
予想
- 最短一致は、1回ごとに後ろとマッチするかどうかを検証するので遅い。
- 最長一致は、末尾まで消費した後先頭までバックトラックを行うので非常に遅い。
- 独占的量指定子付き最長一致は、末尾まで消費した後バックトラックを行わないので速い。
結果
<?php
$try = 10000;
$length = 100000;
$patterns = [
'最短一致' => '/\Aa+?a\A/',
'最長一致' => '/\Aa+a\A/',
'独占的量指定子付き最長一致' => '/\Aa++a\A/',
];
$string = str_repeat('a', $length);
$sum = array_fill_keys(array_keys($patterns), 0.0);
for ($i = 0; $i < $try; ++$i) {
foreach ($patterns as $key => $pattern) {
$a = microtime(true);
preg_match($pattern, $string);
$b = microtime(true);
$sum[$key] += $b - $a;
}
}
print_r(array_map(
function ($i) use ($try) { return sprintf('%.5f sec', $i); },
$sum
));
/*
Array
(
[最短一致] => 2.72884 sec
[最長一致] => 3.40929 sec
[独占的量指定子付き最長一致] => 0.69334 sec
)
*/
これも予想通りですね。
Case 3: "aaa...aaa" ~ /\Aa+b\z/
今度は末尾をb\zとしてみます。このケースはマッチ失敗を期待します。
予想
Case 2 と同様。
結果
<?php
$try = 10000;
$length = 100000;
$patterns = [
'最短一致' => '/\Aa+?b\z/',
'最長一致' => '/\Aa+b\z/',
'独占的量指定子付き最長一致' => '/\Aa++b\z/',
];
$string = str_repeat('a', $length);
$sum = array_fill_keys(array_keys($patterns), 0.0);
for ($i = 0; $i < $try; ++$i) {
foreach ($patterns as $key => $pattern) {
$a = microtime(true);
preg_match($pattern, $string);
$b = microtime(true);
$sum[$key] += $b - $a;
}
}
print_r(array_map(
function ($i) use ($try) { return sprintf('%.5f sec', $i); },
$sum
));
/*
Array
(
[最短一致] => 0.70907 sec
[最長一致] => 0.70840 sec
[独占的量指定子付き最長一致] => 0.70872 sec
)
*/
おっと、これはちょっと予想外です。言明の場合は何も考えずバックトラックを行ってしまうようですが、単なる1文字が明らかにマッチしない場合はバックトラックを行わないという賢明な判断を下してくれるようです。
Case 4: "aaa...aaa" ~ /\Aa+(?=b\z)/
先ほどの考察を実証するため、"懸命な判断" をさせないように無理矢理該当箇所を言明にしてしまいましょう。このケースはマッチ失敗を期待します。
予想
Case 2 と同様。
結果
<?php
$try = 10000;
$length = 100000;
$patterns = [
'最短一致' => '/\Aa+?(?=b\z)/',
'最長一致' => '/\Aa+(?=b\z)/',
'独占的量指定子付き最長一致' => '/\Aa++(?=b\z)/',
];
$string = str_repeat('a', $length);
$sum = array_fill_keys(array_keys($patterns), 0.0);
for ($i = 0; $i < $try; ++$i) {
foreach ($patterns as $key => $pattern) {
$a = microtime(true);
preg_match($pattern, $string);
$b = microtime(true);
$sum[$key] += $b - $a;
}
}
print_r(array_map(
function ($i) use ($try) { return sprintf('%.5f sec', $i); },
$sum
));
/*
Array
(
[最短一致] => 2.79401 sec
[最長一致] => 3.47638 sec
[独占的量指定子付き最長一致] => 0.68388 sec
)
*/
言明での嫌がらせ大成功。
結論
を出すにはまだまだ検証不足だと思うので、編集リクエストやコメントでの提案などお待ちしております。