Comparaison temporelle de Arrays.sort (Object) et Arrays.sort (int)

1. Vue d'ensemble

Dans ce tutoriel, nous allons comparer les deux Arrays.sort (Object []) et Arrays.sort (int []) les opérations de tri .

Tout d'abord, nous décrirons chaque méthode séparément. Après cela, nous écrirons des tests de performances pour mesurer leurs temps de fonctionnement.

2. Arrays.sort (Objet [])

Avant d'aller de l'avant, il est important de garder à l'esprit que Arrays.sort () fonctionne à la fois pour les tableaux de type primitif et de référence.

Arrays.sort (Object []) accepte les types de référence .

Par exemple, nous avons un tableau d' objets Integer :

Integer[] numbers = {5, 22, 10, 0};

Pour trier le tableau, nous pouvons simplement utiliser:

Arrays.sort(numbers);

Maintenant, le tableau des nombres a tous ses éléments dans l'ordre croissant:

[0, 5, 10, 22]

Arrays.sort (Object []) est basé sur l'algorithme TimSort, nous donnant une complexité temporelle de O (n log (n)) . En bref, TimSort utilise le tri par insertion et les algorithmes MergeSort. Cependant, il est encore plus lent par rapport à d'autres algorithmes de tri comme certaines implémentations QuickSort.

3. Arrays.sort (int [])

D'autre part, Arrays.sort (int []) fonctionne avec des tableaux int primitifs .

De même, nous pouvons définir un tableau int [] de primitives:

int[] primitives = {5, 22, 10, 0};

Et triez-le avec une autre implémentation de Arrays.sort (int []) . Cette fois, en acceptant un tableau de primitives:

Arrays.sort(primitives);

Le résultat de cette opération ne sera pas différent de l'exemple précédent. Et les éléments du tableau des primitives ressembleront à:

[0, 5, 10, 22]

Sous le capot, il utilise un algorithme de tri rapide à double pivot. Son implémentation interne à partir du JDK 10 est généralement plus rapide que le tri rapide à un pivot traditionnel.

Cet algorithme offre une complexité temporelle moyenne O (n log (n)) . C'est un excellent temps de tri moyen pour de nombreuses collections. De plus, il présente l'avantage d'être complètement en place, de sorte qu'il ne nécessite aucun stockage supplémentaire.

Cependant, dans le pire des cas, sa complexité temporelle est O (n2) .

4. Comparaison du temps

Alors, quel algorithme est le plus rapide et pourquoi? Commençons par faire de la théorie, puis nous exécuterons des tests concrets avec JMH.

4.1. Analyse qualitative

Arrays.sort (Object []) est généralement plus lent que Arrays.sort (int []) pour plusieurs raisons.

Le premier concerne les différents algorithmes. QuickSort est souvent plus rapide que Timsort.

Deuxièmement, la façon dont chaque méthode compare les valeurs.

Voir, puisque Arrays.sort (Object []) doit comparer un objet à un autre, il doit appeler la méthode compareTo de chaque élément . À tout le moins, cela nécessite une recherche de méthode et un appel sur la pile en plus de l'opération de comparaison.

D'un autre côté, Arrays.sort (int []) peut simplement utiliser des opérateurs relationnels primitifs comme < et > , qui sont des instructions à un seul bytecode.

4.2. Paramètres JMH

Enfin, découvrons quelle méthode de tri fonctionne le plus rapidement avec les données réelles . Pour cela, nous utiliserons l'outil JMH (Java Microbenchmark Harness) pour écrire nos tests de référence.

Nous allons donc simplement faire un benchmark très simple ici. Ce n'est pas complet mais nous donnera une idée de la façon dont nous pouvons aborder la comparaison des méthodes de tri Arrays.sort (int []) et Arrays.sort ( Integer [] ) .

Dans notre classe de référence, nous utiliserons des annotations de configuration:

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Measurement(batchSize = 100000, iterations = 10) @Warmup(batchSize = 100000, iterations = 10) public class ArraySortBenchmark { }

Ici, nous voulons mesurer le temps moyen d'une seule opération ( Mode.AverageTime) et afficher nos résultats en millisecondes ( TimeUnit.MILLISECONDS) . De plus, avec le paramètre batchSize , nous demandons à JMH d'effectuer 100 000 itérations pour garantir une haute précision de nos résultats.

4.3. Tests de référence

Avant d'exécuter les tests, nous devons définir les conteneurs de données que nous voulons trier:

@State(Scope.Thread) public static class Initialize { Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 }; int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; }

Choisissons les entiers [] nombres et l' int [] primitives ensemble d'éléments primitifs. L' annotation @State indique que les variables déclarées dans la classe ne feront pas partie de l'exécution des tests de référence. Cependant, nous pouvons ensuite les utiliser dans nos méthodes de référence.

Maintenant, nous sommes prêts à ajouter le premier micro-benchmark pour Arrays.sort (Integer []) :

@Benchmark public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.numbers); return state.numbers; }

Ensuite, pour Arrays.sort (int []) :

@Benchmark public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.primitives); return state.primitives; }

4.4. Résultats de test

Enfin, nous exécutons nos tests et comparons les résultats:

Benchmark Mode Cnt Score Error Units benchmarkArraysIntSort      avgt   10  1.095 ± 0.022  ms/op benchmarkArraysIntegerSort  avgt   10  3.858 ± 0.060  ms/op

D'après les résultats, nous pouvons voir que la méthode Arrays.sort (int []) a mieux fonctionné que Arrays.sort (Object []) dans notre test, probablement pour les raisons que nous avons identifiées précédemment.

Et même si les chiffres semblent soutenir notre théorie, nous aurions besoin de faire des tests avec une plus grande variété d'entrées pour avoir une meilleure idée.

De plus, gardez à l'esprit que les chiffres que nous présentons ici ne sont que des résultats de référence JMH - nous devons donc toujours tester dans le cadre de notre propre système et de notre propre environnement d'exécution.

4.5. Pourquoi Timsort alors?

We should probably ask ourselves a question, then. If QuickSort is faster, why not use it for both implementations?

See, QuickSort isn't stable, so we can't use it to sort Objects. Basically, if two ints are equal, it doesn't matter that their relative order stays the same since one 2 is no different from another 2. With objects though, we can sort by one attribute and then another, making the starting order matter.

5. Conclusion

Dans cet article, nous avons comparé deux méthodes de tri disponibles en Java: Arrays.sort (int []) et Arrays.sort ( Integer [] ) . De plus, nous avons discuté des algorithmes de tri utilisés dans leurs implémentations.

Enfin, à l'aide de tests de performance de référence, nous avons montré un exemple de durée d'exécution de chaqueoption de tri.

Comme d'habitude, le code complet de cet article est disponible à l'adresse over sur GitHub.