正则表达式太慢了吗？ 现实生活中的例子，简单的非正则表达式替代方案更好
我见过这里的人发表过像“正则表达式太慢了！”这样的评论，或者“你为什么要用正则表达式做一些简单的事情！” （然后提出10+行代替）等。
我还没有真正在工业环境中使用正则表达式，所以我很好奇是否有正则表达式显然太慢的应用程序， 并且存在一个简单的非正则表达式替代方案，其表现更好（甚至可能渐近！）更好。
显然，许多使用复杂字符串算法的高度专业化的字符串操作将轻松胜过正则表达式，但我所说的是存在简单解决方案且明显优于正则表达式的情况。
当然，重要的是主观的，但我认为合理的标准是，如果它只使用String ， StringBuilder等，那么它可能很简单。
注意 ：我非常感谢能够certificate以下内容的答案：
- 一个初学者级的正则表达式解决方案，解决非玩具现实生活中可怕的问题
- 简单的非正则表达式解决方案
- 专家级正则表达式重写，表现相当
我记得一本教科书的例子。 请注意，建议不要将以下方法用于生产用途！ 请改用适当的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。）
我尝试了各种构造的性能，不幸的是我发现Java正则表达式不能执行我认为非常可行的优化。
Java正则表达式使用O(N)匹配"(?s)^.*+$"
这非常令人失望。 ".*"采用O(N)是可以理解的，但是以锚点（ ^和$ ）和单行模式Pattern.DOTALL/(?s)的forms优化“提示”，甚至使重复占有（即没有回溯），正则表达式引擎仍然无法看到这将匹配每个字符串，并且仍然必须匹配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(N)中的O(1)长度前缀模式 。 也就是说， "(?s)^[aeiou]{3}.*$"检查字符串是否以O(N) 3个小写字母开头，当它应该可以优化为O(1) 。
我认为前缀匹配更适合正则表达式，但我认为不可能提出一个O(1)模式来匹配上述（除非有人可以certificate我错了）。
显然你可以做s.substring(0, 3).matches("(?s)^[aeiou]{3}.*$") “技巧”，但模式本身仍然是O(N) ; 您只需使用substring手动将N减少为常量。
因此，对于真正长字符串的任何类型的有限长度前缀/后缀匹配，您应该在使用正则表达式之前使用substring进行预处理; 否则它是O(N) ，其中O(1)就足够了。
正则表达式太慢了吗？
正则表达本质上并不慢。 基本模式匹配是O（n），难以改进，当然对于非平凡模式。
在我的测试中，我发现了以下内容：
使用java的String.split方法（使用正则表达式）在1,000,000次迭代下花了2176ms。 使用此自定义拆分方法在1,000,000次迭代下耗时43ms。
当然，它只有在你的“正则表达式”完全是文字的情况下才有效，但在这种情况下，它会更快。
List array = new ArrayList (); String split = "ab"; String string = "aaabaaabaa"; int sp = 0; for(int i = 0; i < string.length() - split.length(); i++){ if(string.substring(i, i + split.length()).equals(split)){ //Split point found array.add(string.substring(sp, i)); sp = i + split.length(); i += split.length(); } } if(sp != 0){ array.add(string.substring(sp, string.length())); } return array;
那么回答你的问题，理论上它更快吗？ 是的，绝对，我的算法是O（n），其中n是要拆分的字符串的长度。 （我不确定是什么样的正则表达式）。 它实际上更快吗？ 好吧，超过100万次迭代，我基本上节省了2秒。 所以，这取决于你的需求我想，但我不会过分担心将所有使用正则表达式的代码移植到非正则表达式版本，事实上，如果模式非常复杂，那么这可能是必要的。像这样分开是行不通的。 但是，如果你正在分裂，比如逗号，这种方法会表现得更好，虽然“好得多”在这里是主观的。
好吧，并非总是但有时很慢，取决于模式和实现。
一个简单的例子，比正常替换慢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 >>>