我在这里看到人们发表了诸如“正则表达式太慢了！”之类的评论，或者“为什么要使用正则表达式做这么简单的事情！（然后提出10行以上的替代方案），等等。
我还没有在工业环境中真正使用正则表达式，所以我很好奇是否有正则表达式明显太慢的应用程序，并且存在一个简单的非正则表达式替代方案，其性能显着（甚至可能是渐近的！）更好。
显然，许多具有复杂字符串算法的高度专业化的字符串操作将很容易超过正则表达式，但我谈论的是存在简单解决方案并且显着优于正则表达式的情况。
当然，什么是简单的是主观的，但我认为一个合理的标准是，如果它只使用，等等，那么它可能很简单。StringStringBuilder
注意：我非常希望得到以下答案：
我记得一个教科书上的例子，一个正则表达式变坏了。请注意，不建议将以下任何一种方法用于生产用途！请改用适当的 CSV 解析器。
此示例中犯的错误很常见：使用点，其中较窄的字符类更适合。
在每行正好包含 12 个以逗号分隔的整数的 CSV 文件中，找到在第 6 个位置具有 13 的行（无论 13 位于其他位置）。
1, 2, 3, 4, 5, 6, 7, 8 ,9 ,10,11,12 // don't match
42,12,13,12,32,13,14,43,56,31,78,10 // match
42,12,13,12,32,14,13,43,56,31,78,10 // don't match
我们使用正好包含 11 个逗号的正则表达式：
".*,.*,.*,.*,.*,13,.*,.*,.*,.*,.*,.*"
这样，每个“.*”都限制为一个数字。此正则表达式解决了任务，但性能非常差。（在我的计算机上，每个字符串大约600微秒，匹配和不匹配字符串之间几乎没有区别。
一个简单的非正则表达式解决方案是每行并比较第6个元素。（快得多：每串 9 微秒。split()
正则表达式如此缓慢的原因是“*”量词在默认情况下是贪婪的，因此第一个“.*”尝试匹配整个字符串，然后开始逐个字符回溯。运行时在一行上的数字计数中呈指数级。
因此，我们将贪婪的量词替换为不情愿的量词：
".*?,.*?,.*?,.*?,.*?,13,.*?,.*?,.*?,.*?,.*?,.*?"
这对于匹配的字符串（系数为 100）的性能要好得多，但对于不匹配的字符串，性能几乎保持不变。
执行正则表达式将点替换为字符类“[^，]”：
"[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,13,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*"
（对于匹配的字符串，这需要每个字符串 3.7 微秒，对于我的计算机上不匹配的字符串，这需要 2.4 微秒。
我对各种结构的性能进行了一些实验，不幸的是，我发现Java正则表达式不能执行我认为非常可行的优化。
O(N)"(?s)^.*+$"
这是非常令人失望的。这是可以理解的，但是通过锚点（和）和单行模式形式的优化“提示”，即使使重复具有所有格（即没有回溯），正则表达式引擎仍然无法看到这将匹配每个字符串，并且仍然必须在中匹配。".*"O(N)^$Pattern.DOTALL/(?s)O(N)
当然，这种模式不是很有用，但请考虑下一个问题。
O(N)"(?s)^A.*Z$"
同样，我希望正则表达式引擎可以看到，由于锚点和单行模式，这本质上与非正则表达式相同：O(1)
s.startsWith("A") && s.endsWith("Z")
不幸的是，不，这仍然是。非常令人失望。不过，这并不是很有说服力，因为存在一个漂亮而简单的非正则表达式替代方案。O(N)
O(N)"(?s)^.*[aeiou]{3}$"
此模式匹配以 3 个小写元音结尾的字符串。没有漂亮而简单的非正则表达式替代方案，但是您仍然可以编写与此匹配的非正则表达式，因为您只需要检查最后3个字符（为简单起见，我们可以假设字符串长度至少为3）。O(1)
我还尝试了，试图告诉正则表达式引擎忽略其他所有内容，只需检查最后3个字符，但当然这仍然是（从上面的第一部分开始）。"(?s)^.*$(?<=[aeiou]{3})"O(N)
但是，在此特定方案中，正则表达式可以通过将其与 组合来使其有用。也就是说，您可以手动限制模式以尝试仅匹配最后3个字符，而不是查看整个字符串是否与模式匹配。通常，如果您事先知道该模式具有有限长度的最大匹配，则可以从非常长的字符串末尾开始，并且正则表达式仅在该部分上获得必要数量的字符。substringsubstringsubstring
static void testAnchors() {
String pattern = "(?s)^.*[aeiou]{3}$";
for (int N = 1; N < 20; N++) {
String needle = stringLength(1 << N) + "ooo";
System.out.println(N);
boolean b = true;
for (int REPS = 10000; REPS --> 0; ) {
b &=
needle
//.substring(needle.length() - 3) // try with this
.matches(pattern);
}
System.out.println(b);
}
}
此测试中的字符串长度呈指数级增长。如果你运行这个测试，你会发现它开始真正变慢之后（即字符串长度1024）。但是，如果您取消注释该行，则整个测试将立即完成（这也证实了问题不是因为我没有使用，这充其量会产生持续改进，而是因为patttern需要匹配，当渐近增长是指数时，这是有问题的）。10substringPattern.compileO(N)N
Java正则表达式似乎很少或根本没有基于模式的优化。特别是后缀匹配特别昂贵，因为正则表达式仍然需要遍历字符串的整个长度。
值得庆幸的是，使用（如果您知道匹配的最大长度）在切碎的后缀上执行正则表达式仍然可以允许您使用正则表达式进行时间上的后缀匹配，而与输入字符串的长度无关。substring
//update：实际上我刚刚意识到这也适用于前缀匹配。Java 正则表达式与 O（N） 中的 O（1） 长度前缀模式匹配。也就是说，检查字符串是否以 3 个小写字母开头，而此时该字符串应可优化为 。"(?s)^[aeiou]{3}.*$"O(N)O(1)
我认为前缀匹配会更友好，但我认为不可能提出一个-runtime模式来匹配上述内容（除非有人可以证明我错了）。O(1)
显然你可以做“把戏”，但模式本身仍然是;您刚刚通过使用 手动减少到常量。s.substring(0, 3).matches("(?s)^[aeiou]{3}.*$")O(N)Nsubstring
因此，对于任何一种非常长的字符串的有限长度前缀/后缀匹配，您应该在使用正则表达式之前使用预处理;否则就够了。substringO(N)O(1)
