22

我使用 kmean 算法聚集了大约 40000 个点。在程序的第一个版本中，我这样写了欧几里得距离函数

var euclideanDistance = function( p1, p2 ) { // p1.length === p2.length == 3
    var sum = 0;
    for( var i in p1 ){
        sum += Math.pow( p1[i] - p2[i], 2 );
    }
    return Math.sqrt( sum );
};

整个程序执行速度很慢，平均需要 7 秒。经过一些分析后，我像这样重写了上面的函数

var euclideanDistance = function( p1, p2 ) { // p1.length === p2.length == 3
    var sum = 0;
    for( var i = 0; i < p1.length; i++ ) {
        sum += Math.pow( p1[i] - p2[i], 2 );
    }
    return Math.sqrt( sum );
};

现在这些程序平均需要大约 400 毫秒。这是一个巨大的时间差异，只是因为我编写 for 循环的方式。我通常不对for..in数组使用循环，但出于某种原因，我在编写此函数时使用了它。

有人能解释一下为什么这两种风格在性能上有这么大的差异吗？

4

4 回答 4

28

查看每次迭代中发生的不同情况：

for( var i = 0; i < p1.length; i++ )
  1. 检查是否i < p1.length
  2. 加i一

非常简单和快速。

现在看看每次迭代中发生了什么：

for( var i in p1 )

重复

  1. 令 P 为 obj 的 [[Enumerable]] 属性为 true 的下一个属性的名称。如果没有这样的属性，返回（正常，V，空）。

它必须在可枚举的对象中找到下一个属性。使用您的数组，您知道这可以通过简单的整数增量来实现，其中查找下一个可枚举的算法很可能不是那么简单，因为它必须处理任意对象及其原型链键。

于 2012-11-30T13:26:10.437 回答
9

附带说明一下，如果您缓存 p1 的长度：

var plen = p1.length;
for( var i = 0; i < plen; i++ )

你会得到轻微的速度增加。

...如果你记住这个函数，它会缓存结果，所以如果用户尝试相同的数字，你会看到速度大幅提升。

var eDistance = memoize(euclideanDistance);  

function memoize( fn ) {  
    return function () {  
        var args = Array.prototype.slice.call(arguments),  
            hash = "",  
            i = args.length;  
        currentArg = null;  
        while (i--) {  
            currentArg = args[i];  
            hash += (currentArg === Object(currentArg)) ?  
            JSON.stringify(currentArg) : currentArg;  
            fn.memoize || (fn.memoize = {});  
        }  
        return (hash in fn.memoize) ? fn.memoize[hash] :  
        fn.memoize[hash] = fn.apply(this, args);  
    };  
}

eDistance([1,2,3],[1,2,3]);
eDistance([1,2,3],[1,2,3]); //Returns cached value

信用：http ://addyosmani.com/blog/faster-javascript-memoization/

于 2012-11-30T13:46:53.580 回答
6

首先，对于 for/in 和数组，您应该意识到这一点。如果你知道你在做什么，没什么大不了的。

我运行了一些非常简单的测试来显示不同循环之间的性能差异：http: //jsben.ch/#/BQhED

这就是为什么更喜欢对数组使用经典的 for 循环。

于 2012-11-30T13:34:12.010 回答
0

For/In 循环简单地遍历对象中的所有属性。由于您没有指定循环需要进行的迭代次数，因此它只是“猜测”它，并继续下去，直到没有更多对象为止。

在第二个循环中，您指定了所有可能的变量... a)a 起点，b) 循环在停止之前应该进行的迭代次数，c) 增加起点的计数。

你可以这样想... For/In = 猜测迭代次数，你指定的 For(a,b,c)

于 2012-11-30T13:13:28.570 回答