streamalism.org

1. Pregled

U ovom brzom vodiču, usporedit ćemo to dvoje Arrays.sort (Object []) i Nizovi.sort (int []) operacije sortiranja.

Prvo ćemo opisati svaku metodu zasebno. Nakon toga napisat ćemo testove performansi kako bismo izmjerili njihovo radno vrijeme.

2. Arrays.sort (Object [])

Prije nego što krenemo naprijed, važno je to imati na umu Nizovi.sort () radi i za primitivne nizove i za nizove referentnog tipa.

Arrays.sort (Object []) prihvaća referentne vrste.

Na primjer, imamo niz Cijeli broj objekti:

Cijeli broj [] brojevi = {5, 22, 10, 0};

Za sortiranje niza možemo jednostavno upotrijebiti:

Nizovi.sort (brojevi);

Sada niz brojeva ima sve elemente u rastućem redoslijedu:

[0, 5, 10, 22]

Arrays.sort (Object []) temelji se na algoritmu TimSort, dajući nam vremensku složenost od O (n zapis (n)). Ukratko, TimSort koristi algoritme Insertion sort i MergeSort. Međutim, i dalje je sporiji u usporedbi s drugim algoritmima za sortiranje poput nekih implementacija QuickSort-a.

3. Nizovi.sort (int [])

S druge strane, Nizovi.sort (int []) radi s primitivnim int nizovi.

Slično tome, možemo definirati int [] niz primitiva:

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

I to poredati s drugom implementacijom Nizovi.sort (int []). Ovaj put, prihvaćajući niz primitiva:

Nizovi.sort (primitivi);

Rezultat ove operacije neće se razlikovati od prethodnog primjera. I predmeti u primitivci niz će izgledati kao:

[0, 5, 10, 22]

Ispod haube koristi algoritam Dual-Pivot Quicksort. Njegova interna implementacija iz JDK 10 tipično je brža od tradicionalnog quickort-a s jednim pivotom.

Ovaj algoritam nudi O (n zapis (n)) prosječno složenost vremena. To je izvrsno prosječno vrijeme sortiranja za mnoge kolekcije. Štoviše, prednost mu je što je potpuno na svom mjestu, tako da ne zahtijeva nikakvo dodatno skladištenje.

Iako, u najgorem je slučaju njegova vremenska složenost O (n2).

4. Usporedba vremena

Pa, koji je algoritam brži i zašto? Prvo napravimo teoriju, a zatim ćemo pokrenuti neke konkretne testove s JMH.

4.1. Kvalitativna analiza

Arrays.sort (Object []) je obično sporiji u odnosu na Nizovi.sort (int []) iz nekoliko različitih razloga.

Prvi su različiti algoritmi. QuickSort je često brži od Timsorta.

Drugo je kako svaka metoda uspoređuje vrijednosti.

Vidjeti, od Arrays.sort (Object []) treba usporediti jedan objekt s drugim, mora pozvati svaki element usporediTo metoda. U najmanju ruku, ovo zahtijeva traženje metode i guranje poziva na stog uz ono što operacija usporedbe zapravo jest.

S druge strane, Nizovi.sort (int []) mogu jednostavno koristiti primitivne relacijske operatore poput < i >, koji su pojedinačne upute bajt koda.

4.2. JMH parametri

Napokon, saznajmo koja metoda sortiranja teče brže sa stvarnim podacima. Za to ćemo upotrijebiti alat JMH (Java Microbenchmark Harness) za pisanje naših referentnih testova.

Dakle, ovdje ćemo napraviti vrlo jednostavno mjerilo. Nije sveobuhvatan, ali dat će nam ideju o tome kako možemo pristupiti uspoređujući Nizovi.sort (int []) i Nizovi.sort (Cijeli broj []) metode sortiranja.

U našoj referentnoj klasi koristit ćemo napomene o konfiguraciji:

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

Ovdje želimo izmjeriti prosječno vrijeme za jednu operaciju (Mode.AverageTime) i prikazati naše rezultate u milisekundama (TimeUnit.MILLISECONDS). Nadalje, s batchSize parametar, kažemo JMH-u da izvede 100 000 iteracija kako bi bili sigurni da naši rezultati imaju visoku preciznost.

4.3. Referentni testovi

Prije izvođenja testova moramo definirati spremnike podataka koje želimo razvrstati:

@State (Scope.Thread) javna statička klasa Initialize {Integer [] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -105192299195, -10519229995, -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] primitivi = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 209485658, 209485658 562424208, -1233745158, 41308167}; }

Odaberimo Cijeli brojevi [] brojevi i int []primitivci niz primitivnih elemenata. The @Država napomena označava da varijable deklarirane u klasi neće biti dio izvođenja referentnih testova. Međutim, tada ih možemo koristiti u našim referentnim metodama.

Sada smo spremni dodati prvo mikro-mjerilo za Arrays.sort (Integer []):

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

Dalje, za Nizovi.sort (int []):

@Benchmark public int [] benchmarkArraysIntSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.primitive); povratno stanje.primitivi; }

4.4. Rezultati ispitivanja

Na kraju pokrećemo testove i uspoređujemo rezultate:

Benchmark Mode Cnt Score Greške Jedinice benchmarkArraysIntSort avgt 10 1,095 ± 0,022 ms / op benchmarkArraysIntegerSort avgt 3 3,888 ± 0,060 ms / op

Iz rezultata to možemo vidjeti Nizovi.sort (int []) metoda izvedena bolje nego da Arrays.sort (Object [])u našem testu, vjerojatno iz ranijih razloga koje smo identificirali.

Iako se čini da brojevi podržavaju našu teoriju, premda bismo morali napraviti testiranje s većim brojem ulaznih podataka kako bismo dobili bolju ideju.

Također, imajte na umu da su brojevi koje ovdje predstavljamo samo rezultati mjerenja JMH - tako da bismo uvijek trebali testirati u okviru vlastitog sustava i vremena izvođenja.

4.5. Zašto onda Timsort?

Onda bismo si vjerojatno trebali postaviti pitanje. Ako je QuickSort brži, zašto ga ne koristiti za obje implementacije?

Vidjeti, QuickSort nije stabilan, tako da ga ne možemo koristiti za sortiranje Predmeti. U osnovi, ako dva ints jednaki, nema veze što njihov relativni poredak ostaje isti od jednog 2 se ne razlikuje od drugog 2. Međutim, s objektima možemo sortirati prema jednom atributu, a zatim prema drugom, čineći početni redoslijed bitnim.

5. Zaključak

U ovom članku, usporedili smo dvije metode sortiranja dostupne u Javi: Nizovi.sort (int []) i Nizovi.sort (Cijeli broj []). Pored toga, razgovarali smo o algoritmima za sortiranje koji se koriste u njihovim implementacijama.

Napokon, uz pomoć referentnih testova, pokazali smo uzorak vremena rada svakog od njihopcija sortiranja.

Kao i obično, cjeloviti kôd za ovaj članak dostupan je na GitHubu.