高性能JavaScript系列: 算法和流程控制
1. 循环
循环性能
- 在Javascript提供中的循环类型中, 要慎用
for...in因为循环的每次迭代都会产生更多开销,for...in在每次迭代的时候回去搜索实例或原型属性 - 不要使用
for-in来遍历数组成员 - 如果循环类型与性能无关, 那么该如何选择? 那么我们要从 每次迭代处理的事务 和 迭代的次数 两方面来考虑
- 每次迭代处理的事务:
- 缓存 相同的值(每次迭代处理的事务), 减少访问次数
- 倒序遍历(如果可以的话)
- 每次迭代处理的事务:
for(let i=0; len = items.length; i<len; i++){
// 从这里我们缓存了items.length, 来减少每次对 items.length的访问
}
for(let i = items.length-1; i>=0; i--){
// 倒序的时候, 我们值访问了一次items.length, 然后每次只需查看是否i>=0 就可以了,
// 不用每次都访问items.length
}
forEach语句比普通的 for循环要 慢一些
2. 条件语句
switch 大多数情况下switch要比if-else要一些. 但只有当条件数量很大时, 区别是: 当条件数量增加的时候, if-else性能负担增加的成都比switch要多, 而且在js中 switch语句比较值的时候, 使用全等操作符, 不会发生类型转换的损耗. 有如下几种优化方式: a
-
把最可能出现的条件放到首位和前面(
vue中的diff算法用的也是这个), 把最大概率到最小概率的顺序排列. -
另一种减少条件判断的方法,
if-else组织成一些列的嵌套if-else, 在if-else中, 在分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 if (value ===6) {
return result6;
} else {
return result10;
}
可以这样做:
if(value < 3) {
if (value ===0) {
return result0;
} else if (value===1) {
return result1;
} else {
return result2;
}
} else {
if (value === 3) {
return result3;
} else if (value === 4) {
return result4;
} else {
}
....
}
假如我们的value===6那我们的 if-else 的查找次数要比第一种高
- 通过查找表替代
if-else当我们有大量离散值需要测试的时候,if-else和switch比使用查找表慢很多. javascript中可以使用数组和普通对象来构建查找表. 用过查找表访问数据比用if-else或switch快很多. 特别是在条件语句数量很大的时候. 例如:
// 我们将结果返回值先存入数组
var results = [result0, result1, result2, result3, result4];
// 通过(选项条件)直接返回结果
return results[value];
好处: 我们不用书写任何条件判断语句, 即使我们的候选值数增加, 几乎不会产生额外的性能开销. 当单个键和单个值之间存在逻辑映射时(正如上述的例子), 查找表的优势就能体现出来. 而if-else 和switch语句更适合每个选项都需要对应一个独特的动作或者一系列的动作.
3. 递归
递归可以让我们的问题简化,但是也会同时带来 stack overflow的问题, 通常如果我们遇到多层嵌套递归的时候, 会带来假死问题. 因此适当的优化递归也是有必要的
1. 迭代
因此当我们遇到调用栈溢出, 我们要考虑采用迭代的方式. 例如, 合并排序是最常见的利用递归实现的算法
function merge(left, right){
let 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 (item.length===1) {
return items;
}
let middle = Math.floor(item.length / 2);
let left = items.slice(0, middle);
let right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
这段代码 mergeSort()函数会频繁的自调用, 一个长度为n的数组最终会调用mergeSort() 2^(n-1)次, 这意味如果数组足够大, 会在js调用栈上产生溢出的错误. 这并不意味这个算法不正确, 只是说明递归不是最好的实现方式. 那么我们可以改为 迭代实现
fucntion mergeSort(items) {
if (items.length ==1) {
return items;
}
let work = [];
for (let i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]);
for (let lim = len; lim>1; lim = (lim+1)/2) {
for (let j = 0, k=0; k<lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = [];
}
return work[0];
}
Memoization
Memoization是一种避免重复工作的方法, 它缓存多次执行相同任务的结果, 为后续计算使用, 避免重复工作, 因为当重复递归调用的时候, 大量重复工作不可避免会发生.
function memoize(fundamental, cache) {
let cache = cache || {};
let shell = function(){
if(!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(arg);
}
return cache[arg];
}
return shell;
}
// 副作用: 会产生闭包, 造成内存泄漏, 看情况使用
小结
-
for,while和do-while循环性能特性相当, 并没有一种循环类型明显快或明显慢于其他类型 -
避免使用
for-in, 除非你需要遍历一个属性数量未知的对象 -
通常来说,
switch总是比if-else快, 但不总是最佳的解决方案 -
改善循环新能的最佳方式: 减少每次迭代的运算量和较少循环迭代次数
-
浏览器的调用栈大小限制了递归算法在js中的应用, 栈溢出的错误会导致其他代码中断运行