Performance dans le temps

Question

Salut J'ai une question que c'est ma classe qui pour chaque "n" obtiendra le temps moyen pour cela. aussi la méthode que je veux prendre sa performance a T (n) = O (nlogn)

mon code:

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); 
    } 
} 

et imprimera:

1.5 
1.6 
0.0 

le temps moyen est OK? parce que pour n = 500 aura 0.0 et n = 300 aura 1.6

Answer 1

Un certain nombre de choses qui sont/peuvent causer des résultats « étranges ». Tout d'abord, votre analyse comparative ne tient pas compte de la nécessité de «réchauffer» la JVM. Vous devriez mettre une grande boucle autour du code de référence et l'exécuter un certain nombre de fois jusqu'à ce que les nombres semblent se stabiliser. Par exemple:

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

(En exécutant la référence dans une boucle comme celui-ci, vous donnez la machine virtuelle Java une chance de charger et compiler les classes de code à code natif, afin que vos résultats ne sont pas déformés par les frais généraux de la classe chargement, compilation JIT et ainsi de suite.)

Deuxièmement, vous devriez imprimer les résultats avec une plus grande précision. Troisièmement, vous devriez regarder plus de 3 points de données. Enfin, vous êtes peut-être tombé dans le piège de supposer que le grand O vous permet de prédire le comportement avec des valeurs faibles de N. Ce n'est pas correct. Il seulement vous dit ce qui se passe comme N tend à l'infini. Et même alors, il ne vous dit que la performance de la borne supérieure.

Answer 2

Vous devez effectuer le test pendant au moins 2 secondes avant d'obtenir des résultats reproductibles. Votre test fonctionne si vite que vous ne pouvez pas le mesurer avec currentTimeMillis, je suggère d'utiliser System.nanoTime(), après avoir exécuté le test pendant 2 secondes.