0

我在<script>网页上的标签内有以下代码，上面没有其他内容。恐怕我目前没有在线。如您所见，它以两种不同的方式将所有低于 200 万的素数相加，并计算平均花费的时间。该变量howOften用于多次执行此操作，因此您可以对其进行平均。令我困惑的是，对于howOften == 1，方法 2 更快，但对于howOften == 10，方法 1 更快。即使您按 F5 几次，差异也很大并且仍然存在。

我的问题很简单：怎么会？

（这篇文章已被编辑以纳入 alf 的建议。但这没有任何区别！我现在非常困惑。）

（再次编辑：howOften在或超过 1000 时，时间似乎很稳定。阿尔夫的回答似乎是正确的。）

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 的部分是 t run，不幸的是，这种比较没有多大意义。

所以答案是，我不知道。为了得到正确的答案，

  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 次。因此，在第二种方法中，处理器执行的计算次数少于第一种方法的一半。每个方法都包含一个嵌套的 for 循环，这使情况更加复杂。所以methodOne的大O是maxN^2。而 methodTwo 的 big-O 是 ((maxN -2)/2)^2。

于 2012-01-14T14:51:37.467 回答