测量Java中的排序时间

Question

我编写了一个程序来测试和验证“插入排序”的运行时间，该时间应为O（n ^ 2）。输出对我而言并不正确，并且在不同运行之间似乎相差不大。另一个奇怪的是，第二次通过始终是最小的。我希望每次运行程序时都会有更大的差异，但是运行时间似乎并没有我期望的那样波动。我只是想知道是否有某种优化或JVM或编译器正在完成某些事情。我在C＃中有类似的代码，而且似乎变化更大，并且输出符合预期。我不希望每次运行时间都成平方，但我希望它们会比实际增加更多，并且我当然希望在最后一次迭代中会有更大的差异。

样本输出（对于我来说，包括多个输出还不够多：]

• 47
• 20（这总是最低的……这毫无意义！）
• 44
• 90
• 133
• 175
• 233
• 298
• 379

• 490

  public class SortBench {
  
  public static void main(String args[]){
  
      Random rand = new Random(System.currentTimeMillis());
  
      for(int k = 100; k <= 1000; k += 100)
      {
          //Keep track of time
          long time = 0;
          //Create new arrays each time
          int[] a = new int[k];
          int[] b = new int[k];
          int[] c = new int[k];
          int[] d = new int[k];
          int[] e = new int[k];
  
          //Insert random integers into the arrays
          for (int i = 0; i < a.length; i++)
          {
              int range = Integer.MAX_VALUE;
              a[i] = rand.nextInt(range);
              b[i] = rand.nextInt(range);
              c[i] = rand.nextInt(range);
              d[i] = rand.nextInt(range);
              e[i] = rand.nextInt(range);
          }
          long start = System.nanoTime();
          insertionSort(a);
          long end = System.nanoTime();
          time += end-start;
  
          start = System.nanoTime();
          insertionSort(b);
          end = System.nanoTime();
          time += end-start;
  
          start = System.nanoTime();
          insertionSort(c);
          end = System.nanoTime();
          time += end-start;
  
          start = System.nanoTime();
          insertionSort(d);
          end = System.nanoTime();
          time += end-start;
  
          start = System.nanoTime();
          insertionSort(e);
          end = System.nanoTime();
          time += end-start;
  
          System.out.println((time/5)/1000);
      }
  }
      static void insertionSort(int[] a)
      {
          int key;
          int i;
          for(int j = 1; j < a.length; j++)
          {
              key = a[j];
              i = j - 1;
              while(i>=0 && a[i]>key)
              {
                  a[i + 1] = a[i];
                  i = i - 1;
              }
              a[i + 1] = key;
          }
      }
  }
  

Answer 1

在定时区域之前对功能，内存分配器，TLB，CPU频率等进行JVM的JIT优化。

在播种RNG之后，在现有计时循环之前立即添加一些未计时的呼叫。

Random rand = new Random(System.currentTimeMillis()); 

// warmup
for(int k = 100; k <= 10000; k += 100) 
{
    int[]w = new int[1000];
    for (int i = 0; i < w.length; i++) 
    { 
       int range = Integer.MAX_VALUE; 
       w[i] = rand.nextInt(range); 
       insertionSort(w);
     }
 }

升温的结果：

4
16
27
47
68
97
126
167
201
250

未升温的结果：

62
244
514
206
42
59
80
98
122
148

Answer 2

在您的第一次迭代中，您也正在测量JIT时间（或至少some JIT时间-HotSpot将逐步进行进一步优化）。首先运行几次，然后then开始测量。我怀疑随着时间的推移，您会看到HotSpot的好处-先前的测试会因JIT 和不能以最佳代码运行的事实而变慢。 （将其与.NET进行比较，其中JIT仅运行一次-没有逐步优化。）

如果您can，也要先分配所有内存-确保直到最后都没有垃圾回收。否则，您将在时间中包括分配和GC。

您还应考虑尝试以n上升另一个数量级的方式获取更多样本，以更好地了解时间如何增加。 （我没有仔细研究您所做的足够细致的工作来确定它是否真的[[应该是O（n 2）。）