0

解析される文字列の長さに基づいて正規表現を解析するのに指数関数的な時間を費やしているperlスクリプトがあります。コードは次のとおりです。

$BRACE_MATCH = qr/ (?: [^\(\)]+ | \((??{$BRACE_MATCH})\))* /x;
$expr="(abcdef || abcdefghijklmno)"
timethis(1, sub {$expr =~ /^($BRACE_MATCH)\|\|($BRACE_MATCH)$/});

これは実行に8秒かかります。文字列に別の文字を追加すると、16がかかります。これを行う効率的な方法はありますか？

4

2 に答える 2

2

池上が言ったように、時間がかかる理由は、パターンが文字列をチャンクに分割する方法が指数関数的にあるためです。Perlの正規表現エンジンで効率的に機能させるには、バックトラックを制限する必要があります。

++所有格の数量詞を使用してそれを行うことができます。それは、それがすべてかゼロかということによって、バックトラックを制限します。しかし、それを機能させるには、それが何に一致するかについて注意する必要があります。

[^()]++動作しない理由（バックスラッシュは必要ありません。パレンはキャラクタークラス内で特別ではありません）は|、より大きな正規表現が探しているキャラクターであるとも一致するためです。をバックトラックできる必要がありますが|、他の文字をバックトラックすることはできません（正規表現の一致以外の文字で文字列を分割する( )か|、正規表現の一致に役立たないため）。

これを試して：

$BRACE_MATCH = qr/ (?: [^()|]++ | \| | \((??{$BRACE_MATCH})\))* /x;

これは、それ$BRACE_MATCHが3つのことの任意の数のシーケンスであることを示しています。

  1. ()|（単一のチャンクとしてバックトラックされる）以外の文字列
  2. |キャラクター_
  3. バランスの取れた(...)表現

その理由

$BRACE_MATCH = qr/ (?: [^()]++ | \((??{$BRACE_MATCH})\))* /x;

一致しない(XX || YY) || ZZのは、の後に空白があること)です。その空白は[^()]++部分と一致しますが、文字列の残りの部分とも一致し（これ以上親がないため）、その後、その一部を返しません（所有格の数量詞であるため）。

于 2013-03-07T06:09:44.260 に答える
1

問題は、エンジンがそれらのどれも一致しないと判断する前に試行しなければならない多くの可能性があるということです。

Perlのエンジンは、不必要なバックトラックを回避するように設計されていますが（他のエンジンよりもマッチングが少し遅くなりますが）、最適化は明らかにここでは役に立ちません。

したがって、必要なのはバックトラックの量を減らすことであり、それは非常に簡単です。

our $BRACE_MATCH = qr/ (?> (?: [^()]+ | \( (??{ $BRACE_MATCH }) \) )* ) /x;
                       ^^^                                            ^

または、2時間前のコメントで提案したように：

our $BRACE_MATCH = qr/ (?: [^()]++ | \( (??{ $BRACE_MATCH }) \) )*+ /x;
                                 ^                                ^

これらの変更のいずれかを使用すると、テストに22秒ではなく0秒かかります。

ちなみに、あなたは使用を検討したいかもしれません(?PARNO)

(??{ code })コードのコンパイルを伴わないことを除いて同様です

于 2013-03-06T20:27:24.053 に答える