Производительность времени

Question

Привет У меня вопрос, что это мой класс, который для каждого «n» получит среднее время для него. также метод, который я хочу взять его производительность имеет Т (п) = O (NlogN)

мой код:

public class NewClass1 { 

    public static void main(String[] args) { 
     List<Point> randList = new ArrayList<Point>(); 
     for (int n = 100; n <= 500; n+=200) { 
      Random rand = new Random(); 
      for (int i = 1; i <= n; i++) { 
       Point point = new Point(rand.nextInt(10), rand.nextInt(10)); 
       randList.add(point); 
      } 
      get(randList); 
     } 
    } 

    public static void get(List<Point> list) { 
     long time = 0; 
     for(int i=1;i<10;i++) { 
      long t = System.currentTimeMillis(); 
      GrahamVersion.grahamScan(list); 

      long t0 = System.currentTimeMillis(); 
      time = time+t0-t; 
     } 
     System.out.println((double)time/10); 
    } 
} 

и он будет печатать:

1.5 
1.6 
0.0 

среднее время все в порядке? потому что для n = 500 будет 0.0 и n = 300 будет 1.6

Answer 1

ряд вещей, которые/могут вызывать «странные» результаты.

Во-первых, ваш бенчмаркинг не учитывает необходимость «разогрева» JVM. Вы должны поставить большую петлю вокруг эталонного кода и запустить его несколько раз, пока цифры не стабилизируются. Например:

public static void main(String[] args) { 
    while (true) { 
     List<Point> randList = new ArrayList<Point>(); 
     for (int n = 100; n <= 500; n+=200) { 
     ... 
     } 
    } 
} 

(путем запуска отсчета в цикле, как это, вы даете JVM возможность загрузки и компиляции классов кода в машинный код, так что ваши результаты не искажены оверхэдами класса загрузка, сборка JIT и т. д.)

Во-вторых, вы должны печатать результаты с большей точностью.

В-третьих, вы должны смотреть не более 3-х цифровых точек.

Наконец, вы попали в ловушку, предполагая, что большой O позволяет прогнозировать поведение с небольшими значениями N. Это неверно. Это только рассказывает вам, что происходит, поскольку N стремится к бесконечности. И даже тогда, это только говорит о производительности верхней границы.

Answer 2

Вам необходимо запустить тест не менее 2 секунд, прежде чем вы получите воспроизводимые результаты. Ваш тест проходит так быстро, что вы не можете измерить его с помощью currentTimeMillis, я предлагаю использовать System.nanoTime(), после того как вы запустите тест на 2 секунды.