Perl best practices[Perlベストプラクティス] 12章 正規表現 12.22~12.24

バックトラックを防ぐリファクタリング

共有部分を括り出す

m{
    with \s+ each \s+ $EXPR \s* $BLOCK
  | with \s+ each \s+ $VAR  \s* in \s* [(] $LIST [)] \s* $BLOCK
  | with \s+ [(] $LIST [)] \s* $BLOCK
}xms

　上記のコードは頻繁にバックトラックが起こる。例えばeachのeでマッチングの失敗したとすると、2つ目の選択肢に移り、またwith \s+でマッチングを試み、そしてまたeachで失敗して、３つ目の選択肢でまたまたwith \s+でマッチングしようとする。
　この手の正規表現をPerlが内部的に最適化してくれると良いけれど、それをPerlに任せると処理コストが高すぎるので、自分でリファクタリングする必要がある。
　リファクタリングの内容は、共通パターンを括り出すとことだが、実際の手順としては、まず選択肢の集合を(?:)で囲む。そして、共通部分を外に出す。この２ステップを踏む。

m{
    with \s+ each \s+ $EXPR \s* $BLOCK
  | with \s+ each \s+ $VAR  \s* in \s* [(] $LIST [)] \s* $BLOCK
  | with \s+ [(] $LIST [)] \s* $BLOCK
}xms

#まず選択肢集合を括弧で囲む
m{
    (?: with \s+ each \s+ $EXPR \s* $BLOCK
      | with \s+ each \s+ $VAR  \s* in \s* [(] $LIST [)] \s* $BLOCK
      | with \s+ [(] $LIST [)] \s* $BLOCK
    )
}xms

#共通部分を外に出す。頭のwith \s+ とお尻の\s+ $BLOCK。
m{
    with \s+
    (?: each \s+ $EXPR
      | each \s+ $VAR  \s* in \s* [(] $LIST [)]
      | [(] $LIST [)]
    )
    \s* $BLOCK
}xms

#まだeach \s+が括り出せるので、括弧で囲む。
m{
    with \s+
    (?: 
        (?: each \s+ $EXPR
          | each \s+ $VAR  \s* in \s* [(] $LIST [)]
        )
      | [(] $LIST [)]
    )
    \s* $BLOCK
}xms

#each \s+を外に出す。
m{
    with \s+
    (?: each \s+
        (?: $EXPR
          | $VAR  \s* in \s* [(] $LIST [)]
        )
      | [(] $LIST [)]
    )
    \s* $BLOCK
}xms

　この方法の欠点として可読性の低下が挙げられるが、正規表現を定数に変換するなどして対処すること。

(?>)でさらにバックトラックを無くす

先ほどの、選択肢集合から共通部分を括り出す方法は、外に出されたプレフィックスに関しては当然バックトラックは起こらないけれども、外に出したサフィックス(接尾辞)でマッチングに失敗した場合は、選択肢集合にバックトラックして、選択肢集合の中でありとあらゆる可能性を走査するため、バックトラックが頻発する。
　もし、マッチングが最初から最後まで成功するか、まったくしないかの2パターン（相互排他関係）ならば、サフィックスでマッチングに失敗した際に、バックトラックする必要はない。このことをPerlに教えるために(?>)を使用する。
　先ほどの例では、(?:)を(?>)に置き換えるだけでいい。


　この(?>)の説明で紹介されている例が興味深かった。それは、ほぼ正しい入力によって、正規表現のマッチングが失敗する場合は、バックトラックが頻発すること。紹介されている例は、コンマで区切られたリストとマッチする正規表現でした。

my $str =~ m{ [(]
           $ITEM       #少なくとも1つは要素があるようにする
           (?:         #コンマと要素のペア。
                ,
                $ITEM
           )*
           [)]
         }xms;

　このとき、入力されたリストが閉じ括弧が無かったらどうなるか。まず[)]でパターンマッチに失敗した後、前に成功したマッチ(?:,$ITEM)*の最後の繰り返し部分、つまり、リストの最後のコンマと要素の組1つとのマッチ成功を捨てて、その分を[)]とのマッチに使用する。しかし、このマッチは当然失敗する。そうすると、バックトラックして、また一つ前のマッチ成功を捨てて[)]とのマッチを試みる。これは、リスト要素の数だけ繰り替えされる。
　これを防ぐために、(?>)を使用するが、先ほどの説明通りに、単純に(?:)を(?>)に置き換えてはいけない。なぜなら*を含めて、パターンの方法は1つとしなければならないから。(?> (?: , $ITEM)* )とする。
　まとめ。2つの部分パターンXとYが、照合する文字列に対して相互排他の関係にあるならば、

• X | Y は (?> X | Y )
• X* Y は (?> X*) Y

とすること。

文字列比較

固定文字列との照合は|ではなく、個別にeqする

初めから照合したい文字列が決まっている場合、(?: A | B | C)より、($hoge eq 'A') || ($hoge eq 'B') || ($hoge eq 'C')のほうが20%程高速であるし、コードも読み易くなる。

固定文字列の数が多い場合や、数が決まっていない場合

　選択肢の数が多い場合や、数が決まっていない場合は、正規表現を生成するほうが適していると思うかもしれないがeqを使用したほうがすっきりする。ただし低速。

Readonly my $EXIT_WORD => join '|', @EXIT_WORDS;
last COMMAND if $cmd =~ m{\A (?: $EXIT_WORD ) \z}xms;

use List::MoreUtils qw( any );
last COMMAND if any { $cmd eq $_ } @EXIT_WORDS;