Измерение времени сортировки в 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 ² ).)

Answer 2

Прогрейте, добавив следующее сразу после Random rand = new Random (System.currentTimeMillis ());

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