☰

正規表現：Perlの正規表現は非常に遅いです。最適化する方法は？

tag-icon • tag-icon regular-expression perl
正規表現：Perlの正規表現は非常に遅いです。最適化する方法は？

これ：

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  perl -pe '/^(.*?B(?:A.*?B){30})A/'

私のコンピュータでは、なんと8秒かかりました。私はそれが最大数ミリ秒かかると思いました。

10ms未満かかります。

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
   perl -pe '/^(.*?B(?:A.*?B){30})A/'

最初の作業をより早く進めるにはどうすればよいですか？

正規表現になるにはAとBが必要です。つまり、これらは単純な単一文字ではありません。

答え1

負の予測合計の使用.:

perl -pe '/^((?:(?!BA).)*?B(?:A(?:(?!BA).)*?B){30})A/'

きれいではありませんが効果的です。

答え2

使用幸せ（以前のPerl_6）

Rakuに変換された上記のPerl Regexは非常に遅かった（まだ非常に遅かった。テストは2回繰り返された）。

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'  49.44s user 0.41s system 100% cpu 49.791 total

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'  52.92s user 0.42s system 100% cpu 53.269 total

単一の:文字を追加してRakuの速度を大幅に向上させます（ローカルバックトラッキング防止、2回繰り返しテスト）。

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'  0.22s user 0.04s system 138% cpu 0.185 total

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'  0.21s user 0.04s system 139% cpu 0.177 total

Rakuにはバックトラッキングをオフにするいくつかの方法があります。逆追跡は:ratchet（または）副詞を使用して全体的にオフにできます:r。上記のコードでは、30Regexエンジンがアトミックインスタンスを検索する場所で逆追跡がローカルにオフになります。

[A .*? B] ** 30 ~になる [A .*? B] **: 30

最後に、最もパフォーマンスの良いRaku正規表現（および関連参照）は次のとおりです。

raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'

https://docs.raku.org/言語/regexes.html#Preventing_backtracking:_:
https://docs.raku.org/言語/regexes.html#Ratchet
https://docs.raku.org/言語/regexes.html

関連情報