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が、何らかの理由でこの関数を作成するときに使用しました。

これら 2 つのスタイルのパフォーマンスに大きな違いがある理由を誰か説明できますか?

4

4 に答える 4

28

各反復で何が異なるかを見てください。

for( var i = 0; i < p1.length; i++ )
  1. チェックするi < p1.length
  2. i1ずつ増加

非常にシンプルで高速です。

これについて、各反復で何が起こっているかを見てみましょう。

for( var i in p1 )

繰り返す

  1. [[Enumerable]] 属性が true である obj の次のプロパティの名前を P とします。そのようなプロパティがない場合は、(normal、V、empty) を返します。

列挙可能なオブジェクト内の次のプロパティを見つける必要があります。配列を使用すると、これは単純な整数のインクリメントによって実現できることがわかります。次の列挙可能なアルゴリズムを見つけるアルゴリズムは、任意のオブジェクトとそのプロトタイプ チェーン キーで動作する必要があるため、それほど単純ではない可能性があります。

于 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 ループは、オブジェクト内のすべてのプロパティを単純にループします。ループに必要な反復回数を指定していないため、単純に「推測」し、オブジェクトがなくなるまで続行します。

2 番目のループでは、すべての可能な変数を指定しています... a) 開始点、b) ループが停止するまでの反復回数、c) 開始点のカウントを増やします。

このように考えることができます... For/In = 反復回数を推測します。指定している For(a,b,c)

于 2012-11-30T13:13:28.570 に答える