2

なぜパターン

[0123]123456|98765

Javaで[0123]123456を実行してから98765を実行すると2倍遅くなりますか? したがって、OR で実行するよりも、個別に検索する方が高速です。誰か説明がありますか？

UPD

結果のテスト例については、 https ://gist.github.com/cy6erGn0m/5077720 を参照してください。

UPD2

その理由が java.util.regex 内にあることを発見しました。次のテストで明らかになります: https://gist.github.com/cy6erGn0m/5083426

ご覧のとおり、Matcher は source char シーケンスに対して大幅に多くのリクエストを行います。したがって、最初のパターンでは、2 つの個別のパターンよりも約 2 倍多くのリクエストを調達する必要があります。

複数行および大文字と小文字を区別しないことは無関係です。または、演算子が複雑さに影響します。

4

1 に答える 1

2

わかった。答えの半分を見つけたようです。

123456 のようなパターンしかない場合、正規表現エンジンは Boyer-Moore 文字列マッチング アルゴリズムを使用します。ただし、OR がある場合は、それを使用せず、単にすべての文字を比較します。

その性質上、Boyer-Moore アルゴリズムの方がはるかに効率的である可能性があるため、2 番目のアプローチの方が高速です。

たとえば、入力文字列「11223344」とパターン「123456」がある場合、Boyer-Moore の実装によれば、チェックする必要がある文字は 5 番目の位置にある「3」だけです。これは、すべての文字に対してパターンをテストしようとするよりもはるかに効率的です。

于 2013-03-05T17:40:14.990 に答える