技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> [正则优化] 加速正则失败效率

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

浏览:1604次  出处信息

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

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

优化前                               优化后

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

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

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

匹配结果如下:

2010-11-06_120921

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

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

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

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

建议继续学习:

  1. 统计最近用过的linux命令    (阅读:5236)
  2. grep 正则表达式选项要记得转义    (阅读:5093)
  3. 正则表达式基础    (阅读:4944)
  4. 正则表达式的与或非    (阅读:4587)
  5. 学习Grep,Sed中的正则    (阅读:3910)
  6. URL正则表达式    (阅读:3479)
  7. 正则表达式简要入门    (阅读:3367)
  8. PHP 正则里面的两个重要技巧    (阅读:3363)
  9. 正则表达式简介及使用    (阅读:3190)
  10. 正则转义符汇总    (阅读:3196)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
  • 作者:Miller    来源: Miller
  • 标签: 正则
  • 发布时间:2011-09-04 23:35:10
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1