最近在看《高性能 JavaScript》,讲了一章节——算法和流程控制,现在来做一下记录。

循环类型

  1. 标准for循环

    1
    2
    3
    for (var i=0; i<10; i++){
    // 循环体
    }
  2. while循环
    前测循环

    1
    2
    3
    4
    var i = 0;
    while (i < 10){
    // 循环体
    }
  3. do-while循环
    后测循环

    1
    2
    3
    4
    var i = 0;
    do{
    // 循环体
    }while (i++ < 10)
  4. for-in循环
    这四种循环体中,for-in 循环明显要慢

    1
    2
    3
    for (var prop in object){
    // 循环体
    }

循环性能

提高循环的整体性能,考虑一下两个因素:

  1. 减少迭代的工作量
  2. 减少迭代次数 (如: “达夫设备”

基于函数的迭代

ECMA-262 标准第四版引入了一个新的原生数组方法: forEach()。
但是它比基于循环的迭代要慢一些。

条件语句

  1. if-else
  2. switch

条件数量越大,越倾向于使用 switch。
大多数情况下 switch 比 if-else 运行得要快,但只有当条件数量很大时才快得明显。

优化 if-else

if-else 中的条件语句应该总是按照从最大概率到最小概率的顺序排列,以确保运行速度最快;
把 if-else 组织成一系列嵌套的 if-else 语句。

查找表

JavaScript 中可以使用数组和普通对象来构建查找表,通过查找表访问数据比用 if-else 或 switch 快很多,特别是在条件语句数量很大的时候。
(没想到我误打误撞,在写项目的时候,喜欢用 Array 代替 if-else、switch 来进行查找判断。因为感觉这样也会比写条件判断简洁好看。)

递归

使用递归可以吧复杂的算法变得简单。有些传统算法正式使用递归实现的,比如阶乘函数:

1
2
3
4
5
6
7
function factorial(n){
if (n === 0){
return 1;
} else {
return n * factorial(n-1);
}
}

但是有潜在的问题:

  1. 终止条件不明确或缺少种植条件会导致函数长时间运行,并使得用户界面处于假死状态;
  2. 还可能遇到浏览器的“调用栈大小限制”。

另外,如遇下列情况

1
2
3
var anotherFactorial = factorial;
factorial = null;
anotherFactorial(4); //Uncaught TypeError: factorial is not a function

可以使用 argument.callee

1
2
3
4
5
6
7
function factorial(n){
if (n === 0){
return 1;
} else {
return n * argument.callee(n-1);
}
}

但是严格模式下,不可以通过脚本访问 argumen.callee,会导致错误。
但是可以使用命名函数表达式来达成相同的结果。

1
2
3
4
5
6
7
var factorial = (function f(num){
if (num === 0){
return 1;
} else {
return num * f(num-1);
}
})

调用栈限制

JavaScript 引擎支持的递归数量与 JavaScript 调用栈大小直接相关。只有 IE 例外,它的调用栈与系统空闲内存有关,而其它所有浏览器都有固定数量的调用栈限制。

递归模式

  1. 直接递归模式

    1
    2
    3
    4
    function recurse(){
    recurse();
    }
    recurse();
  2. 隐伏模式

    1
    2
    3
    4
    5
    6
    7
    function first(){
    second();
    }
    function second(){
    first();
    }
    recurse();

最常见的导致栈溢出的原因是不正确的终止条件,因此定位模式错误的第一步是验证终止条件。
或是算法中包含太多层递归,为了能在浏览器中安全地工作,建议改用迭代、Memoization、或者结合二者使用。

迭代

例如,常见的合并排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function merge(left,right){
var result = [];
while(left.length>0 && right.length>0){
if(left[0] < right[0]){
result.push(left.shift());
}else{
result.push(right.shift())
}
}
return result.concat(left).concat(right);
}
function mergeSort(items){
if(items.length == 1){
return items;
}
var work = [];
for( var i=0,len=items.length; i<len; i++){
work.push([items[i]])
}
work.push([]);
for(var lim=len; lim>1; lim=(lim+1)/2){
for (var j=0,k=0; k<lim; j++, k+=2){
work[j] = merge(work[k],work[k+1]);
}
work[j] = [];
}
return work[0];
}

Memoization

一种避免重复工作的方法,它缓存前一个计算结果供后续计算使用,避免了重复工作。

1
2
3
4
5
6
7
8
9
10
11
12
function memfactorial(n){
if(!memfactorial.cache){
memfactorial.cache = {
"0":1,
"1":1
}
}
if(!memfactorial.cache.hasOwnProperty(n)){
memfactorial.cache[n] = n * memfactorial(n-1);
}
return memfactorial.cache[n];
}