正規表現パート２ NFAエンジンの場合は、正規表現の磨き上げが必要？覚えていないと思うので・・・おさらいまずは、 DFA（テキスト主導型）エンジンバックトラックが持つ効率の悪さを回避する為に全ての可能性のあるマッチを同時に管理することによって、高速処理を実現するエンジン管理用のマップを作るため、場合により時間がかかり、メモリが必要になる語ると長いのでざっくりNFA NFA（正規表現主導型）エンジンバックトラックを根幹にもつエンジン＊POSIX NFA 最長のマッチを返さなくてはならない＊従来型NFA 正規表現主導型の性質を利用して、どのようなマッチを望むか性格に指定できる ※ 覚える必要はないですが・・・記憶のない人は、前回の資料を見て下さい。バックトラックと効率化バックトラック機能のあるNFAエンジンの場合選択肢が発生した場合、その位置に戻れるようぱんくずのように戻り位置を記録していく方法を採用している分かりにくいので例を次に示します。つまり斜めの線の→が入っている箇所が選択によるバックトラックが発生する位置バックトラックが多いですね。もしかして・・・バックトラック減らしたら効率化？こうしたら、バックトラック減らせる？減らせそうですが・・・どうでしょう？考えるべきこと変更によってメリットがあるか否かは以下を考える必要があります。エンジンの違いによって得られる効果は同じかこの変更が効果をはっきするのは、どんなときか結論１エンジンタイプによる効果のちがい POSIX NFAエンジンタイプこの変更による効果はほとんどありません。理由は、正規表現が方言できる全ての順列が試さ従来型NFA すぐにマッチに結びつくような選択肢の並べ方をすれば、最初のマッチが見つかったところで結論２マッチ結果による効果の違いこの変更によって処理がはやくなるのは、マッチが有る時だけに限られます。従来型NFAがマよって、最終的にマッチ不成功になったからには、全ての順列を試し済みなので、順番を変えまとめ NFAエンジンの場合マッチするパターンにおいて、バックスラッシュの回数を減らすことはパフォーマンス向上にさらに良い方法とは文字のひとつひとつを反復処理（循環処理）しなければならない。ここにオーバーヘッドがかこの部分を削減できれば、効率手的な正規表現となる。ではどうするか・・・さらに、もっと良い方法元々（上段）を下段のように変更するとバックスラッシュを抑えることができる「[^＼＼”]」は、通常の文字列にマッチするので「[^＼＼”]+」を使えば、(...)*の１回分で１度に読める通常の文字をまるまる読み込める →バックトラックを削減し、スターによる反復処理も最小限！話は飛びますが・・・正規表現にはいろいろな書き方があるお話は前回しました。例えば a, b, c, d, e, f, g のどれかに一致する文字は、 [a-g] という文字クラスを使う方法のほか a|b|c|d|e|f|gという書き方もできますね。さて・・・どっちが早いのでしょう？そうだ、ベンチマークテストをやってみよう！正規表現のベンチマークテスト方法そもそもベンチマークテストとは？ → ある仕事を行うのにどれくらい時間がかかるかを単純に計測すること時間計測のためにすることは？システム時間を取得し、問題の処理を実行し、再度システムの時間を取得するこの最初に取得したシステム時間と、次に取得したシステム時間のさが処理に要した時間とな計測時の注意点計測したい仕事の時間だけを計測する十分な仕事を実行する（コンピュータが優秀すぎると比較できない）正しい仕事を実行させる（オーバーヘッドを増やさない）ベンチマークに使うコード（PHP版) $TimesToDo = 1000; // テスト文字列の準備 $TestString = ""; for ($i = 0; $i < 1000; $i++) { $TestString .= "abababdedfg"; } // 最初のテストの実行 $start = gettimeofday(); for ($i = 0; $i < $TimesToDo; $i++) { preg_match('/^(a|b|c|d|e|f|g)+$/, $TestString); } $final = gettimeofday(); $sec = ($final['sec'] + $final['usec']/1000000) ($start['sec'] + $start['usec']/1000000); print("Alternation takes %.3f seconds\n", $sec); // 第二のテストの実行実際、自分では計測していませんが環境にもよりますが以下のような結果がでたそうです。 Alternation takes 27.404 seconds Character class takes 0.288 seconds ずいぶん違いますね。なぜ？「a|b|c|d|e|f|g」は、１つの開始位置で必ず７文字分のバックトラックが必要となり、マッチに「[a-g]」は、次の位置でマッチするまで、１文字分前進のバックトラックしか発生させない為正規表現の処理の高速化には、他にも色々ありますが、選択はNFAエンジンの場合、必ずバッ Fin 皆さん、用法用量を正しく守って使いましょう。