爲什麼程序的執行時間會發生顯着變化？

Question

我想測試不同排序算法的執行時間，我發現了一個有趣的問題。當我多次運行該程序時，比如說插入排序，第一次或第二次比以後的花費更多時間。這種情況發生在數組的大小很大時，不同的大小對執行時間有不同的影響。

public static void insertSort(int[] array){ 
    for(int i = 1; i<array.length; i++){ 
     int current = array[i]; 
     int j = i-1; 
     while((j>=0)&&(array[j]>current)){ 
      array[j+1] = array[j]; 
      array[j] = current; 
      j--; 
     } 
    } 
} 

public static void multiTimes(int size){ 
    Random r = new Random();  
    int a[] = new int[size]; 
    int b[] = new int[size]; 
    for(int j = 0; j<size; j++) 
     a[j] = r.nextInt(size); 

    long startTime, endTime = 0; 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 

    b = Arrays.copyOf(a, a.length); 
    startTime=System.nanoTime(); 
    insertSort(b); 
    endTime=System.nanoTime(); 
    System.out.println("Insert "+(endTime-startTime)+" ns"); 
} 

面積：100
插入77908個納秒
插入82573個納秒
插入75109個納秒
插入76508個納秒
插入91902個納秒
插入78840個納秒

每次的執行時間很相似。

尺寸：1000：
插入6256400納秒
插入5674659納秒
插入188938納秒
插入188004納秒
插入187071納秒
插入186605納秒

尺寸：2000：
插入7961037 ns
插入6590889 ns
插入793538 NS
插入793072納秒
插入793072納秒
插入792138納秒

我們可以看到，對於1000，2000以上的尺寸，結果相當有趣。前兩次的執行時間比後面的執行時間大約多30倍（大小= 1000）。

注：

1. 語言：Java的JDK7; IDE：Eclipse;平臺：Win8.1;
2. 對於每個尺寸，許多實驗都經過測試，結果非常相似。儘管執行時間有一些隨機性，但它無法解釋爲什麼前兩次相似，比後一次長30倍以上。
3. 一個可能的原因可能是該數組已經在數據高速緩存中，因此稍後的執行會花費更少的時間。我不確定是否有其他原因。

PS： 當我測試了插入排序後，我發現它在快速排序時甚至感到困惑。

public static void quickSort(int a[], int left, int right){ 
    if(right<=left) 
     return; 
    int temp[] = new int[right-left+1]; 
    for(int i = left; i<=right; i++) 
     temp[i-left] = a[i]; 
    int pivot = a[left]; 
    int subr = right, subl = left; 
    for(int i = left+1; i<=right;i++){ 
     if(temp[i-left]>pivot) 
      a[subr--] = temp[i-left]; 
     else 
      a[subl++] = temp[i-left]; 
    } 
    a[subl] = pivot; 
    quickSort(a, left, subl-1); 
    quickSort(a, subr+1, right); 
} 

尺寸= 1000：
Qs的888240納秒
Qs的2218734納秒
Qs的2179547納秒
Qs的2132896納秒
Qs的2146890納秒
Qs的2212670納秒

尺寸= 500：
Qs 432924 ns
Qs 406799 ns
Qs的941889納秒
Qs的1103302納秒
Qs的1101436納秒
Qs的1086042納秒

當尺寸圍繞[200，2000]中，第一幾次花費的時間少於後來者，這是相對比插入排序。當大小增加到2000以上時，它與插入排序中的情況類似，後者的執行花費更少的時間。

Answer 1

可能有很多原因，但在你的情況下，我相信這是JIT（即時編譯）的效果，它編譯爲本地代碼最近使用的字節碼片段。這是前兩次執行速度較慢的原因。它們由解釋java字節碼的JVM完成。然後JIT將你的排序算法編譯成本地代碼，JVM執行它，從而顯着提高性能。

Answer 2

當您刪除排序方法的完整的方法體，並與當前的代碼， 你會發現同樣的效果稱之爲 - 在一個較小範圍：

Insert 1488 ns 
Insert 353 ns 
Insert 246 ns 
Insert 240 ns 
Insert 224 ns 
Insert 212 ns 

如果您現在要刪除屬性int[] array還有，你仍然會看到同樣的效果：

Insert 1452 ns 
Insert 342 ns 
Insert 232 ns 
Insert 203 ns 
Insert 228 ns 
Insert 209 ns 

所以，很顯然這種行爲是獨立於數據（-sate），內存分配或已存在於內存的值的重複。

顯然，只有具有方法存根

public static void insertSort(){ 

} 

左邊，它需要有一些待辦事項與方法聲明本身。正如AlexR已經指出的那樣，Java有一個JIT編譯器。而且由於數據中沒有任何內容，所以這種行爲可能只有一個原因：運行時優化。

• Java的編譯代碼，這意味着在構建應用程序時編寫的Java-SOURE被編譯到較低水平語言。
• 編譯語言時，可以有各種抽象步驟。每個單個字符都需要（最終）從人類可讀代碼翻譯爲「零」和「一個」 - 中間有語言相關的層數。
• 由於你不知道運行時數據在設計時，它不能被翻譯爲1和0--所以代碼保持在兩者之間。 （，但它可以在運行時進一步翻譯，當你最終知道數據並且用相同的數據重複訪問相同的方法！）
• 每種語言都有一個共同點：相同的輸入等於相同的輸出。
• 因此，每個圖層都可能有自己的（內部）緩存來加快速度並減少CPU /內存負載。

就像你可以重用的java中的對象，以避免從數據庫中重裝，已經被用於罐頭重用之間的比特和字節的每一層。

（查看但從數據庫的點這樣的效果會提出同樣的問題：爲什麼第一次字符串顯示取爲125ms，和所有其他時間只需5ms的？）

---

想象一個房間10人，你問一個人：這裏的平均年齡是多少？ - 該人需要向每個人詢問他的年齡，進行一些計算以便用來回答。

如果您想再次懇請 - 而無需改變任何東西 - 答案會立即出現。 （複製陣列將是一個房間開關，同時保持相同的人）

但是，如果你要改變人（不管保持或改變房間） - 整個算法需要再次執行。

而且這個例子在之間（在問人）只有一層，可能已經記得問的問題。