Tri par casse vs Insertion Tri JMH benchmark: pourquoi mon insertion impl. prend moins de temps?

Question

J'ai implémenté le tri par insertion et le tri par tas. En théorie, le tri Heap a une complexité temporelle nlogn et l'insertion a n^2. Pourquoi, alors il faut environ six fois plus de temps pour que mon implémentation d'Insertion trier un tableau de 100 000? J'ai utilisé JMH pour évaluer le temps moyen de chaque algorithme de tri. Voici mon code de référence:

import java.util.concurrent.ThreadLocalRandom; 
import java.util.concurrent.TimeUnit; 
import java.util.stream.IntStream; 

import org.openjdk.jmh.annotations.Benchmark; 
import org.openjdk.jmh.annotations.BenchmarkMode; 
import org.openjdk.jmh.annotations.Mode; 
import org.openjdk.jmh.annotations.OutputTimeUnit; 
import org.openjdk.jmh.runner.Runner; 
import org.openjdk.jmh.runner.RunnerException; 
import org.openjdk.jmh.runner.options.Options; 
import org.openjdk.jmh.runner.options.OptionsBuilder; 

public class MyBenchmark { 

// setup the benchmark - create a new array for each iteration 
    @State(Scope.Thread) 
    public static class MyState { 
     int[] array = null; 

     @Setup(Level.Iteration) 
     public void doSetup() { 
      array = createArray(100000, 0, 100); 
     } 
    } 

    @Benchmark 
    @BenchmarkMode(Mode.AverageTime) 
    @OutputTimeUnit(TimeUnit.SECONDS) 
    public void insertionSort(MyState state) { 
     int[] array = state.array; 

     for (int i = 1; i < array.length; i++) { 
      int element = array[i]; 
      for (int j = i - 1; j >= 0; j--) { 
       if (element < array[j]) { 
        int temp = array[j]; 
        array[j] = element; 
        array[j + 1] = temp; 
       } else { 
        break; 
       } 
      } 
     } 
    } 

    @Benchmark 
    @BenchmarkMode(Mode.AverageTime) 
    @OutputTimeUnit(TimeUnit.SECONDS) 
    public void heapSort(MyState state) { 
     int[] array = state.array; 
     sort(array, array.length); 
    } 

    public static void sort(int[] arr, int size) { 

     for (int i = 0; i < size;) { 
      maxHeapify(size, arr); 
      int temp = arr[0]; 
      arr[0] = arr[size - 1]; 
      arr[size - 1] = temp; 
      size--; 
     } 
    } 

    private static void maxHeapify(int size, int[] arr) { 
     int nonLeafs = size/2; 
     for (int i = nonLeafs; i > 0; i--) { 
      int arrayPos = heapToArrayPos(i), leftChild = heapToArrayPos(leftChild(i)), 
        rightChild = heapToArrayPos(rightChild(i)); 
      if (rightChild < size) { 
       if (arr[rightChild] < arr[leftChild]) { 
        if (arr[arrayPos] < arr[leftChild]) { 
         switchWithLeftChild(arrayPos, arr); 
        } 
       } else if (arr[arrayPos] < arr[rightChild]) { 
        switchWithRightChild(arrayPos, arr); 
       } 
      } else if (arr[arrayPos] < arr[leftChild]) { 
       switchWithLeftChild(arrayPos, arr); 
      } 
     } 
    } 

    private static int heapToArrayPos(int heap) { 
     return heap - 1; 
    } 

    private static int rightChild(int pos) { 
     return pos * 2 + 1; 
    } 

    private static int leftChild(int pos) { 
     return pos * 2; 
    } 

    private static void switchWithRightChild(int pos, int[] arr) { 
     int father = arr[pos]; 
     int childPos = heapToArrayPos(rightChild(pos + 1)), child = arr[childPos]; 
     arr[childPos] = father; 
     arr[pos] = child; 
    } 

    private static void switchWithLeftChild(int pos, int[] arr) { 
     int father = arr[pos]; 
     int childPos = heapToArrayPos(leftChild(pos + 1)), child = arr[childPos]; 
     arr[childPos] = father; 
     arr[pos] = child; 
    } 

    public static void main(String[] args) throws RunnerException { 
     Options opt = new OptionsBuilder().include(MyBenchmark.class.getSimpleName()).forks(1).build(); 

     new Runner(opt).run(); 
    } 

    public static int[] createArray(int length, int minValue, int maxValue) { 
     return IntStream.generate(() -> ThreadLocalRandom.current().nextInt(minValue, maxValue)).limit(length) 
       .toArray(); 
    } 

    public static int[] createArray(int length) { 
     return createArray(length, 0, 10); 
    } 

    public static int[] createArray(int minValue, int maxValue) { 
     return createArray(10, minValue, maxValue); 

    } 
} 

Et voici la sortie d'étalonnage:

JMH 1,12 (publié il y a 51 jours) VM version: JDK 1.8.0_65, VM 25,65-B01 VM invocateur : C: \ Program Files \ Java \ jdk1.8.0_65 \ jre \ bin \ java.exe Options de machine virtuelle: -Dfile.encoding = UTF-8 -Xbootclasspath: C: \ Program Files \ Java \ jdk1.8.0_65 \ jre \ lib \ resources.jar; C: \ Program Files \ Java \ jdk1.8.0_65 \ jre \ lib \ rt.jar; C: \ Program Files \ Java \ jdk1.8.0_6 5 \ jre \ lib \ jsse.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ jce.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ charsets.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ jfr.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ lib \ tools.jar
Réchauffement: 20 itérations, 1 de chaque
mesure: 20 itérations, 1 de chaque
Timeout: 10 min par itération
Sujets: 1 fil, se synchronise itérations
Mode de référence: temps moyen, du temps/op
référence: org. sample.MyBenchmark.heapSort

Run progression: 0,00% complet, ETA 00:01:20
Fourchette: 1 de 1
Warmup Iteration 1: 17.651 s/op
Warmup Iteration 2: 16,004 s/op
Warmup Iteration 3: 14.640 s/op
Warmup itération 4: 14.699 s/op
Warmup itération 5: 14.836 s/op
Warmup itération 6: 14.900 s/op
Warmup itération 7: 14.758 s/op
Warmup itération 8: 15,084 s/op
Warmup Iterat ion 9: 15.652 s/OP
Warmup Iteration 10: 15.121 s/OP
Warmup Iteration 11: 15.315 s/OP
Warmup Iteration 12: 15.299 s/OP
Warmup Iteration 13: 15.234 s/op
Warmup itération 14: 14,822 s/oP
Warmup itération 15: 15.078 s/oP
Warmup itération 16: 15.565 s/oP
Warmup itération 17: 15.509 s/oP
Warmup itération 18: 15.189 s/oP
Warmup Itération 19: 14.748 s/op
Warmup Iteration 20: 14,902 s/OP
Itération 1: 14.888 s/OP
Itération 2: 15.381 s/OP
Itération 3: 16.099 s/OP
Itération 4: 15.536 s/OP
Itération 5: 15.635 s/op
Itération 6: 16.446 s/op
Itération 7: 16.034 s/op
Itération 8: 15.828 s/op
Itération 9: 15.666 s/op
Iteration 10: 16,071 s/oP
Iteration 11: 15.962 s/op
Iteration 12: 15.777 s/op
Iteration 13: 15.757 s/op
Iteration 14: 15.424 s/op
Iteration 15: 15.449 s/o
Iteration 16: 15,920 s/OP
Iteration 17: 14.609 s/op
Iteration 18: 14.651 s/op
Iteration 19: 14.661 s/op
Iteration 20: 14.607 s/op

résultat " heapSort ": 15.520 ± (99.9%) 0.486 s/op [Moyenne] (min, moyenne, max) = (14.607, 15.520, 16.446), stdev = 0.560 CI (99.9%): [15.034, 16.006] (suppose normal distribution)

JMH 1,12 (publié il y a 51 jours) version VM: JDK 1.8.0_65, VM-B01 25,65 VM invocateur: C: \ Pro gram Files \ Java \ jdk1.8.0_65 \ jre \ bin \ java.exe Options de machine virtuelle: -Dfile.encoding = UTF-8 -Xbootclasspath: C: \ Programmes \ Java \ jdk1.8.0_65 \ jre \ lib \ resources .jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ rt.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ jsse.jar; C: \ Programme Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ jce.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ charsets.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ jre \ lib \ jfr.jar; C: \ Program Fichiers \ Java \ jdk1.8.0_65 \ lib \ tools.jar Réchauffement: 20 itérations, 1 s chacune Mesure: 20 itérations, 1 s chacune Délai d'expiration: 10 min par itération Threads: 1 thread, va synchroniser les itérations Benchmark mode: Temps moyen, temps/op Référence: org.sample.MyBenchmark.insertionSort

Run progrès: 50.00% complet, ETA 00:10:15 Fourchette: 1 de 1 Warmup Iteration 1: 1,726 s/op Warmup itération 2: 1,636 s/oP Warmup itération 3: 1,968 s/op Warmup itération 4: 1,970 s/op Warmup itération 5: 1,961 s/op Warmup itération 6: 1,966 s/op Warmup itération 7: 1,962 s/op Échauffement itération 8: 1.961 s/op Échauffement itération 9: 1.959 s/op Échauffement itération 10: 1.965 s/op Échauffement itération 11: 1.9 66 s/OP Warmup Itération 12: 1.970 s/OP Warmup Iteration 13: 1.964 s/OP Warmup Iteration 14: 1.952 s/OP Warmup Iteration 15: 1.955 s/OP Warmup Iteration 16: 1.956 s/op Echauffement Iteration 17: 1.972 s/oP Warmup Iteration 18: 1.966 s/oP Warmup Iteration 19: 1.954 s/oP Warmup Iteration 20: 1.956 s/op
itération 1: 1.969 s/op
itération 2: 1,963 s/o
Itération 3: 2,050 s/o
Itération 4: 2,019 s/op Itération 5: 1.934 s/OP
Itération 6: 1.953 s/op
Itération 7: 1.961 s/op
Itération 8: 1.972 s/op
Itération 9: 1.957 s/op
Iteration 10: 1.956 s/op
Iteration 11: 1,975 s/oP
Iteration 12: 1.950 s/op
Iteration 13: 1.965 s/op
Iteration 14: 1.961 s/op
Iteration 15: 1.950 s/op
Iteration 16: 1.956 s/o
Iteration 17: 1,975 s/OP
Iteration 18: 1.966 s/op
Iteration 19: 1.959 s/op
Iteration 20: 1.965 s/op

résultat "InsertionSort":
1,968 ± (99.9 %) 0,022 s/op [Moyenne] (min, moy, max) = (1.934, 1.968, 2.050), stdev = 0.025 CI (99.9%): [1.946, 1.990] (suppose une distribution normale)

. Temps total: 00:09:55

mode Benchmark Cnt Score d'erreur Unités
MyBenchmark.heapSort avgt 20 12,692 ± 0,282 s/op
MyBenchmark.insertionSort avgt 20 2,024 ± 0,020 s/op

Modifier: Depuis que j'ai posté la question j'ai ajouté le @setup pour mettre en place le tableau avant le benchmark, donc les opérations de création de tableau ne seront pas un facteur. J'ai refait le benchmark et les résultats pour le tri d'insertion étaient à peu près les mêmes. Le tri de tas a été accéléré de 3 secondes en moyenne. J'ai seulement posté le résumé mis à jour des résultats.

Answer 1

Votre tri de tas est implémenté de manière incorrecte. Le code que vous avez posté semble faire un tri de sélection. C'est-à-dire, pour chaque élément qu'il appelle maxHeapify, prend le premier élément dans le tas, le met à la fin, et diminue le nombre. Donc maxHeapify est appelé size fois, chaque fois avec une taille décroissante. Le nombre d'itérations de la boucle interne dans maxHeapify finit par être quelque chose comme (n^2)/4.

Vous avez implémenté un tri de sélection glorifié avec la complexité O (n^2). L'astuce pour effectuer un tri de tas sur place est de construire d'abord le tas - une fois - puis de le réorganiser pour le trier. Vous appelez maxHeapify fois:

maxHeapify(size, arr); 

Quand cela est fait, vous avez un tas max valide, avec le plus grand élément à arr[0], etc. Cela prend O (n).

Ce que vous voulez est un tableau dans l'ordre croissant. Pour ce faire, vous créez une boucle qui copie l'élément le plus volumineux du tas (c'est-à-dire arr[0]) et l'enregistre temporairement. Ensuite, prenez le dernier objet dans le tas, réduisez le nombre par un, puis réinsérez cet élément en haut, en le tamisant au besoin. Enfin, placez le plus grand élément précédent à la position précédemment occupée par le dernier élément.Lorsque le comte arrive à 0, vous avez un tableau trié:

int count = size; 
while (count > 0) 
{ 
    int save = arr[0];  // save the largest item 
    arr[0] = arr[count-1]; // move last item to top 
    arr[count-1] = save; // and place the largest item 
    count = count - 1;  // reduce the count 
    SiftDown(0);   // sift item into place 
} 

Tout ce que vous faites est d'appeler successivement removeMax sur le tas, et stocker le résultat dans le tableau dans la position qui a été libéré. Est la même que celle que vous utilisez lorsque vous insérez un élément dans un segment de mémoire.

Voir mon article de blog, A Simple Heap of Integers, pour un exemple complet de construction d'un tas à l'aide de la méthode O (n) heapify. C'est en C#, mais je pense que c'est assez simple si vous comprenez Java, vous pouvez le comprendre. Je ne montre pas comment faire le tri, mais avec ce code et les quelques lignes ci-dessus, vous devriez vous débrouiller.