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

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

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

 

优化前                               优化后

 

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

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

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

匹配结果如下:

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

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

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

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

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="">