A tömbök rendezése (objektum) és tömbök rendezése (int) összehasonlítása

1. Áttekintés

Ebben a gyors bemutatóban összehasonlítjuk a kettőt Tömbök. Rendezés (objektum []) és Tömbök. Rendezés (int []) válogatási műveletek.

Először minden módszert külön leírunk. Ezt követően teljesítményteszteket írunk a futási idejük mérésére.

2. Tömbök. Rendezés (objektum [])

Mielőtt továbblépnénk, fontos ezt szem előtt tartani Tömbök. Rendezés () primitív és referencia típusú tömbökhöz egyaránt működik.

Tömbök. Rendezés (objektum []) referencia típusokat fogad el.

Például van egy tömbünk Egész szám tárgyak:

Egész [] számok = {5, 22, 10, 0};

A tömb rendezéséhez egyszerűen használhatjuk:

Tömbök.rendezés (számok);

Most a számtömb minden elemét növekvő sorrendben tartalmazza:

[0, 5, 10, 22]

Tömbök. Rendezés (objektum []) a TimSort algoritmuson alapul, amely időbeli bonyolultságot ad nekünk O (n log (n)). Röviden: a TimSort az Insertion sort és a MergeSort algoritmusokat használja. Ez azonban még mindig lassabb más rendezési algoritmusokhoz, például a QuickSort egyes megvalósításaihoz képest.

3. Tömbök. Rendezés (int [])

Másrészről, Tömbök. Rendezés (int []) primitível működik int tömbök.

Hasonlóképpen definiálhatunk egy int [] primitívek tömbje:

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

És rendezze a Tömbök. Rendezés (int []). Ezúttal egy primitív tömb elfogadásával:

Tömbök.rendezés (primitívek);

Ennek a műveletnek az eredménye nem fog különbözni az előző példától. És a tételek a primitívek tömb fog kinézni:

[0, 5, 10, 22]

A motorháztető alatt Dual-Pivot Quicksort algoritmust használ. Belső megvalósítása a JDK 10-ből általában gyorsabb, mint a hagyományos egycsuklós Quicksort.

Ez az algoritmus kínál O (n log (n)) átlagos az idő bonyolultsága. Ez egy átlagos átlagos válogatási idő sok gyűjtemény számára. Sőt, az az előnye, hogy teljesen a helyén van, ezért nem igényel további tárolást.

Bár, legrosszabb esetben időbeli összetettsége az O (n2).

4. Idő összehasonlítás

Tehát melyik algoritmus gyorsabb és miért? Először készítsünk néhány elméletet, majd futtatunk néhány konkrét tesztet a JMH-val.

4.1. Minőségi elemzés

Tömbök. Rendezés (objektum []) jellemzően lassabb, mint Tömbök. Rendezés (int []) néhány különböző okból.

Az első a különböző algoritmusok. A QuickSort gyakran gyorsabb, mint a Timsort.

A második az, hogy az egyes módszerek összehasonlítják-e az értékeket.

Lát, mivel Tömbök. Rendezés (objektum []) össze kell hasonlítania az egyik objektumot a másikkal, meg kell hívnia az egyes elemeket összehasonlítani módszer. Legalább ehhez metódus keresésre és hívásra van szükség a veremben, bármi is legyen az összehasonlítási művelet valójában.

Másrészről, Tömbök. Rendezés (int []) egyszerűen olyan primitív relációs operátorokat használhat, mint a < és >, amelyek egyetlen bájtkódú utasítások.

4.2. JMH Paraméterek

Végül derítsük ki mely válogatási módszer gyorsabban fut a tényleges adatokkal. Ehhez a JMH (Java Microbenchmark Harness) eszközt fogjuk használni összehasonlító tesztjeink megírásához.

Tehát itt csak egy nagyon egyszerű benchmarkot fogunk megtenni. Nem átfogó, de ötletet ad arról, hogyan tudunk megközelíteni összehasonlítva Tömbök. Rendezés (int []) és Arrays.sort (Egész szám[]) válogatási módszerek.

A benchmark osztályunkban konfigurációs jegyzeteket fogunk használni:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MILLISECONDS) @Measurement (batchSize = 100000, iterációk = 10) @Warmup (batchSize = 100000, iterációk = 10) public class ArraySortBenchmark {}

Itt szeretnénk megmérni egy művelet átlagos idejét (Mode.AverageTime) és ezredmásodpercekben jelenítsük meg eredményeinket (TimeUnit.MILLISECONDS). Továbbá a csomó méret paraméter, azt mondjuk a JMH-nak, hogy hajtson végre 100 000 ismétlést, hogy megbizonyosodjon eredményeink nagy pontosságáról.

4.3. Összehasonlító tesztek

A tesztek futtatása előtt meg kell határoznunk a rendezni kívánt adattárolókat:

@State (Scope.Thread) public static class Inicializálja az {Integer [] számokat = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, -1051922993, -1051922993 -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] primitívek = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 20948512, 20910512, 20948512 562424208, -1233745158, 41308167}; }

Válasszuk a Egész [] számok és a int []primitívek primitív elemek tömbje. A @Állapot a kommentár azt jelzi, hogy az osztályban deklarált változók nem lesznek a benchmark tesztek részei. Ezeket azonban felhasználhatjuk benchmark módszereinkben.

Most készen állunk az első mikro-benchmark hozzáadására Tömbök. Rendezés (egész szám []):

@Benchmark public Integer [] benchmarkArraysIntegerSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.numbers); visszatérési állapot.számok; }

Következő, a Tömbök. Rendezés (int []):

@Benchmark public int [] benchmarkArraysIntSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.primitives); visszatérő állapot.primitívek; }

4.4. Vizsgálati eredmények

Végül lefuttatjuk tesztjeinket és összehasonlítjuk az eredményeket:

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

Az eredményekből ezt láthatjuk Tömbök. Rendezés (int []) módszer jobban teljesített, mint a Tömbök. Rendezés (objektum [])tesztünkben valószínűleg a korábban azonosított okok miatt.

Annak ellenére, hogy a számok látszólag alátámasztják elméletünket, bár jobb ötlet érdekében többféle bemenettel kell tesztelnünk.

Is, ne feledje, hogy az itt bemutatott számok csak a JMH benchmark eredményei - ezért mindig teszteljünk saját rendszerünk és futási idejük körében.

4.5. Miért akkor Timsort?

Akkor valószínűleg feltennünk kellene magunknak egy kérdést. Ha a QuickSort gyorsabb, miért nem használja mindkét megvalósításhoz?

Lát, A QuickSort nem az stabil, ezért nem tudjuk rendezni Tárgyak. Alapvetően, ha kettő ints egyenlőek, nem számít, hogy relatív sorrendjük ugyanaz marad, mivel egy 2 nem különbözik a másiktól 2. Az objektumokkal azonban rendezhetünk egy, majd egy másik attribútum szerint, így a kezdő sorrend számít.

5. Következtetés

Ebben a cikkben, két, a Java-ban elérhető rendezési módot hasonlítottunk össze: Tömbök. Rendezés (int []) és Arrays.sort (Egész szám[]). Ezenkívül megvitattuk a megvalósításuk során alkalmazott rendezési algoritmusokat.

Végül összehasonlító teljesítménytesztek segítségével bemutattuk mindegyik mintafutási idejétválogatási lehetőség.

Szokás szerint a cikk teljes kódja elérhető a GitHubon.