高性能JavaScript（算法和流程控制）

在大多与编程语言中，代码的执行时间大部分消耗在循环中，是提升性能必须关注的要点之一

 

循环的类型

for循环（它由四部分组成：初始化、前测条件、后执行体、循环体。）

for(var i = 0; i < 10; i++){

    doSomething();

}

可以将 var 改成 let 因为 var i会创建一个函数级/全局变量。

 

while循环（while循环是最简单的循环，由前测条件和循环体组成。）

var i = 0;

while（i < 10） {

    doSomething();

    i++;

}

任何for循环都能改成 while 反之亦然

 

do-while循环（由循环体和后测条件组成。）

var i = 0;

do {

    doSomething();

} while（i++ < 10） 

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

 

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

for(var prop in object){

    doSomething();

}

循环体每次运行时，prop会被赋值为object的一个属性/方法名（字符串），直到遍历完所有属性/方法才结束，所返回的属性包括对象实例以及从原型链中继承而来的属性。

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]))

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

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

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

    process(items[i])

}

这样就减少了查找属性的操作

 

倒序循环

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

for(var i = items.length; i--;){

    process(items[i])

}

 

减少迭代次数

减少迭代次数的典型方法“达夫设备（Duff's Device）”。是一种循环体展开技术，是在一次迭代中实际执行了多次迭代的操作。示例如下（感兴趣的同学可以自行百度查询达夫设备）

console.time(0)
var a = [0, 1, 2, 3, 4];
var sum = 0;
for(var i = 0; i < 5; i++)
  sum += a[i];
console.timeEnd(0) // 0: 0.011962890625ms

console.time(1)
var as = [0, 1, 2, 3, 4];
var sums = 0;
sums += as[0];
sums += as[1];
sums += as[2];
sums += as[3];
sums += as[4];
console.timeEnd(1) // 1: 0.010009765625ms

因为少作了多次的for循环，很显然这段代码比前者效率略高，而且随着数组长度的增加，少作的for循环将在时间上体现更多的优势。

var iterations = Math.floor(items.length / 8),
  startAt = items.length % 8,
  i = 0;

  do {
    switch(startAt) {
      case 0: process(items[i++]);
      case 7: process(items[i++]);
      case 6: process(items[i++]);
      case 5: process(items[i++]);
      case 4: process(items[i++]);
      case 3: process(items[i++]);
      case 2: process(items[i++]);
      case 1: process(items[i++]);
    }
    startAt = 0;
  } while(--iterations);

看switch/case语句，因为没有写break，所以除了第一次外，之后的每次迭代实际上会运行8次！Duff's Device背后的基本理念是：每次循环中最多可调用8次process()。循环的迭代次数为总数除以8。由于不是所有数字都能被8整除，变量startAt用来存放余数，便是第一次循环中应调用多少次process()。

此算法一个稍快的版本取消了switch语句，将余数处理和主循环分开：

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

尽管这种方式用两次循环代替了之前的一次循环，但它移除了循环体中的switch语句，速度比原始循环更快。

 

基于函数的迭代

数组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
}

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次，可以改写为

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更优，特别是大量离散数值的情况。使用查找表不仅能提高性能还能答复降低圈复杂度和提高可读性，而且非常方便扩展。

例如上面的示例改为查找表：

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: 不显示调用栈溢出错误

try-catch 可以捕获。

 

递归模式

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([]); // 如果数组长度为奇数
  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

就是缓存前一次的计算结果避免重复计算。

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

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

三个阶乘，共需要执行factorial函数18次。其实计算6的阶乘的时候，已经计算过5和4的阶乘。特别是4的阶乘被计算了3次。

利用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的阶乘直接中缓存里取出结果。

 

小结：

 

JavaScript 和其它编程语言一样，代码的写法和算法会影响运行时间。与其它语言不同的是，JavaScript可用资源有限，因此优化技术更为重要。

 

1.for、while、do-while 循环性能相当，并没有一种明显快于或鳗鱼其它类型。

 

2.避免使用 for-in 循环，除非你需要遍历一个属性数量未知的对象。

 

3.通常改善性能的最佳方式是减少每次迭代的运算量和减少循环迭代次数。

 

4.通常来说，switch 总是比 if-else 快，但并不是最佳解决方案，当判断条件较多时，使用查找表比 if-else 和 switch 更快。

 

5.浏览器的调用栈大小限制了递归算法在JavaScript中的应用，栈溢出错误会导致其它代码中断运行。

 

6.可以使用迭代算法，或使用 Memoization 来避免重复计算。

 

运行的代码量越大，使用这些策略所带来的性能提升也越明显。