0

Webページのタグ内に次のコードがあります<script>。他には何もありません。私は現在それをオンラインで持っていないのではないかと思います。ご覧のとおり、2つの異なる方法で、200万未満のすべての素数を合計し、平均でかかった時間を計算します。変数howOftenはこれを何度も行うために使用されるため、平均化できます。私が困惑しているのはhowOften == 1、方法2の方が速いのですがhowOften == 10、方法1の方が速いということです。この違いは重要であり、F5を数回押しても保持されます。

私の質問は単純です：どうしてですか？

（この投稿は、alfの提案を組み込むように編集されています。しかし、それは違いはありませんでした。私は今、非常に困惑しています。）

（再編集：howOften1000以上の場合、時間は安定しているように見えます。Alfの答えは正しいようです。）

function methodOne(maxN) {
    var sum, primes_inv, i, j;

    sum = 0;
    primes_inv = [];
    for ( var i = 2; i < maxN; ++i ) {
        if ( primes_inv[i] == undefined ) {
            sum += i;
            for ( var j = i; j < maxN; j += i ) {
                primes_inv[j] = true;
            }
        }
    }
    return sum;
}

function methodTwo(maxN) {
    var i, j, p, sum, ps, n;

    n = ((maxN - 2) / 2);
    sum = n * (n + 2);
    ps = [];
    for(i = 1; i <= n; i++) {
        for(j = i; j <= n; j++) {
            p =  i + j + 2 * i * j;
            if(p <= n) {
                if(ps[p] == undefined) {
                    sum -= p * 2 + 1;
                    ps[p] = true;
                }
            }
            else {
                break;
            }
        }
    }
    return sum + 2;
}



// ---------- parameters
var howOften = 10;
var maxN = 10000;

console.log('iterations: ', howOften);
console.log('maxN: ', maxN);


// ---------- dry runs for warm-up
for( i = 0; i < 1000; i++ ) {
    sum = methodOne(maxN);
    sum = methodTwo(maxN);
}

// ---------- method one
var start = (new Date).getTime();

for( i = 0; i < howOften; i++ )
    sum = methodOne(maxN);

var stop = (new Date).getTime();
console.log('methodOne: ', (stop - start) / howOften);

// ---------- method two

for( i = 0; i < howOften; i++ )
    sum = methodTwo(maxN);

var stop2 = (new Date).getTime();
console.log('methodTwo: ', (stop2 - stop) / howOften);
4

2 に答える 2

2

JSランタイムは最適化されたJITコンパイラです。つまり、しばらくの間、コードは解釈され（t int）、その後コンパイルされ（t jit）、最後にコンパイルされたコードを実行します（t run）。

ここで、計算するのはおそらく（t int + t jit + t run）/Nです。Nにほぼ線形に依存する唯一の部分がtrunであることを考えると、残念ながら、この比較はあまり意味がありません。

答えは、わかりません。適切な答えを得るには、

  1. プロファイルしようとしているコードを関数に抽出します
  2. これらの関数でウォームアップサイクルを実行し、ウォームアップサイクルのタイミングを使用しないでください
  3. ウォームアップと測定の両方で、1..10回以上実行します
  4. アルゴリズムの時間を測定する順序を入れ替えてみてください
  5. 可能であればJSインタープリターの内部に入り、何が起こるかを確実に理解してください。自分がしていると思うことを本当に測定していますか？JITは、測定中ではなく、ウォームアップサイクル中に実行されますか？等

更新： 1サイクルの場合、実行時間はシステムタイマーの解像度よりも短くなることに注意してください。これは、間違いが比較する実際の値よりもおそらく大きいことを意味します。

于 2012-01-14T13:09:06.080 に答える
0

methodTwoでは、プロセッサが実行する計算が少なくて済みます。methodOneでは、最初のforループはmaxN回実行されます。methodTwoでは、最初のforループが（maxN -2）/2回実行されています。したがって、2番目の方法では、プロセッサは最初の方法が実行している計算の半分未満の数を実行しています。これは、各メソッドにネストされたforループが含まれているという事実によってさらに複雑になります。したがって、methodOneのbig-OはmaxN^2です。一方、methodTwoのbig-Oは（（maxN -2）/ 2）^2です。

于 2012-01-14T14:51:37.467 に答える