パフォーマンス

パターンに記述可能な要素のうち、幾つかの要素は、他の要素よりも 効率的に処理されます。 (a|e|i|o|u) のような選択肢の集合よりも [aeiou] のような文字クラスの方が効率的です。一般に、構文が 最も単純なものが、たいてい最も効率が良くなります。Jeffrey Friedl の本には、正規表現の性能を向上させる最適化について 様々な検討が行われています。

パターンが .* で始まり、PCRE_DOTALL オプションを設定した場合、対象文字列の始端でしかマッチできないため、 PCRE は、暗黙のうちにそのパターンを固定パターンとみなします。しかし、 PCRE_DOTALL を設定しない場合、メタ文字 . が改行にマッチせず、 対象文字列が改行を含む場合、パターンは文字列の始端からではなく各改行の 直後の文字からマッチする可能性があるため、PCRE は この最適化を行うことができません。 例えば、パターン

      (.*) second
      
を、対象文字列 "first\nand second"(ここで、\n は改行文字を意味します)に マッチングさせます。 1 番目のキャプチャ文字列は、"and" になります。 このような動作をするには、 PCRE は対象文字列の各改行文字の後から マッチングを繰り返し行う必要があります。

このようなパターンを、改行を含まない対象文字列に適用する場合は、 PCRE_DOTALL を設定するか、固定パターンであることを明示的に示すためにパターンを ^.* で開始すると最高の性能が得られます。そうすることで、PCRE が対象文字列の改行を探し、そこからマッチングが再び始められることを 防止します。

制限のない繰り返しをネストするようなパターンについては注意が必要です。 そのようなパターンが、マッチが成功し得ない文字列に適用された場合には、 実行に長い時間を要します。

      (a+)*
      
というパターンを考えてみましょう。

このパターンが "aaaa" にマッチし得る方法は 33 通りもあります(つまり、 * による繰り返しは 0, 1, 2, 3 もしくは 4 回の繰り返しにマッチし、 0 回以外のそれぞれの場合について、 + による繰り返しは様々な回数分 マッチします)〔訳注:a 1文字の 4 回繰り返しとか、 a 1文字とa 3文字の 組合せとかを意味する〕。この数は、文字列が長くなるにつれて急激に 増大します。このパターンの後ろに、マッチが失敗するような別のパターンが 続いていて、パターン全体としてマッチが失敗してしまう場合、PCREは、基本的に 取り得るすべての選択肢を調べるため、非常に長い時間がかかります。

      (a+)*b
      
のように単一の文字リテラルが最後にある場合には最適化が行われます。 標準のマッチング手順に着手する前に、PCRE は対象文字列の後方に "b" があるかどうかを調べます。無い場合には、直ちにマッチは失敗します。 文字リテラルが最後にない場合には、この最適化は行われません。
      (a+)*\d
      
というパターンと上に挙げたパターンの動作を比較してみましょう。 "a" 文字だけが連続する行に適用した場合、前者のパターンでは、 ほぼ瞬間的に失敗と判定されます。一方、後者のパターンでは、 文字列の長さがおよそ 20 文字を超えると、かなりの時間がかかります。

関連キーワード:  パターン, 文字, PCRE, マッチ, パフォーマンス, 対象, 改行, マッチング, 失敗, 繰り返し