Zeitvergleich von Arrays.sort (Object) und Arrays.sort (int)

1. Übersicht

In diesem kurzen Tutorial, werden wir die beiden vergleichen Arrays.sort (Object []) und Arrays.sort (int []) Sortiervorgänge .

Zunächst werden wir jede Methode separat beschreiben. Danach schreiben wir Leistungstests, um ihre Laufzeiten zu messen.

2. Arrays.sort (Object [])

Bevor wir fortfahren , ist es wichtig zu beachten, dass Arrays.sort () sowohl für primitive Arrays als auch für Arrays vom Referenztyp funktioniert.

Arrays.sort (Object []) akzeptiert Referenztypen .

Zum Beispiel haben wir ein Array von Integer- Objekten:

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

Um das Array zu sortieren, können wir einfach verwenden:

Arrays.sort(numbers);

Jetzt hat das Zahlenarray alle Elemente in aufsteigender Reihenfolge:

[0, 5, 10, 22]

Arrays.sort (Object []) basiert auf dem TimSort-Algorithmus und gibt uns eine zeitliche Komplexität von O (n log (n)) . Kurz gesagt, TimSort verwendet die Einfügungssortierung und die MergeSort-Algorithmen. Im Vergleich zu anderen Sortieralgorithmen wie einigen QuickSort-Implementierungen ist es jedoch immer noch langsamer.

3. Arrays.sort (int [])

Andererseits arbeitet Arrays.sort (int []) mit primitiven int- Arrays.

In ähnlicher Weise können wir ein int [] -Array von Grundelementen definieren:

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

Und sortieren Sie es mit einer anderen Implementierung von Arrays.sort (int []) . Diesmal akzeptieren Sie eine Reihe von Grundelementen:

Arrays.sort(primitives);

Das Ergebnis dieser Operation unterscheidet sich nicht vom vorherigen Beispiel. Und die Elemente im Primitiv- Array sehen folgendermaßen aus:

[0, 5, 10, 22]

Unter der Haube wird ein Dual-Pivot-Quicksort-Algorithmus verwendet. Die interne Implementierung aus dem JDK 10 ist normalerweise schneller als die herkömmliche One-Pivot-Quicksort.

Dieser Algorithmus bietet eine durchschnittliche Zeitkomplexität von O (n log (n)) . Das ist eine großartige durchschnittliche Sortierzeit für viele Sammlungen. Darüber hinaus hat es den Vorteil, dass es vollständig vorhanden ist, sodass kein zusätzlicher Speicher erforderlich ist.

Obwohl, im schlimmsten Fall, zu seiner Zeit Komplexität ist O (n2) .

4. Zeitvergleich

Welcher Algorithmus ist also schneller und warum? Lassen Sie uns zuerst eine Theorie machen und dann einige konkrete Tests mit JMH durchführen.

4.1. Qualitative Analyse

Arrays.sort (Object []) ist aus verschiedenen Gründen im Vergleich zu Arrays.sort (int []) normalerweise langsamer .

Der erste ist die verschiedenen Algorithmen. QuickSort ist oft schneller als Timsort.

Zweitens vergleicht jede Methode die Werte.

Siehe, da Arrays.sort (Object []) braucht ein Objekt gegen einen anderen zu vergleichen, muss es jedes Element nennen compareTo - Methode. Zumindest erfordert dies eine Methodensuche und das Übertragen eines Aufrufs auf den Stapel zusätzlich zu dem, was die Vergleichsoperation tatsächlich ist.

Andererseits kann Arrays.sort (int []) einfach primitive relationale Operatoren wie < und > verwenden , bei denen es sich um Einzelbytecode-Anweisungen handelt.

4.2. JMH-Parameter

Lassen Sie uns abschließend herausfinden, welche Sortiermethode mit tatsächlichen Daten schneller ausgeführt wird . Dafür verwenden wir das JMH-Tool (Java Microbenchmark Harness), um unsere Benchmark-Tests zu schreiben.

Wir werden hier also nur einen sehr einfachen Benchmark durchführen. Es ist nicht umfassend, gibt uns jedoch eine Vorstellung davon, wie wir die Sortiermethoden Arrays.sort (int []) und Arrays.sort ( Integer [] ) vergleichen können.

In unserer Benchmark-Klasse verwenden wir Konfigurationsanmerkungen:

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

Hier möchten wir die durchschnittliche Zeit für eine einzelne Operation messen ( Mode.AverageTime) und unsere Ergebnisse in Millisekunden anzeigen ( TimeUnit.MILLISECONDS) . Darüber hinaus weisen wir JMH mit dem Parameter batchSize an, 100.000 Iterationen durchzuführen, um sicherzustellen, dass unsere Ergebnisse eine hohe Genauigkeit aufweisen.

4.3. Benchmark-Tests

Bevor wir die Tests ausführen, müssen wir die Datencontainer definieren, die sortiert werden sollen:

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

Wählen wir die Integer [] - Zahlen und das int [] - Primitivarray primitiver Elemente. Die Annotation @State gibt an, dass die in der Klasse deklarierten Variablen nicht Teil der Ausführung von Benchmark-Tests sind. Wir können sie dann jedoch in unseren Benchmark-Methoden verwenden.

Jetzt können wir den ersten Mikro-Benchmark für Arrays.sort (Integer []) hinzufügen :

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

Als nächstes für Arrays.sort (int []) :

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

4.4. Testergebnisse

Schließlich führen wir unsere Tests durch und vergleichen die Ergebnisse:

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

Aus den Ergebnissen können wir ersehen, dass die Methode Arrays.sort (int [] ) in unserem Test eine bessere Leistung erbrachte als die Methode Arrays.sort (Object []) , wahrscheinlich aus den zuvor identifizierten Gründen.

Und obwohl die Zahlen unsere Theorie zu unterstützen scheinen, müssten wir Tests mit einer größeren Vielfalt von Eingaben durchführen, um eine bessere Vorstellung zu erhalten.

Auch bedenken , dass die Zahlen , die wir hier präsentieren sind nur JMH Benchmark - Ergebnisse - so sollten wir immer Test im Rahmen unseres eigenen Systems und der Laufzeit.

4.5. Warum dann Timsort?

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

In diesem Artikel haben wir zwei in Java verfügbare Sortiermethoden verglichen: Arrays.sort (int []) und Arrays.sort ( Integer [] ) . Zusätzlich haben wir die Sortieralgorithmen besprochen, die in ihren Implementierungen verwendet werden.

Schließlich haben wir mit Hilfe von Benchmark-Leistungstests jeweils eine Beispiellaufzeit gezeigtSortieroption.

Wie üblich ist der vollständige Code für diesen Artikel auf GitHub verfügbar.