高性能javaScript（四）——算法和流程控制

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

• for、while和do-while循环性能特性相当，并没有一种循环类型明显快于或慢于其他类型。
• 避免使用for-in循环，除非你需要遍历一个属性未知的对象。

    //除非获得属性未知，否则不适用以下方式
    for(var prop in object) {
        //循环主体
    }
    
    //使用以下方式代替上述代码
    var props = ["prop1","prop2"],
        i = 0;
    
    while(i < props.length) {
        process(object[props[i++]]);
    }

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

//原始版本
for(var i=0; i<items.length;i++){
    process(items[i]);
}

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

var k=0;
do {
    process(items[k++]);
} while(k < items.length);


//将length保存到临时变量，并使用反转，JavaScript倒序循环会略微提升性能
for(var i=items.length;i--;){
    process(items[i]);
}

var j = items.length;
while(j--) {
    process(items[j]);
}

var k = items.length-1;
do {
    process(items[k]);
}

使用“Duff's Device”，一种循环体展开技术，它使得一次迭代中实际上执行了多次迭代的操作。

//credit: Jeff Greenberg
//只有在迭代次数大于1000时，执行效率才会明显提升
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++l);
        case 3: process(items[i++]);
        case 2: process(items[i++]);
        case 1: process(items[i++]);
    }
    startAt =0;
} while (--iterations);

//取消switch语句的稍快版本
var len = items.length;
var i = len % 8;
while(i) {
    process(items[len--]);
}

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

• 通常来说，switch总是比if-else快，但并不总是最佳解决方案。

//当值为离散值时使用swith，连续值使用二分法优化if-else
if(value < 6){
    
    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 {
            return result5;
        }
    }
    
} else {
    
    if(value < 8){
        if(value == 6) {
            return result6;
        } else {
            return result7;
        }
    } else {
        if(value == 8) {
            return result8;
        } else if(value == 9) {
            return result9;
        } else {
            return result10;
        }
    }
    
}

• 在判断条件较多时，使用查找表比if-else和switch更快。

//使用查找表
var results = [result0,result1,result2,result3,result4,result5,result6,
                result7,result8,result9,result10];
return results[value];

• 浏览器的调用栈大小限制了递归算法在JavaScript中的应用；栈溢出错误会导致其他代码中断运行。
• 如果遇到栈溢出错误，可将方法改为迭代算法，或使用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));
}

//使用迭代避免栈溢出
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 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];
}

//以下为通用版本，但只能缓存特定值，若需缓存全部值请使用上面的版本
function memoize(fundamental,cache){
    cache = cache || {};
    
    var shell = function(arg){
        if(!cache.hasOwnProperty(arg)){
            cache[arg] = fundamental(arg);
        }
        return shell;
    }
}