streamalism.org

1. Overzicht

In deze korte tutorial, we zullen de twee vergelijken Arrays.sort (Object []) en Arrays.sort (int []) sorteerbewerkingen.

Eerst zullen we elke methode afzonderlijk beschrijven. Daarna zullen we prestatietests schrijven om hun looptijden te meten.

2. Arrays.sort (Object [])

Voordat we verder gaan, is het belangrijk om dat in gedachten te houden Arrays.sort () werkt voor zowel primitieve arrays als arrays van het referentietype.

Arrays.sort (Object []) accepteert referentietypes.

We hebben bijvoorbeeld een reeks Geheel getal voorwerpen:

Geheel getal [] getallen = {5, 22, 10, 0};

Om de array te sorteren, kunnen we eenvoudigweg gebruiken:

Arrays.sort (getallen);

Nu heeft de array met nummers alle elementen in oplopende volgorde:

[0, 5, 10, 22]

Arrays.sort (Object []) is gebaseerd op het TimSort-algoritme, wat ons een tijdcomplexiteit geeft van O (n logboek (n)). Kortom, TimSort maakt gebruik van de Insertion sort en de MergeSort algoritmen. Het is echter nog steeds langzamer in vergelijking met andere sorteeralgoritmen zoals sommige van de QuickSort-implementaties.

3. Arrays.sort (int [])

Aan de andere kant, Arrays.sort (int []) werkt met primitief int arrays.

Evenzo kunnen we een int [] reeks primitieven:

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

En sorteer het met een andere implementatie van Arrays.sort (int []). Deze keer accepteren we een reeks primitieven:

Arrays.sort (primitieven);

Het resultaat van deze bewerking zal niet verschillen van het vorige voorbeeld. En de items in de primitieven array ziet er als volgt uit:

[0, 5, 10, 22]

Onder de motorkap maakt het gebruik van een Dual-Pivot Quicksort-algoritme. De interne implementatie van de JDK 10 is doorgaans sneller dan de traditionele Quicksort met één draaipunt.

Dit algoritme biedt O (n log (n)) gemiddelde tijd complexiteit. Dat is voor veel collecties een prima gemiddelde sorteringstijd. Bovendien heeft het het voordeel dat het volledig op zijn plaats zit, dus het vereist geen extra opslag.

Hoewel, in het ergste geval is de tijdcomplexiteit O (n2).

4. Tijdvergelijking

Dus, welk algoritme is sneller en waarom? Laten we eerst wat theorie doen, en dan zullen we enkele concrete tests uitvoeren met JMH.

4.1. Kwalitatieve analyse

Arrays.sort (Object []) is doorgaans langzamer in vergelijking met Arrays.sort (int []) om een ​​paar verschillende redenen.

De eerste zijn de verschillende algoritmen. QuickSort is vaak sneller dan Timsort.

Ten tweede is er hoe elke methode de waarden vergelijkt.

Zien, sinds Arrays.sort (Object []) moet het ene object met het andere vergelijken, het moet elk element aanroepen vergelijk met methode. Dit vereist op zijn minst het opzoeken van een methode en het pushen van een oproep op de stapel, naast wat de vergelijkingsoperatie ook werkelijk is.

Aan de andere kant, Arrays.sort (int []) kan eenvoudig primitieve relationele operatoren gebruiken, zoals < en >, dit zijn enkele bytecode-instructies.

4.2. JMH-parameters

Laten we eindelijk eens kijken welke sorteermethode werkt sneller met actuele gegevens. Daarvoor gebruiken we de JMH-tool (Java Microbenchmark Harness) om onze benchmarktests te schrijven.

Dus we gaan hier gewoon een heel eenvoudige benchmark doen. Het is niet allesomvattend maar geeft ons een idee van hoe we dit kunnen aanpakken vergelijken Arrays.sort (int []) en Arrays.sort (Geheel getal[]) sorteermethoden.

In onze benchmarkklasse gebruiken we configuratie-annotaties:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MILLISECONDS) @Measurement (batchSize = 100000, iteraties = 10) @Warmup (batchSize = 100000, iteraties = 10) openbare klasse ArraySortBenchmark {}

Hier willen we de gemiddelde tijd voor een enkele bewerking meten (Mode.A AverageTime) en toon onze resultaten in milliseconden (TimeUnit.MILLISECONDS). Bovendien, met de seriegrootte parameter, vertellen we JMH om 100.000 iteraties uit te voeren om ervoor te zorgen dat onze resultaten een hoge precisie hebben.

4.3. Benchmark-tests

Voordat we de tests uitvoeren, moeten we de datacontainers definiëren die we willen sorteren:

@State (Scope.Thread) publieke statische klasse Initialiseer {Geheel getal [] getallen = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, 7516052019 -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, -209 ... 562424208, -1233745158, 41308167}; }

Laten we de Geheel getal [] getallen en de int []primitieven reeks primitieve elementen. De @Staat annotatie geeft aan dat de variabelen die in de klasse zijn gedeclareerd, niet deel uitmaken van het uitvoeren van benchmarktests. We kunnen ze echter wel gebruiken in onze benchmarkmethoden.

Nu zijn we klaar om de eerste micro-benchmark toe te voegen voor Arrays.sort (geheel getal []):

@Benchmark openbaar geheel getal [] benchmarkArraysIntegerSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.numbers); terugkeer staat. nummers; }

Vervolgens voor Arrays.sort (int []):

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

4.4. Test resultaten

Ten slotte voeren we onze tests uit en vergelijken we de resultaten:

Benchmark Mode Cnt Score Error Units benchmarkArraysIntSort gem. 10 1,095 ± 0,022 ms / op benchmarkArraysIntegerSort gem. 10 3,858 ± 0,060 ms / op

Aan de resultaten kunnen we dat zien Arrays.sort (int []) methode presteerde beter dan Arrays.sort (Object [])in onze test, waarschijnlijk vanwege de eerdere redenen die we hebben vastgesteld.

En hoewel de cijfers onze theorie lijken te ondersteunen, moeten we testen met een grotere verscheidenheid aan inputs om een ​​beter idee te krijgen.

Ook, Houd er rekening mee dat de cijfers die we hier presenteren slechts JMH-benchmarkresultaten zijn - dus we moeten altijd testen in het bereik van ons eigen systeem en runtime.

4.5. Waarom Timsort dan?

Dan moeten we onszelf waarschijnlijk een vraag stellen. Als QuickSort sneller is, waarom zou u het dan niet voor beide implementaties gebruiken?

Zien, QuickSort is dat niet stal, dus we kunnen het niet gebruiken om te sorteren Voorwerpen. Kortom, als er twee zijn ints zijn gelijk, het maakt niet uit dat hun relatieve volgorde hetzelfde blijft sinds één 2 is niet anders dan een ander 2. Bij objecten kunnen we echter sorteren op het ene attribuut en vervolgens op het andere, waardoor de startvolgorde belangrijk is.

5. Conclusie

In dit artikel, we hebben twee sorteermethoden vergeleken die beschikbaar zijn in Java: Arrays.sort (int []) en Arrays.sort (Geheel getal[]). Bovendien hebben we de sorteeralgoritmen besproken die bij hun implementaties worden gebruikt.

Ten slotte hebben we met behulp van benchmarkprestatietests een voorbeeld van de runtime van elk laten ziensorteeroptie.

Zoals gewoonlijk is de volledige code voor dit artikel beschikbaar op GitHub.