高性能JavaScript系列: 算法和流程控制

1. 循环

循环性能

• 在Javascript提供中的循环类型中, 要慎用for...in 因为循环的每次迭代都会产生更多开销, for...in 在每次迭代的时候回去搜索实例或原型属性
• 不要使用for-in来遍历数组成员
• 如果循环类型与性能无关, 那么该如何选择? 那么我们要从 每次迭代处理的事务 和 迭代的次数 两方面来考虑
  • 每次迭代处理的事务:
    1. 缓存 相同的值(每次迭代处理的事务), 减少访问次数
    2. 倒序遍历(如果可以的话)

    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

1. 把最可能出现的条件放到首位和前面(vue中的diff算法用的也是这个), 把最大概率到最小概率的顺序排列.

2. 另一种减少条件判断的方法, 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 的查找次数要比第一种高

1. 通过查找表替代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中的应用, 栈溢出的错误会导致其他代码中断运行