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

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()每一行并比较第六个元素.(快得多:每串9微秒.)

正则表达式如此慢的原因是默认情况下"*"量词是贪婪的,因此第一个".*"尝试匹配整个字符串,然后开始逐个字符地回溯.运行时是一行中数字的指数.

所以我们用不情愿的人取代贪婪的量词:

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

这对匹配的字符串执行得更好(因子为100),但对于不匹配的字符串,性能几乎没有变化.

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

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

(对于匹配的字符串,每个字符串需要3.7微秒,而对于我计算机上不匹配的字符串,这需要2.4.)

Answer 2

我尝试了各种构造的性能,不幸的是我发现Java正则表达式不能执行我认为非常可行的优化.

Java正则表达式需要O(N)匹配"(?s)^.*+$"

这非常令人失望.这是可以理解的".*"采取O(N),但与优化"暗示",在锚(形式^和$)和单行模式Pattern.DOTALL/(?s),甚至使得重复占有欲(即无回溯),正则表达式引擎还是没能看到,这将匹配每一个字符串,仍然必须匹配O(N).

当然,这种模式不是很有用,但考虑下一个问题.

Java正则表达式需要O(N)匹配"(?s)^A.*Z$"

再一次,我希望正则表达式引擎能够看到由于锚点和单行模式,这与O(1)非正则表达式基本相同:

 s.startsWith("A") && s.endsWith("Z")

不幸的是,不,这仍然是O(N).非常失望.仍然,不是很有说服力,因为存在一个漂亮而简单的非正则表达式替代方案.

Java正则表达式需要O(N)匹配"(?s)^.*[aeiou]{3}$"

此模式匹配以3个小写元音结尾的字符串.没有好的和简单的非正则表达式替代方案,但你仍然可以编写一些与之匹配的非正则表达式O(1),因为你只需要检查最后3个字符(为简单起见,我们可以假设字符串长度至少为3 ).

我也尝试过"(?s)^.*$(?<=[aeiou]{3})",试图告诉正则表达式引擎忽略其他所有内容,只检查最后3个字符,但当然这仍然是O(N)(从上面的第一部分开始).

但是,在这种特殊情况下,通过将正则表达式与其组合可以使正则表达式变得有用substring.也就是说,您可以手动限制模式以尝试仅匹配最后3个字符,而不是查看整个字符串是否与模式匹配substring.一般来说,如果您事先知道模式具有有限长度的最大匹配,则可以substring从非常长的字符串的末尾开始必要的字符数量,并且仅在该部分上使用正则表达式.

测试线束

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);
    }
}

此测试中的字符串长度呈指数增长.如果你运行这个测试,你会发现它开始真的慢下来10(即字符串长度1024).substring但是,如果取消注释该行,整个测试将立即完成(这也证实问题不是因为我没有使用Pattern.compile,这会产生最好的持续改进,而是因为patttern需要O(N)匹配,当渐近增长N是指数时,这是有问题的.

结论

似乎Java正则表达式几乎没有根据模式进行优化.特别是后缀匹配特别昂贵,因为正则表达式仍然需要遍历字符串的整个长度.

值得庆幸的是,使用substring(如果知道匹配的最大长度)对切​​断的后缀执行正则表达式仍然允许您在时间上使用正则表达式进行后缀匹配,而与输入字符串的长度无关.

//更新:实际上我刚刚意识到这也适用于前缀匹配.Java正则表达式匹配O(1)长度前缀模式O(N).也就是说,"(?s)^[aeiou]{3}.*$"检查一个字符串是否以3个小写字母开头,O(N)并且应该可以优化O(1).

我认为前缀匹配对正则表达式更友好,但我认为不可能想出一个O(1)与上面相符的-runtime模式(除非有人能证明我错了).

显然你可以做s.substring(0, 3).matches("(?s)^[aeiou]{3}.*$")"技巧",但模式本身仍然存在O(N); 您只需N通过使用手动缩减为常量substring.

因此,对于真正长字符串的任何类型的有限长度前缀/后缀匹配,您应该substring在使用正则表达式之前进行预处理; 否则它的O(N)地方O(1)就足够了.

Answer 3

正则表达式太慢了吗？

正则表达本质上并不慢.基本模式匹配是O(n),难以改进,当然对于非平凡模式.

Answer 4

嗯，并不总是，但有时很慢，取决于模式和实现。

一个简单的例子，比正常替换慢 2 倍，但我不认为它那么慢。

>>> import time,re
>>>
>>> x="abbbcdexfbeczexczczkef111anncdehbzzdezf" * 500000
>>>
>>> start=time.time()
>>> y=x.replace("bc","TEST")
>>> print time.time()-start,"s"
0.350999832153 s
>>>
>>> start=time.time()
>>> y=re.sub("bc","TEST",x)
>>> print time.time()-start,"s"
0.751000165939 s
>>>