streamalism.org

1. Oversikt

I denne raske opplæringen, vi sammenligner de to Arrays.sort (Objekt []) og Arrays.sort (int []) sorteringsoperasjoner.

Først vil vi beskrive hver metode separat. Etter det vil vi skrive ytelsestester for å måle kjøretiden.

2. Arrays.sort (Objekt [])

Før vi går videre, er det viktig å huske på det Arrays.sort () fungerer for både primitive og referansetypearriser.

Arrays.sort (Objekt []) godtar referansetyper.

For eksempel har vi en rekke Heltall gjenstander:

Heltall [] tall = {5, 22, 10, 0};

For å sortere matrisen kan vi ganske enkelt bruke:

Arrays.sort (tall);

Nå har tallene alle elementene i stigende rekkefølge:

[0, 5, 10, 22]

Arrays.sort (Objekt []) er basert på TimSort-algoritmen, gir oss en tidskompleksitet av O (n logg (n)). Kort sagt, TimSort benytter seg av Insertion sort og MergeSort algoritmene. Imidlertid er det fremdeles tregere sammenlignet med andre sorteringsalgoritmer som noen av QuickSort-implementeringene.

3. Arrays.sort (int [])

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

På samme måte kan vi definere en int [] rekke primitiver:

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

Og sorter det med en annen implementering av Arrays.sort (int []). Denne gangen aksepterer vi en rekke primitiver:

Arrays.sort (primitiver);

Resultatet av denne operasjonen vil ikke være forskjellig fra forrige eksempel. Og elementene i primitiver array vil se ut:

[0, 5, 10, 22]

Under panseret bruker den en Dual-Pivot Quicksort-algoritme. Den interne implementeringen fra JDK 10 er vanligvis raskere enn tradisjonell en-pivot Quicksort.

Denne algoritmen tilbyr O (n logg (n)) gjennomsnitt tidskompleksitet. Det er en flott gjennomsnittlig sorteringstid for mange samlinger. Videre har den fordelen av å være helt på plass, slik at den ikke krever ekstra lagring.

Selv om, i verste fall er dens tidskompleksitet O (n2).

4. Tidssammenligning

Så hvilken algoritme er raskere og hvorfor? La oss først gjøre litt teori, og deretter kjøre noen konkrete tester med JMH.

4.1. Kvalitativ analyse

Arrays.sort (Objekt []) er vanligvis tregere sammenlignet med Arrays.sort (int []) av noen få forskjellige grunner.

Den første er de forskjellige algoritmene. QuickSort er ofte raskere enn Timsort.

For det andre er hvordan hver metode sammenligner verdiene.

Se, siden Arrays.sort (Objekt []) må sammenligne ett objekt mot et annet, må det kalle hvert element sammenligne med metode. I det minste krever dette en metodesøking og skyve en samtale på bunken i tillegg til hva sammenligningsoperasjonen faktisk er.

På den andre siden, Arrays.sort (int []) kan ganske enkelt bruke primitive relasjonsoperatører som < og >, som er enkle bytekodeinstruksjoner.

4.2. JMH-parametere

Til slutt, la oss finne ut av det hvilken sorteringsmetode som går raskere med faktiske data. For det vil vi bruke JMH (Java Microbenchmark Harness) -verktøyet til å skrive våre referansetester.

Så vi skal bare gjøre en veldig enkel referanse her. Det er ikke omfattende, men vil gi oss en ide om hvordan vi kan nærme oss sammenligne Arrays.sort (int []) og Arrays.sort (Heltall []) sorteringsmetoder.

I vår referanseklasse bruker vi konfigurasjonskommentarer:

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

Her vil vi måle gjennomsnittlig tid for en enkelt operasjon (Mode.AverageTime) og vise resultatene i millisekunder (TimeUnit.MILLISECONDS). Videre, med Partistørrelse, Gruppestørrelse parameter, vi ber JMH utføre 100.000 iterasjoner for å sikre at resultatene våre har høy presisjon.

4.3. Referansetester

Før du kjører testene, må vi definere databeholderne som vi vil sortere:

@State (Scope.Thread) offentlig statisk klasse Initialiser {Heltall [] tall = {-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, -6148565 562424208, -1233745158, 41308167}; }

La oss velge Heltall [] tall og int []primitiver rekke primitive elementer. De @Stat kommentar indikerer at variablene deklarert i klassen ikke vil være en del av å kjøre referansetester. Imidlertid kan vi bruke dem i våre referansemetoder.

Nå er vi klare til å legge til den første mikro-referansen for Arrays.sort (Heltall []):

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

Neste, for Arrays.sort (int []):

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

4.4. Testresultater

Til slutt kjører vi testene våre og sammenligner resultatene:

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

Fra resultatene kan vi se det Arrays.sort (int []) metoden utført bedre enn å Arrays.sort (Objekt [])i testen vår, sannsynligvis av de tidligere grunnene vi identifiserte.

Og selv om tallene ser ut til å støtte teorien vår, må vi teste med et større utvalg av innganger for å få en bedre ide.

Også, husk at tallene vi presenterer her bare er JMH-referanseresultater - så vi bør alltid teste i omfanget av vårt eget system og kjøretid.

4.5. Hvorfor Timsort da?

Vi burde nok stille oss et spørsmål, da. Hvis QuickSort er raskere, hvorfor ikke bruke det til begge implementeringene?

Se, QuickSort er det ikke stabil, så vi kan ikke bruke den til å sortere Objekter. I utgangspunktet, hvis to ints er like, spiller det ingen rolle at deres relative rekkefølge forblir den samme siden en 2 er ikke forskjellig fra en annen 2. Med objekter kan vi imidlertid sortere etter ett attributt og deretter et annet, slik at startordren betyr noe.

5. Konklusjon

I denne artikkelen, vi sammenlignet to tilgjengelige sorteringsmetoder i Java: Arrays.sort (int []) og Arrays.sort (Heltall []). I tillegg diskuterte vi sorteringsalgoritmene som ble brukt i implementeringene.

Til slutt viste vi en prøvekjøringstid på hver ved hjelp av ytelsestestersorteringsalternativ.

Som vanlig er den komplette koden for denne artikkelen tilgjengelig på GitHub.