上一文《正则优化一则:CSS选择符匹配》中说到了如何优化一个正则在匹配成功时的效率,而实际上正则匹配有成功就会有失败,因此失败时的效率也是需要注意的。继续上文中的正则,分析了一下优化前和优化后表达式失败时的效率:
匹配文本:.a select,.b input,.b input[
优化前 优化后
优化前的表达式一共用了166步才完成匹配,优化后的表达式也是用了109步才完成匹配,虽然效率要高一些,但是相对于一共才28个字符的文本,总的效率还是不尽如人意。其实造成如此低效率的原因很简单:当引擎试图用表达式去匹配文本中最后一个"["时,会把之前所有已经成功匹配的字符一个一个的“吐”出来重新尝试匹配,这个尝试过程是指数级别的。因此有没有办法改造一下这个表达式,让引擎可以一组一组的“吐”出来,因为表达式(,\s*[.\w-][.\w\s\->+~]*)中并没有包括字符"[",如果引擎足够聪明就应该把这一组匹配集体“吐”出来,但是实际上却是上图的情况。
在尝试改进回溯状况的过程中发现了一个有趣的现象,在优化后的正则最后加上引号即表达式变成:
^\s*[.\w-][.\w\s\->+~]*(,\s*[.\w-][.\w\s\->+~]*)*"$
匹配结果如下:
新的表达式只用了21步就迅速的结束了匹配过程,相比之前的109步是个不小的进步。简单分析一下可以看出,新的表达式在回溯的时候是以组为单位进行回溯的,而不是之前的字符级别而且是双重循环,因此新的表达式结束的十分迅速。
进一步测试发现,加在表达式的最后一个字符(例如引号)必须是循环表达式中所不包含的,例如引号就不包含在(,\s*[.\w-][.\w\s\->+~]*),如果增加的字符包含在其中例如+号那么结果会和最初的表达式一样,会经过漫长的匹配后才失败。究其原因,目前还未找到合理解释,不过这也可以作为加速正则失败的一个参考案例。
同样,经过测试,添加引号后的正则完成的速度提升大概10%左右。围观地址: