一、算法和流程控制
代码的组织结构和解决具体问题的思路是影响代码性能的主要因素。
1.1 循环性能
JavaScript
中有5
种循环,分别是for
,while
,do while
,for in
,for of
,其中for of
为ES6
之后出来的,这里暂不讲解。前面四种循环中,for in
的速度为其他循环的1/7
,所以遍历object
时尽量采用for
去遍历。除此之外,我们想要提高循环性能有以下2个着手点:
- 每次迭代处理的事务
- 迭代次数
通过减少上述2
点中的一个或者全部时间开销,便可以提高循环性能。
1.1.1 优化建议
这里书上的建议是:当时间复杂度大于O(n)
时,着重减少迭代次数,当时间复杂度小于等于O(n)
时,着重减少每次迭代要处理的事务。另外,Array
还具有基于函数的迭代比如Array.prototype.forEach
,但是基于函数的迭代要比循环慢大约8
倍,不过好处是方便,所以当我们的代码有严格的性能要求时,尽量用循环而不是函数迭代。
1.2 条件语句
JavaScript
中有两种条件语句:if else
和switch
。书上的结论是:当条件明显比较多的时候,使用switch
更加好,因为switch
代码可读性更高,并且大多数浏览器都对switch
做了优化,使用branch table
(分支表)索引进行优化,并且switch
判断是用的全等,节省了类型转换带来的性能损耗。
1.2.1 优化建议
-
if else
主要从减少判断次数着手,比如:(1)将最可能的条件放在前面;(2)对离散值进行分段(类似数组二分法); - 当需要测试的离散值特别多时应该避免使用分支结构,而是采用
lookup table(查找表)
1.3 递归
递归可以把复杂的算法变得简单,但是如果未明确终止条件或者运行环境对调用栈的大小限制比较多,就会导致递归出现栈溢出的问题。
1.3.1 优化建议
任何能用递归实现的逻辑都可以用迭代实现,并且迭代减少了调用函数时产生的额外开销,占用更少的内存,所以我们尽量使用迭代。
二、正则表达式优化
目前正则表达式引擎主要有两种,DFA(确定型有穷自动机)
和NFA(非确定型有穷自动机)
,DFA
规定不回溯,不会匹配同一位置或字符多次,所以速度较快,但是也因为状态有限,所以无法完成反向引用和组捕获;NFA
采用了回溯算法,会按照既定顺序挨个匹配所有可能,所以可能会匹配一个字符或位置多次,所以速度会比较慢,但是支持捕获等操作;现在高级语言一般都采用的是NFA
引擎。
2.1 正则表达式工作原理
下面的步骤为再浏览器中使用正则表达式的工作原理
- 编译,浏览器验证正则表达式对象,然后转为原生代码程序;
-
设置起始位置,即指定字符串的起始搜索位置,当刚开始匹配时,起始位置为字符串的首个位置或者
match/exec
指定的lastIndex
,当从匹配失败后回溯到该位置时,起始位置则为该位置的下一个字符; - 匹配每个正则表达式字元,诸葛检查文本和正则表达式模式;
- 匹配成功或者失败,如果在当前位置发现了一个完全匹配,那么正则表达式宣布不匹配成功,如果所有的路径都匹配失败,那么会回退到第二步,到下一个字符处重新开始匹配,直到成功或者全部失败。
2.2 影响性能的因素
影响正则表达式性能的关键因素就是回溯。过多的,无意义的的回溯是造成正则表达式性能下降的元凶!一般以下两种情况会造成回溯:
- 分支与回溯,分支表达式造成的回溯;
- 重复与回溯,贪婪量词或者范围过大的匹配可能会造成回溯。
2.3 优化建议
既然造成性能下降的主要因素是回溯,那么优化的主要着手点就是减少不必要的回溯。
2.3.1 优化分支结构
目标字符串:my blackcat
, 正则表达式:/^my\s(blackhat|blackcat)$/
,正则表达式匹配步骤如下:
优化后为:/^my\sblack(h|c)at$/
,匹配步骤如下:
tips:
- 与
if
表达式一样,可能的分支放在前面; - 尽可能减少分支里内容,尤其是无意义的重复内容;
- 尽量不使用顶层的分支结构,正则以确定的元字符开始;
- 甚至可以将分支结构优化掉以至于不使用分支结构
2.3.2 具体化匹配范围
目标字符串: <script>I am a piece of javascript.</script>
,正则表达式为:/^<script>.?<\/script>$/
,匹配步骤如下:
优化后为:/^<script>[^<]*<\/script>$/
,匹配步骤如下:
tips:
尽可能具体化分隔符之间的字符串匹配模式,使用更为精准的元字符:
- 使用正确的边界匹配器(^、$、\b、\B等),限定搜索字符串位置;
- 使用具体的元字符、字符类(\d、\w、\s等) ,少用”.”字符;
- 使用正确的量词(+、*、?、{n,m}),如果能够限定长度,匹配最佳;
- 使用非捕获组、原子组,减少没有必要的字匹配捕获用(?:);
2.3.3 使用预查和反向引用的模拟原子组
一些正则表达式引擎支持一种名为原子组
的特性,即该捕获组具有原子性
,表示该捕获组表示为一个整体,不可再拆分,当回溯的时候,会直接略过原子组,把原子组当作元字符
看待。示例如下:
目标字符串:<html>123woodman</html>
,正则表达式:<html>[^<]*</html>
,使用模拟原子组:<html>(?=[^<]*)\1</html>
。
匹配过程如下:
预查-优化.png
从结果来看似乎并没有什么效果,甚至是负优化,但是如果我们尝试匹配:<html>123woodman</html
,结果如下:
预查-结束-优化.png
可以看到使用模拟原子组再回溯的时候并没有进入捕获组以至于更早地退出了匹配,节省了时间。
2.3.4 使用非捕获组
使用非捕获组(?:exp)
替代(exp)
,有时我们并不需要反向引用捕获组,所以应该使用非捕获组,避免浪费内存。
参考文献
[1] 正则表达式原理
[2] 正则表达式优化
[3] 《高性能JavaScript》Nicolas C. Zakas 著
网友评论