forEach优化

时常、经常,我们需要循环遍历数组或者HTMLCollection、NodeList等伪数组,让其每一项执行同一个函数。于此,可以考虑封装一个forEach函数。

function forEach1(arr,func){
    for(var i = 0; i < arr.length; i++){
        func(arr[i]);
    }
}

而针对这个循环,需要做一些性能等等方面的优化。现在,就来仔细探讨一下。
下面是相同的准备,对于同一个数组(共有10,000,001项),循环遍历这个数组,比较一下它们所花费的时间。测试环境:Chrome 版本 31.0.1650.63 m 。测试次数:2次,测试结果仅供参考(不准确)。

var arr = [],
    time1 =  new Date();
arr[0] = 0;
arr[10000000] = 10000000;
function process1(item){
    if(item === 100000000){
        var time2 = new Date();
        console.log(time2 - time1);
    }
}

PS:Firefox所花费的时间是Chrome的十倍,Chrome花1000ms,相应的FF将近开销10000ms,着实让人无语,也就不在FF上测了。下面正式开始:

forEach1(arr,process1);

开销:1328ms 1328ms

我们平常,都习惯用for(var i = 0; i < arr.length; i++)这样的循环,可曾想过,每一次遍历,循环体的执行终止条件都需要去访问arr的length属性,并且,假使,arr的length更新了。相应的执行终止条件也就改变了。如下就是一个无限循环。

var aTest = [1];
forEach1(aTest,function(){
    aTest.push(1);
});

针对这类情况,也为了避免对length属性的访问,可以用一个变量len将length属性的值存起来len = arr.length

function forEach2(arr,func){
    for(var i = 0,len = arr.length; i < len; i++){
        func(arr[i]);
    }
}
forEach2(arr,process1);

开销:1328ms 1328ms 性能貌似没有提升,当然,这是Chrome上的,其它浏览器你可以自行测试下。

减值迭代:在很多情况下使用减值迭代,从最大值开始,在循环中不断减值的迭代器更加高效。

function forEach3(arr,func){
    for(var i = arr.length - 1; i >= 0; i--){
        func(arr[i]);
    }
}

相应的,我们修改下测试函数process1,判断条件更改为item === 0:

function process2(item){
    if(item === 0){
        var time2 = new Date();
        console.log(time2 - time1);
    }
}
forEach3(arr,process2);

开销:1312ms 1344ms

简化终止条件:由于每次循环过程都会计算终止条件,所以,尽量要避免属性查找或其他O(n)操作。这里,我们有两个方法:

  1. 将执行终止条件和更新语句合并起来。倒计数到0,更有效地进行比较。
function forEach4(arr,func){
    for(var i = arr.length; i--; ){
        func(arr[i]);
    }
}
forEach4(arr,process2);

开销:1313ms 1328ms

或者采用while语句。

function forEach4(arr,func){
    var i = arr.length;
    while (i--) {
        func(arr[i]);
    }
}
forEach4(arr,process2);

开销:1313ms 1328ms

2.使用后测试循环do-while,避免最初终止条件的计算。

function forEach5(arr,func){
    var i = arr.length - 1;
    if(i > -1){
        do{
            func(arr[i]);
        }while(--i >= 0);
    }
}
forEach5(arr,process2);

开销:1313ms 1312ms

除此之外,针对大量的循环,可以展开(消除)循环,消除建立循环和处理终止条件的额外开销。这是一种称为Duff装置的技术。

function duff1(arr,process){
    var iterations = Math.ceil(arr.length / 8),
        startAt = arr.length % 8,
        i = 0;
    do {
        switch(startAt) {
            case 0:process(arr[i++]);
            case 7:process(arr[i++]);
            case 6:process(arr[i++]);
            case 5:process(arr[i++]);
            case 4:process(arr[i++]);
            case 3:process(arr[i++]);
            case 2:process(arr[i++]);
            case 1:process(arr[i++]);
        }
        startAt = 0;
    } while (--iterations > 0);
}

将arr的项,8个一组进入do-while循环体,注意:switch语句中没有break。而针对duff1,也有一个优化,来自于Andrew B.King所著《Speed Up Your Site》,将do-while循环分成两个单独的循环。

[lang:JavaScript]
function duff2(arr,process){
    var iterations = Math.floor(arr.length / 8),
        leftover = arr.length % 8,
        i = 0;
    if (leftover > 0){
        do {
            process(arr[i++])
        } while (--leftover > 0);
    }
    do {
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
            process(arr[i++]);
    } while (--iterations > 0);
}

此文文献参考:《JavaScript高级程序设计 第三版》、《JavaScript Patterns》。