Java，惰性表达式的正则表达式性能不佳

Question

代码实际上是在 Scala (Spark/Scala) 中，但是根据文档，库 scala.util.matching.Regex 委托给 java.util.regex。

基本上，代码从配置文件中读取一堆正则表达式，然后将它们与提供给 Spark/Scala 应用程序的日志进行匹配。一切正常，直到我添加了一个正则表达式来提取由制表符分隔的字符串，其中制表符已展平为“#011”（通过 rsyslog）。由于字符串可以有空格，我的正则表达式看起来像： (.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)#011(.+?)

当我将此正则表达式添加到列表中时，应用程序需要很长时间才能完成日志处理。为了让您了解延迟的严重程度，在我的 Spark 集群上，典型的一百万行批处理 match/extract 只需不到 5 秒。如果我加上上面的表达式，一批需要一个小时！

在我的代码中，我尝试了几种匹配正则表达式的方法：

if ( (regex findFirstIn log).nonEmpty ) { do something }
val allGroups = regex.findAllIn(log).matchData.toList if (allGroups.nonEmpty) { do something }
if (regex.pattern.matcher(log).matches()){do something}

当上面提到的正则表达式添加到正则表达式列表时，这三个都表现不佳。有任何改进正则表达式性能或更改正则表达式本身的建议吗？

标记为 duplicate 的 Q/A 有一个 link 我觉得很难理解。如果引用的软件 regexbuddy 是免费的或者至少在 Mac.

上运行过，那么理解文本可能会更容易一些

我试过否定前瞻，但我不知道如何否定一个字符串。而不是 /(.+?)#011/，类似于 /([^#011]+)/ 但它只是表示否定“#”或“0”或“1”。如何否定“#011”？即使在那之后，我也不确定否定是否会解决我的性能问题。

Answer 1

最简单的方法是在 #011 上拆分。如果你想要一个正则表达式，你确实可以否定字符串，但这很复杂。我会选择原子组

(?>(.+?)#011)

一经匹配，不再回溯。完成并期待下一组。

取反字符串

#011 的补码是任何不以 # 开头，或以 # 开头且后面不跟 0，或以两者开头的任何内容并没有跟随……你知道的。为了便于阅读，我添加了一些空白：

 ((?: [^#] | #[^0] | #0[^1] | #01[^1] )+) #011

很糟糕，不是吗？与您的原始表达式不同，它匹配换行符（您没有具体说明它们）。

另一种方法是使用否定前瞻：(?!#011) 匹配当且仅当以下字符不是 #011，但不吃任何东西，所以我们使用 . 来吃一个单个字符：

 ((?: (?!#011). )+)#011

这一切都非常复杂，而且很可能比简单地使用原子组的性能要差。

优化

在我上面的正则表达式中，第一个是最好的。然而，正如 Casimir et Hippolyte 所写，还有改进的空间（因子 1.8）

( [^#]*+ (?: #(?!011) [^#]* )*+ ) #011

它并不像看起来那么复杂。首先以原子方式匹配任意数量（包括零）的非 #（尾部 +）。然后匹配 # 后面没有跟 011，然后再匹配任意数量的非 #。重复最后一句话任意次数。

它的一个小问题是它也匹配一个空序列，我找不到解决它的简单方法。

Java，惰性表达式的正则表达式性能不佳

Java, poor regex performance with lazy expressions

java

regex

performance

non-greedy

取反字符串

优化