streamalism.org

1. Oversigt

I denne hurtige vejledning vi sammenligner de to Arrays.sort (Objekt []) og Arrays.sort (int []) sorteringsoperationer.

Først beskriver vi hver metode separat. Derefter skriver vi præstationstest for at måle deres køretider.

2. Arrays.sort (Objekt [])

Før vi går videre, er det vigtigt at huske det Arrays.sort () fungerer til både primitive og referencetype arrays.

Arrays.sort (Objekt []) accepterer referencetyper.

For eksempel har vi en række Heltal genstande:

Heltal [] tal = {5, 22, 10, 0};

For at sortere arrayet kan vi blot bruge:

Arrays.sort (tal);

Nu har talrammen alle sine elementer i stigende rækkefølge:

[0, 5, 10, 22]

Arrays.sort (Objekt []) er baseret på TimSort-algoritmen, giver os en tidskompleksitet af O (n log (n)). Kort sagt bruger TimSort indsættelsessorteringen og MergeSort-algoritmerne. Det er dog stadig langsommere sammenlignet med andre sorteringsalgoritmer som nogle af QuickSort-implementeringerne.

3. Arrays.sort (int [])

På den anden side, Arrays.sort (int []) fungerer med primitive int arrays.

På samme måde kan vi definere en int [] række primitiver:

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

Og sorter det med en anden implementering af Arrays.sort (int []). Denne gang accepterer en række primitiver:

Arrays.sort (primitiver);

Resultatet af denne handling vil ikke være anderledes end det foregående eksempel. Og elementerne i primitiver array ser ud som:

[0, 5, 10, 22]

Under emhætten bruger den en Dual-Pivot Quicksort-algoritme. Dens interne implementering fra JDK 10 er typisk hurtigere end traditionel one-pivot Quicksort.

Denne algoritme tilbyder O (n log (n)) gennemsnit tidskompleksitet. Det er en god gennemsnitlig sorteringstid for mange samlinger at have. Desuden har den fordelen ved at være helt på plads, så den ikke kræver yderligere lagerplads.

Selvom, i værste fald er dens tidskompleksitet O (n2).

4. Tidssammenligning

Så hvilken algoritme er hurtigere, og hvorfor? Lad os først lave nogle teorier, og derefter køre nogle konkrete tests med JMH.

4.1. Kvalitativ analyse

Arrays.sort (Objekt []) er typisk langsommere sammenlignet med Arrays.sort (int []) af nogle få forskellige grunde.

Den første er de forskellige algoritmer. QuickSort er ofte hurtigere end Timsort.

For det andet er, hvordan hver metode sammenligner værdierne.

Se, siden Arrays.sort (Objekt []) har brug for at sammenligne et objekt mod et andet, skal det kalde hvert element sammenligne med metode. I det mindste kræver dette en metodeopslag og skubber et opkald på stakken ud over hvad sammenligningsoperationen faktisk er.

På den anden side, Arrays.sort (int []) kan simpelthen bruge primitive relationelle operatorer som < og >, som er enkle bytecode-instruktioner.

4.2. JMH-parametre

Lad os endelig finde ud af det hvilken sorteringsmetode kører hurtigere med faktiske data. Til det bruger vi JMH (Java Microbenchmark Harness) -værktøjet til at skrive vores benchmark-tests.

Så vi skal bare lave et meget simpelt benchmark her. Det er ikke omfattende, men vil give os en idé om, hvordan vi kan nærme os sammenligning Arrays.sort (int []) og Arrays.sort (Heltal[]) sorteringsmetoder.

I vores benchmark-klasse bruger vi konfigurationskommentarer:

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

Her vil vi måle den gennemsnitlige tid for en enkelt operation (Mode.AverageTime) og vise vores resultater i millisekunder (TimeUnit.MILLISECONDS). Desuden med batchSize parameter, vi beder JMH om at udføre 100.000 iterationer for at sikre, at vores resultater har høj præcision.

4.3. Benchmark-tests

Før vi kører testene, skal vi definere de databeholdere, som vi vil sortere:

@State (Scope.Thread) offentlig statisk klasse Initialiser {Heltal [] tal = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922999, 1215, 7515 -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] primitiver = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 209485659, -206148526 562424208, -1233745158, 41308167}; }

Lad os vælge Heltal [] numre og int []primitiver vifte af primitive elementer. Det @Stat annotation indikerer, at de variabler, der er erklæret i klassen, ikke vil være en del af kørsel af benchmark-tests. Vi kan dog derefter bruge dem i vores benchmarkmetoder.

Nu er vi klar til at tilføje det første mikro-benchmark for Arrays.sort (Heltal []):

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

Næste til Arrays.sort (int []):

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

4.4. Test resultater

Endelig kører vi vores tests og sammenligner resultaterne:

Benchmark Mode Cnt Score Fejl Enheder benchmarkArraysIntSort avgt 10 1.095 ± 0,022 ms / op benchmarkArraysIntegerSort avgt 10 3.858 ± 0,060 ms / op

Fra resultaterne kan vi se det Arrays.sort (int []) metode udført bedre end at Arrays.sort (Objekt [])i vores test sandsynligvis af de tidligere grunde, vi identificerede.

Og selvom tallene ser ud til at understøtte vores teori, selvom vi bliver nødt til at lave test med et større udvalg af input for at få en bedre idé.

Også, husk, at de tal, vi præsenterer her, kun er JMH-benchmark-resultater - så vi skal altid teste i omfanget af vores eget system og runtime.

4.5. Hvorfor Timsort så?

Vi burde sandsynligvis stille os et spørgsmål. Hvis QuickSort er hurtigere, hvorfor ikke bruge det til begge implementeringer?

Se, QuickSort er det ikke stabil, så vi kan ikke bruge det til at sortere Objekter. Dybest set, hvis to ints er lige, det betyder ikke noget, at deres relative rækkefølge forbliver den samme siden en 2 er ikke forskellig fra en anden 2. Med objekter kan vi dog sortere efter en attribut og derefter en anden, hvilket gør startordren vigtig.

5. Konklusion

I denne artikel vi sammenlignede to tilgængelige sorteringsmetoder i Java: Arrays.sort (int []) og Arrays.sort (Heltal[]). Derudover diskuterede vi de sorteringsalgoritmer, der blev brugt i deres implementeringer.

Endelig viste vi en prøvekørselstid for hver ved hjælp af benchmark-præstationstestsorteringsmulighed.

Som sædvanlig er den komplette kode til denne artikel tilgængelig på GitHub.