java - 测量 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

在您的第一次迭代中，您还测量 JIT 时间(或至少一些 JIT 时间 - HotSpot 将逐步进一步优化)。先运行几次，然后开始测量。我怀疑随着时间的推移，您正在看到 HotSpot 的好处 - 早期的测试因 JIT 花费的时间和 未作为最佳代码运行而变慢。 (与 .NET 相比，JIT 仅运行 一次 - 没有渐进式优化。)

如果您可以，也首先分配所有内存 - 并确保在结束之前没有任何垃圾回收。否则，您将在您的时间安排中包括分配和 GC。

您还应该考虑尝试获取更多样本，将 n 提高另一个数量级，以便更好地了解时间是如何增加的。 (我还没有足够仔细地查看您所做的事情，无法确定它是否真的应该为 O(n²)。)