IT技术博客大学习 共学习 共进步

[正则优化] 加速正则失败效率

Miller 2011-09-04 23:35:10 浏览 2,342 次

上一文《正则优化一则:CSS选择符匹配》中说到了如何优化一个正则在匹配成功时的效率,而实际上正则匹配有成功就会有失败,因此失败时的效率也是需要注意的。继续上文中的正则,分析了一下优化前和优化后表达式失败时的效率:

匹配文本:.a select,.b input,.b input[

优化前                               优化后

2010-11-06_091758 2010-11-06_092446

优化前的表达式一共用了166步才完成匹配,优化后的表达式也是用了109步才完成匹配,虽然效率要高一些,但是相对于一共才28个字符的文本,总的效率还是不尽如人意。其实造成如此低效率的原因很简单:当引擎试图用表达式去匹配文本中最后一个"["时,会把之前所有已经成功匹配的字符一个一个的“吐”出来重新尝试匹配,这个尝试过程是指数级别的。因此有没有办法改造一下这个表达式,让引擎可以一组一组的“吐”出来,因为表达式(,\s*[.\w-][.\w\s\->+~]*)中并没有包括字符"[",如果引擎足够聪明就应该把这一组匹配集体“吐”出来,但是实际上却是上图的情况。

在尝试改进回溯状况的过程中发现了一个有趣的现象,在优化后的正则最后加上引号即表达式变成:

^\s*[.\w-][.\w\s\->+~]*(,\s*[.\w-][.\w\s\->+~]*)*"$

匹配结果如下:

2010-11-06_120921

新的表达式只用了21步就迅速的结束了匹配过程,相比之前的109步是个不小的进步。简单分析一下可以看出,新的表达式在回溯的时候是以组为单位进行回溯的,而不是之前的字符级别而且是双重循环,因此新的表达式结束的十分迅速。

进一步测试发现,加在表达式的最后一个字符(例如引号)必须是循环表达式中所不包含的,例如引号就不包含在(,\s*[.\w-][.\w\s\->+~]*),如果增加的字符包含在其中例如+号那么结果会和最初的表达式一样,会经过漫长的匹配后才失败。究其原因,目前还未找到合理解释,不过这也可以作为加速正则失败的一个参考案例。

同样,经过测试,添加引号后的正则完成的速度提升大概10%左右。围观地址:

http://jsperf.com/regexp-test-3

建议继续学习

  1. grep 正则表达式选项要记得转义 (阅读 6,445)
  2. 统计最近用过的linux命令 (阅读 6,405)
  3. 正则表达式基础 (阅读 6,162)
  4. 正则表达式的与或非 (阅读 5,744)
  5. 学习Grep,Sed中的正则 (阅读 5,267)
  6. URL正则表达式 (阅读 4,663)
  7. 正则表达式简要入门 (阅读 4,364)
  8. 正则转义符汇总 (阅读 4,321)
  9. 使用Oracle正则表达式监控应用到数据库的连接情况 (阅读 4,267)
  10. PHP 正则里面的两个重要技巧 (阅读 4,261)