☰

正则表达式：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 秒。我原以为最多需要几毫秒。

这需要 < 10 毫秒：

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）

上面的 Perl Regex 翻译成 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 /;'  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。在上面的代码中，回溯在 Regex 引擎搜索30原子实例的地方本地关闭：

[A .*? B] ** 30 变成 [A .*? B] **: 30

最终的、性能最佳的 Raku 正则表达式（和相关参考文献）如下。

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

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

相关内容