Java regexp OR 太慢

Question

为什么要模式

[0123]123456|98765

比在 Java 中执行 [0123]123456 然后 98765 慢两倍？所以单独搜索它们比用 OR 执行更快。有人有解释吗？

UPD

查看带有结果的测试示例: https://gist.github.com/cy6erGn0m/5077720

UPD2

我发现原因在 java.util.regex 中。下面的测试说明了这一点:https://gist.github.com/cy6erGn0m/5083426

正如您所看到的，Matcher 对源字符序列发出了更多的请求。因此，与两个单独的模式相比，第一个模式需要大约 2 倍的来源请求。

多行和不区分大小写是无关紧要的。或运算符影响复杂性。

Answer 1

好的。看来我找到了一半的答案。

当我们只有像 123456 这样的模式时，正则表达式引擎使用 Boyer-Moore 字符串匹配算法。但是如果你有 OR 那么它就不会使用它而只是比较每个字符。

由于它的性质，Boyer-Moore 算法可能更有效，所以这就是第二种方法更快的原因。

例如，如果我输入字符串“11223344”和模式“123456”，那么根据 Boyer-Moore 实现，唯一应该检查的字符是第 5 个位置的“3”。这比尝试针对每个字符测试模式要有效得多。