最近在看《高性能 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];
}