java - 正则表达式太慢了吗？现实生活中简单的非正则表达式替代方案更好的例子

Question

我看到这里有人发表评论，如“正则表达式太慢了!”，或“你为​​什么要使用正则表达式做这么简单的事情!” (然后提供 10 多行替代方案)，等等。

我还没有真正在工业环境中使用正则表达式，所以我很好奇是否有应用程序证明正则表达式太慢，并且其中简单非-存在性能显着(甚至可能渐近!)更好的正则表达式替代方案。

显然，许多使用复杂字符串算法的高度特化的字符串操作很容易优于正则表达式，但我说的是存在简单解决方案并且显着优于正则表达式的情况。

简单当然是主观的，但我认为一个合理的标准是，如果它只使用String、StringBuilder等，那么它可能很简单。

---

注意:我非常感谢能够证明以下内容的答案:

1. 针对非玩具现实生活问题的初级正则表达式解决方案，但效果非常糟糕
2. 简单的非正则表达式解决方案
3. 性能相当的专家级正则表达式重写

Answer 1

我记得正则表达式变坏的教科书示例。请注意，不建议将以下任何方法用于生产!请改用适当的 CSV 解析器。

这个例子中犯的错误很常见:在更适合较窄字符类的地方使用点。

在一个 CSV 文件中，每行恰好包含 12 个以逗号分隔的整数，找到第 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 微秒，匹配和不匹配的字符串之间几乎没有区别。)

一个简单的非正则表达式解决方案是 split() 每行并比较第 6 个元素。 (快得多:每个字符串 9 微秒。)

正则表达式如此缓慢的原因是默认情况下“*”量词是贪婪的，因此第一个“.*”尝试匹配整个字符串，然后开始逐个字符回溯。运行时间在一行中的数字计数方面呈指数级增长。

因此我们将贪婪量词替换为不情愿的量词:

".*?,.*?,.*?,.*?,.*?,13,.*?,.*?,.*?,.*?,.*?,.*?"

对于匹配的字符串，这表现得更好(100 倍)，但对于非匹配的字符串，性能几乎没有变化。

高性能正则表达式用字符类“[^,]”替换点:

"[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,13,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*"

(在我的计算机上，每个字符串匹配的字符串需要 3.7 微秒，不匹配的字符串需要 2.4 微秒。)