如果更頻繁地執行，相同的代碼需要更長的時間？

我在網頁上有一個<script>標記裏面的下面的代碼，其他都沒有。恐怕我目前沒有在線。正如你所看到的，它以兩種不同的方式將兩百萬以下的所有素數加起來，並計算平均花費多少時間。變量howOften用於執行此操作很多次，因此您可以對其進行平均處理。令我感到困惑的是，對於howOften == 1，方法2更快，但對於howOften == 10，方法1是。即使您幾次擊中F5，差異仍然很大。如果更頻繁地執行，相同的代碼需要更長的時間？

我的問題很簡單：怎麼回事？

（！這個帖子已被編輯納入ALF的建議，但認爲沒有什麼區別，我很疑惑，現在。）

（再次編輯：在與howOften或超過1000時，有時似乎是穩定的。 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);

來源

2012-01-14 toon81

方法1對我來說似乎總是比較快，當'howOften = 1'時：http://jsfiddle.net/KYsGm/。我用10000，因爲它花了太長的時間，否則。 – pimvdb 2012-01-14 13:09:35

這看起來像一個很大的問題：http://en.wikipedia.org/wiki/Time_complexity – Ted 2012-01-14 14:43:12

那麼，JS運行時是一個優化的JIT編譯器。這意味着一段時間後，您的代碼將被解釋（t _int），然後編譯（t _jit），最後運行編譯代碼（t _運行）。

現在你計算什麼是最可能（T _INT + T _JIT + T _運行）/ N。鑑於N上幾乎線性的唯一部分是t _run，不幸的是，這種比較沒有多大意義。

所以答案是，我不知道。爲了有一個正確的答案，

提取您嘗試這些功能簡介進入功能
運行熱身週期的代碼，並從熱身週期不使用時刻
運行遠遠超過1..10次，用於熱身和測量
嘗試交換您爲算法測量時間的順序
如果可以，進入JS解釋器內部，並確保您瞭解發生了什麼：你真的衡量你的東西嗎？嗨，你呢？ JIT在熱身週期中運行，而不是在測量時運行？等等，等等

更新：還要注意的是1個週期，你就會得到運行時間小於系統計時器的分辨率，這意味着該錯誤可能比你比較實際值更大。

來源

2012-01-14 13:09:06 alf

非常好的答案。有道理，教會了我很多。試試吧！ – toon81 2012-01-14 13:28:50

對不起。試過了，沒有任何區別;看到編輯過的帖子。不過，不收回我的+1。再一次，真棒答案。 – toon81 2012-01-14 13:38:06

那麼，當我增加到幾乎超過1000時，這似乎穩定了測量的時間。 – toon81 2012-01-14 13:42:34

方法二隻需要處理器執行較少的計算。在方法中，您的初始for循環正在執行maxN次。在methodTwo中，您的初始for循環正在執行（maxN -2）/ 2次。因此，在第二種方法中，處理器執行的次數不到第一種方法所執行的計算次數的一半。這是因爲每個方法都包含一個嵌套for循環。所以methodOne的big-O是maxN^2。而方法二的big-O是（（maxN-2）/ 2）^ 2。

來源

2012-01-14 14:51:37 Ted

那麼，從技術上講，他們有相同的大O然後，他們不是...無論如何，第一個內部循環只對素數執行。這是有區別的。表面上看，第二個對我來說看起來還不錯，但我不能確定。 – toon81 2012-01-14 16:35:18

他們沒有。 n^2的大O與（n/2）^ 2的大O不同。 – Ted 2012-01-14 16:42:39

是的。因爲一個需要一百萬次n^2的算法比一個需要一次n^3的算法具有更好的大O.當然，我可能是錯的，有時我是。但我不認爲我在這種情況下。 – toon81 2012-01-14 16:48:27

如果更頻繁地執行，相同的代碼需要更長的時間？

回答

相關問題