前言

代码的组织结构和解决具体问题的思路是影响代码性能的主要因素。程序运行速度与代码量的多少没有必然关系。
这里讨论的技术并不限于JavaScript，同样适用于其他编程语言。

循环

在大多与编程语言中，代码的执行时间大部分消耗在循环中，是提升性能必须关注的要点之一。在JavaScript中，死循环或长时间运行的循环还会严重影响用户体验，所以必须充分重视循环的实现。

循环的类型

在ECMA-262中定义了四种循环类型

1、for循环

for循环是最常见的循环类型。它由四部分组成：初始化、前测条件、后执行体、循环体。如下示例：

for(var i = 0; i < 10; i++){
    doSomething();
}
// i=0,是初始化
// i<10,是前测条件
// i++是后执行体
// {}内是循环体

for循环的执行顺序如下：

1. 初始化
2. 前测条件判断，true继续执行，false结束
3. 循环体执行
4. 后执行体执行，返回2。

从for的执行顺序我们可以看出，i的值在循环结束时是10.

注意：由于JavaScript中没有块级作用域，所以var i实际可能是函数级/全局变量。所以lint检查时，同一个函数里的两个及以上的for循环，同时定义var i时，会报'i' used outside of binding context. (block-scoped-var)错误。

2、while循环

while循环是最简单的循环，由前测条件和循环体组成。如下示例

var i = 0;
while（i < 10） {
    doSomething();
    i++;
}

这里i=0可以理解为初始化，因为i未声明，前测条件为false。

3、do-while循环

由循环体和后测条件组成。如下示例

var i = 0;
do {
    doSomething();
} while（i++ < 10） 

在do-while循环中，至少会执行一次循环体，与其他三种有明显的区别。

4、for-in循环

for-in循环是比较特殊的循环类型。它可以遍历一个对象的属性/方法名。如下示例：

for(var prop in object){
    doSomething();
}

循环体每次运行时，prop会被赋值为object的一个属性/方法名（字符串），直到遍历完所有属性/方法才结束。fori-in循环遍历的属性/方法包括对象实例属性/方法和原型链中继承的属性/方法。
注意：如果数组有追加属性/方法，那么遍历数组时就会出错。所以编程规范中强调数组遍历不要使用for-in

var array = [1,2,3]
for(var prop in array) {
    console.log(prop)
}
// 打印结果 1 2 3
Array.prototype.isNumber = function(){
    return true;
}
for(var prop in array) {
    console.log(prop)
}
// 打印结果 1 2 3 isNumber
var object ={
    a:1,
    b:2,
    f1:function(){}
}
for(var prop in object) {
    console.log(prop)
}
// 打印结果 a b f1

循环性能

因为for-in循环每次迭代操作都要搜索实例或原型的属性/方法，所以其性能明显低于其他三种循环。其他三种循环类型则没有明显的性能差异。所以除非必要，否则避免使用for-in循环。
影响循环的性能主要是如下两个因素：

1. 每次迭代处理的事务
2. 迭代的次数

减少这两者中一个或者全部的时间开销，就能提升整体性能。下面分别就这两个因素进行说明。

减少迭代工作量

如果每次循环迭代要执行很多操作，花很长时间，那么整个循环必然需要更多时间才能完成。
典型的循环示例如下：

for(var i=0; i < items.length; i++){
    process(items[i])
}

在上面的循环中，每次迭代执行时会产生如下操作：

1. 在控制条件中查找一次属性（items.length）
2. 在控制条件中查找一次比较（i < items.length）
3. 一次比较操作，查看控制条件是否为true（i < items.length == true）
4. 一次自增操作（i++）
5. 一次数组查找（items[i]）
6. 一次函数调用 (process(items[i]))

如此简单的循环中，即使代码不多，也要进行许多操作。下面我们看看，如何减少迭代执行时的操作。

减少对象成员及数组项的查找次数

例如之前提到过的局部变量替换成员函数或者属性。这样修改后每次控制条件中直接跟局部变量len比较，而不用去读取items.length属性。

for(var i=0， len = items.length; i < len; i++){
    process(items[i])
}

倒序循环

通过点到数组的顺序，减少控制条件中的查找属性和比较操作。

for(var i = items.length; i--;){
    process(items[i])
}

当然如果实际需求对顺序有要求，就不能用此方法了。

利用数组取值结果进行条件判断

JS在赋值时会自动返回结果，利用这个返回结果进行条件判断，从而使得条件判断和数组取值合二为一，达到减少操作的目的。

for(var i=0, item; item = items[i]; i++){
    process(item)
}

提示：当循环复杂度为O(n)时，减少每次迭代的工作量最有效，当复杂度大于O(n)时，建议减少迭代次数。

减少迭代次数

减少迭代次数的典型方法“达夫设备（Duff's Device）”。是一种循环体展开技术，是在一次迭代中实际执行了多次迭代的操作。示例如下（原书上的例子是错误的）：

var i = items.length % 8;
while(i){
    process(items[--i])
}
i = items.length
var j = Math.floor(items.length / 8)
while(j--){
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
}

基于函数的迭代

数组forEach方法，遍历数组的所有成员，并在每个成员上执行一次函数。示例如下：

items.forEach(function (value, index , array) {
    process(value)
})

三个参数分别是：当前数组项的值，索引和数组本身。
各大浏览器都原生支持该方法，同时各种JS类库也都由类似的实现。但由于要调用外部方法，带来了额外的开销，所以性能比之前介绍的集中循环实现慢很多。

条件语句

if-else对比switch

由于各浏览器针对if-else和switch进行了不同程度的优化，很难简单说那种方式更好，只有在判断条件数量很大时，switch的性能优势才明显。更多的时候是从易读性方面考虑。一般来说判断条件较少时使用if-else更易读，当条件较多时switch更易读。

优化if-else

同样是使用if-else，实际也存在很大的性能差距。这是因为到达正确分支时，所需要执行的判断条件数量不同造成的。主要的的优化方法有如下几种：

1. 最可能出现的条件放首位。

if (value < 5) {
    //dosomthing
} else if (value >5 && value < 10) {
    //dosomthing
} else {
    //dosomthing
}

如果value大部分情况下小于5，此时只需要执行一次条件判断。如果value大部分大于10，那么需要执行两次条件判断，造成性能下降。

2. 把if-else组织成一系列嵌套的if-else，减少每个分支达到的判断次数。

if (value == 0) {
    return result0
} else if (value == 1) {
    return result1
}  else if (value == 2) {
    return result2
}  else if (value == 3) {
    return result3
}  else if (value == 4) {
    return result4
}  else if (value == 5) {
    return result5
} else {
    return result
}

上述条件语句最多要判断6次，如果value是均匀分布的，那么必然会增加平均执行时间。采用类似二分法的方式，进行嵌套，就可以有效减少判断次数。改进后代码如下：

if (value < 3) {
    if (value == 0) {
        return result0
    } else if (value == 1) {
        return result1
    } else {
        return result2
    }
} else {
    if (value == 3) {
        return result4
    } else if (value == 4) {
        return result4
    } else if (value == 5) {
        return result5
    }  else {
        return result
    }
}

此时最多判断次数变为4次，减少了平均执行时间。

查找表

有时候使用查找表的方式比if-else和switch更优，特别是大量离散数值的情况。JS中可以很方便的使用数组和对象来构建查找表。使用查找表不仅能提高性能还能答复降低圈复杂度和提高可读性，而且非常方便扩展。
例如上面的示例改为查找表：

var results = [result0,result1,result2,result3,result4,result5,result]
return result[value]

这里示例是数值，调用函数也同样适用，例如

var fn = {
    1: function(){/* */},
    2: function(){/* */},
    3: function(){/* */}
}
fn[value]()

递归

递归可以把复杂的算法变得简单。很多传统算法就是用递归实现的，例如阶乘函数：

function factorial (n) {
    if (n == 0) {
        return 1
    } else {
        return n * factorial(n -1)
    }
}

但是递归函数存在着终止条件不明确或缺少终止条件，导致函数长时间运行，使得用户界面处于假死状态。而且递归还可能遇到浏览器的“调用栈大小限制（Call stack size limites）”。所以需要慎用。

调用栈限制

JS引擎支持的递归数量与JS调用栈大小直接相关。只有IE的调用栈与系统空闲内存有关，其他浏览器都是固定数量的调用栈限制。需要注意的是各浏览器和版本调用栈数量大小差别很大。
当使用太多的递归（或者死循环），甚至超过最大调用栈限制时，就会出现调用栈异常。各浏览器报错信息如下：

IE: Stack overflow at line x
Firefox: Too much recursion
Safari: Maximum call stack size exceeded
Opera: Abort (control stack overflow)
Chrome: 不显示调用栈溢出错误

同时各浏览器对该错误的处理方式也是不同的，请直接看书中描述，这里不再赘述。

递归模式

递归有两种模式：

1. 函数调用自身，如之前说的阶乘。
2. 隐伏模式，即循环调用。A调用B，B又调用A，形成了无限循环，很难定位。
   由于递归的这些隐藏危害，建议使用迭代、Memoization替代。

迭代

任何递归实现的算法，同样可以使用迭代来实现。迭代算法通常包含几个不同的循环，分别对应计算过程的不同方面，这也会引入他们自身的性能问题。然而，使用优化后的循环替代长时间运行的递归函数可以提升性能。
以合并排序算法为例

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 middle = Math.floor(items.length / 2),
    left = items.slice(0, middle),
    right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

此算法中mergeSort存在频繁的递归调用，当数组长度为n时，最终会调用2*n-1次，很容易造成栈溢出错误。
使用迭代改进此算法。mergeSort代码如下：

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([]); //in case of odd number of items
  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] = []; //in case of odd number of items
  }
  return work[0];
}

Memoization

就是缓存前一次的计算结果避免重复计算。继续以阶乘为例，如下三个阶乘，共需要执行factorial函数18次。其实计算6的阶乘的时候，已经计算过5和4的阶乘。特别是4的阶乘被计算了3次。

var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);

我们利用Memoization技术重写factorial函数，代码如下：

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];
}

这是再执行6,5,4的阶乘，实际只有6的阶乘进行了递归计算，共执行factorial函数8次。5和4的阶乘直接中缓存里取出结果。