Časové porovnanie Arrays.sort (objekt) a Arrays.sort (int)

1. Prehľad

V tomto rýchlom návode tieto dva porovnáme Arrays.sort (Object []) a Arrays.sort (int []) triediace operácie.

Najskôr si popíšeme každú metódu zvlášť. Potom napíšeme testy výkonu, aby sme zmerali ich prevádzkové časy.

2. Arrays.sort (Object [])

Predtým, ako napredujeme, je potrebné mať na pamäti to Arrays.sort () funguje pre polia primitívneho aj referenčného typu.

Arrays.sort (Object []) prijíma referenčné typy.

Napríklad máme pole Celé číslo objekty:

Celé číslo [] čísla = {5, 22, 10, 0};

Na zoradenie poľa môžeme jednoducho použiť:

Polia. Zoradiť (čísla);

Teraz má pole čísel všetky svoje prvky vo vzostupnom poradí:

[0, 5, 10, 22]

Arrays.sort (Object []) je založený na algoritme TimSort, čo nám dáva časovú zložitosť O (n log (n)). Stručne povedané, TimSort využíva triedenie Insertion a algoritmy MergeSort. V porovnaní s inými algoritmami triedenia, ako sú niektoré z implementácií QuickSort, je to však stále pomalšie.

3. Arrays.sort (int [])

Na druhej strane, Arrays.sort (int []) pracuje s primitivom int polia.

Podobne môžeme definovať int [] pole primitív:

int [] primitíva = {5, 22, 10, 0};

A triediť to s ďalšou implementáciou Arrays.sort (int []). Tentokrát prijímame rad primitívnych nástrojov:

Polia. Triedenie (primitívne);

Výsledok tejto operácie sa nebude líšiť od predchádzajúceho príkladu. A položky v primitívi pole bude vyzerať takto:

[0, 5, 10, 22]

Pod kapotou používa algoritmus Dual-Pivot Quicksort. Jeho interná implementácia z JDK 10 je zvyčajne rýchlejšia ako tradičný jednopivotový Quicksort.

Tento algoritmus ponúka O (n log (n)) priemer časová zložitosť. To je skvelý priemerný čas na triedenie pre mnoho zbierok. Výhodou je, že je úplne na svojom mieste, takže nevyžaduje žiadne ďalšie skladovanie.

Predsa, v najhoršom prípade je jeho časová zložitosť O (n2).

4. Časové porovnanie

Ktorý algoritmus je teda rýchlejší a prečo? Najprv si urobme teóriu a potom vykonáme niekoľko konkrétnych testov s JMH.

4.1. Kvalitatívna analýza

Arrays.sort (Object []) je v porovnaní s Arrays.sort (int []) z niekoľkých rôznych dôvodov.

Prvým sú rôzne algoritmy. QuickSort je často rýchlejší ako Timsort.

Druhým je, ako každá metóda porovnáva hodnoty.

Pozri, odkedy Arrays.sort (Object []) potrebuje porovnať jeden objekt s druhým, musí zavolať každý prvok porovnať s metóda. Prinajmenšom to vyžaduje vyhľadanie metódy a tlačenie hovoru do zásobníka okrem toho, čo porovnávacia operácia v skutočnosti je.

Na druhej strane, Arrays.sort (int []) môže jednoducho použiť primitívne relačné operátory ako < a >, čo sú pokyny pre jeden bajtkód.

4.2. Parametre JMH

Nakoniec to zistíme ktorá metóda triedenia beží rýchlejšie so skutočnými údajmi. Na to použijeme nástroj JMH (Java Microbenchmark Harness) na napísanie našich testov.

Teraz tu teda urobíme veľmi jednoduchý štandard. Nie je to komplexné, ale vám poskytne predstavu o tom, ako môžeme pristupovať porovnávanie Arrays.sort (int []) a Arrays.sort (Celé číslo []) metódy triedenia.

V našej testovacej triede použijeme anotácie konfigurácie:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MILLISECONDS) @Measurement (batchSize = 100000, iterácie = 10) @Warmup (batchSize = 100000, iterácie = 10) verejná trieda ArraySortBenchmark {}

Tu chceme zmerať priemerný čas jednej operácie (Mode.AverageTime) a zobraziť naše výsledky v milisekundách (TimeUnit.MILLISECONDS). Ďalej s batchSize parameter, hovoríme JMH, aby vykonal 100 000 iterácií, aby sa ubezpečil, že naše výsledky majú vysokú presnosť.

4.3. Porovnávacie testy

Pred spustením testov musíme definovať dátové kontajnery, ktoré chceme triediť:

@State (Scope.Thread) verejná statická trieda Inicializovať {Integer [] čísla = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922992, 75160520919, 751605199, 751605199, 751605199 -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] primitive = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 1920, 2094851818, 562424208, -1233745158, 41308167}; }

Vyberme si Celé číslo [] čísla a int []primitívi pole primitívnych prvkov. The @Štát anotácia naznačuje, že premenné deklarované v triede nebudú súčasťou prebiehajúcich testov. Potom ich však môžeme použiť v našich referenčných metódach.

Teraz sme pripravení pridať prvý mikro-benchmark pre Arrays.sort (Integer []):

@Benchmark public Integer [] benchmarkArraysIntegerSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.numbers); návratový stav.čísla; }

Ďalej pre Arrays.sort (int []):

@Benchmark public int [] benchmarkArraysIntSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.primitives); návratový stav.primitívne; }

4.4. Výsledky testu

Nakoniec spustíme naše testy a porovnáme výsledky:

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

Z výsledkov to vidíme Arrays.sort (int []) metóda fungovala lepšie ako Arrays.sort (Object [])v našom teste pravdepodobne z predchádzajúcich dôvodov, ktoré sme identifikovali.

A aj keď sa zdá, že čísla podporujú našu teóriu, na získanie lepšej predstavy by sme potrebovali testovanie s väčšou rozmanitosťou vstupov.

Tiež majte na pamäti, že čísla, ktoré tu uvádzame, sú iba referenčnými výsledkami JMH - mali by sme preto vždy testovať v rozsahu nášho vlastného systému a runtime.

4.5. Prečo potom Timsort?

Asi by sme si teda mali položiť otázku. Ak je program QuickSort rýchlejší, prečo ho nevyužiť pre obe implementácie?

Pozri, QuickSort nie je stabilný, takže ho nemôžeme použiť na triedenie Predmety. V zásade, ak dva ints sú si rovné, nezáleží na tom, že ich relatívne poradie zostáva od jedného rovnaké 2 sa nelíši od iného 2. S objektmi však môžeme triediť podľa jedného a druhého atribútu, čím záleží na počiatočnom poradí.

5. Záver

V tomto článku porovnali sme dve metódy triedenia dostupné v Jave: Arrays.sort (int []) a Arrays.sort (Celé číslo []). Ďalej sme diskutovali o algoritmoch triedenia použitých pri ich implementácii.

Nakoniec sme pomocou benchmarkových testov výkonu ukázali ukážku doby chodu každého z nichmožnosť triedenia.

Úplný kód tohto článku je ako obvykle k dispozícii na serveri GitHub.


$config[zx-auto] not found$config[zx-overlay] not found