IT技术博客大学习 共学习 共进步
全部 移动开发 后端 数据库 AI 算法 安全 DevOps 前端 设计 开发者

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

Miller 2011-09-04 23:35:10 累计浏览 2,422 次
本机暂存

上一文《正则优化一则: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. 对基本有序的序列排序算法 (2026-06-11 17:46:49)
  2. Four Levels Of Customer Understanding (2026-05-22 21:00:00)
  3. 除法的意义 (2026-04-12 20:52:17)

查看更多 算法 文章 →

建议继续学习

  1. vim几个小技巧(批量替换,列编辑) (累计阅读 37,515)
  2. 由浅入深探究mysql索引结构原理、性能分析与优化 (累计阅读 16,519)
  3. AWK介绍 (累计阅读 6,707)
  4. 正则表达式基础 (累计阅读 6,316)
  5. 一次神奇的MySQL优化 (累计阅读 6,080)
  6. Perl命令行常见用法及技巧 (累计阅读 5,912)
  7. 正则表达式的与或非 (累计阅读 5,868)
  8. 百度搜索URL参数解析 (累计阅读 5,717)
  9. VIM查找替换归纳总结 (累计阅读 5,388)
  10. mysql索引浅析 (累计阅读 5,334)