为什么程序的执行时间会发生显着变化？

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人，你问一个人：这里的平均年龄是多少？ - 该人需要向每个人询问他的年龄，进行一些计算以便用来回答。

如果您想再次恳请 - 而无需改变任何东西 - 答案会立即出现。 （复制阵列将是一个房间开关，同时保持相同的人）

但是，如果你要改变人（不管保持或改变房间） - 整个算法需要再次执行。

而且这个例子在之间（在问人）只有一层，可能已经记得问的问题。