9

次の Python コードは非常に遅いです。

import re
re.match( '([a]+)+c', 'a' * 30 + 'b' )

30 をより大きな定数に置き換えると、さらに悪化します。

連続による解析のあいまいさが原因+だと思いますが、私は正規表現の解析と照合の専門家ではありません。これは Python 正規表現エンジンのバグですか、それとも適切な実装でも同じことが起こりますか?

私は Perl の専門家ではありませんが、次のコードは非常に高速に返されます。

perl -e '$s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; print "ok\n" if $s =~ m/([a]+)+c/;'

また、「a」の数を増やしても、実行速度は大幅に変わりません。

4

2 に答える 2

13

Perl は 2 つ+の s を 1 つにまとめるほど賢いと思いますが、Python はそうではありません。これが最適化されていない場合、エンジンが何をするか想像してみましょう。また、キャプチャは一般的にコストがかかることを覚えておいてください。また、両方+の s が貪欲であるため、エンジンは 1 回のバックトラッキング ステップでできるだけ多くの繰り返しを使用しようとすることに注意してください。各箇条書きは、1 つのバックトラッキング ステップを表します。

  • エンジンは[a]可能な限り多くを使用し、30 秒すべてを消費しますa。その後、それ以上進むことができないため、最初の繰り返しを離れて30秒をキャプチャしaます。次の繰り返しがオンになり、別の繰り返しでさらに消費しようとします([a]+)が、もちろんうまくいきません。そして、 はc一致しませんb。
  • バックトラック！a内側の繰り返しによって消費された最後のものを捨てます。この後、再び内側の繰り返しを残すため、エンジンは29秒をキャプチャしaます。次に、もう一方+が開始され、内側の繰り返しが再度試行されます (30 番目を消費しますa)。次に、内部の繰り返しをもう一度残します。これにより、キャプチャ グループも離れるため、最初のキャプチャは破棄され、エンジンは最後のをキャプチャaします。c一致しませんb。
  • バックトラック！中にもう一枚捨てるa。28秒をキャプチャしaます。キャプチャ グループの 2 番目 (外側の繰り返し) は、キャプチャされた最後の 2 秒を消費しaます。一致しません。cb
  • バックトラック！これで、2 番目の他の繰り返しでバックトラックし、2 番目の s を捨てることができますa。残ったものはキャプチャされます。次に、3 回目のキャプチャグループに入り、最後のa. c一致しませんb。
  • バックトラック！a最初の繰り返しで27秒まで。

これが簡単な視覚化です。各行は 1 つのバックトラッキング ステップを表し、括弧の各セットは内側の繰り返しの 1 つの消費を示します。中かっこは、バックトラッキングのそのステップで新しくキャプチャされたものを表しますが、通常のかっこは、この特定のバックトラッキング ステップでは再訪されません。また、b/cは一致しないため省略します。

{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaa}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaa}{aaaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aaa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa){a}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a)(a){a}{a}

と。それで。の上。

最後に、エンジンは のサブセットのすべての組み合わせも試行して(最初の 29秒から最初の 28秒aまでバックトラック)、それも一致しないことを発見することに注意してください。aaca

正規表現エンジンの内部の説明は、 regular-expressions.infoに散在する情報に基づいています。

これを解決するには. のいずれかを削除するだけ+です。または、使用量を取得したいr'a+c'場合。ar'(a+)s'

最後に、あなたの質問に答えます。私はこれを Python の正規表現エンジンのバグとは考えていませんが、(どちらかと言えば) 最適化ロジックの欠如にすぎません。この問題は一般的には解決できないため、エンジンが壊滅的なバックトラックを自分で処理する必要があると想定するのは不合理ではありません。Perl が十分に単純なケースを十分に認識できるほど賢い場合は、はるかに優れています。

于 2012-11-01T14:42:12.293 に答える
4

正規表現を書き直して、ネストされた量指定子を削除して、 「壊滅的なバックトラッキング」を排除します (この質問を参照してください)。

re.match( '([a]+)+c', 'a' * 30 + 'b' )
# becomes
re.match( 'a+c', 'a' * 30 + 'b' )
于 2012-11-01T14:41:42.517 に答える