streamalism.org

1. Áttekintés

Ebben az oktatóanyagban a Java Collection API különböző gyűjteményeinek teljesítményéről fogunk beszélni. Amikor gyűjteményekről beszélünk, általában a Lista, térkép, és Készlet adatstruktúrák és közös megvalósításaik.

Először megvizsgáljuk a közös műveletek Big-O komplexitását, majd ezután megmutatjuk egyes gyűjtési műveletek futási idejének valós számát.

2. Az idő komplexitása

Általában, amikor az idő összetettségéről beszélünk, a Big-O jelölésre hivatkozunk. Egyszerűen fogalmazva: a jelölés leírja, hogyan növekszik az algoritmus végrehajtásának ideje a bemenet nagyságával.

Hasznos leírások állnak rendelkezésre a Big-O jelöléselmélet vagy a Java gyakorlati példáinak megismeréséhez.

3. Lista

Kezdjük egy egyszerű listával - amely egy rendezett gyűjtemény.

Itt megnézzük a ArrayList, LinkedList, és CopyOnWriteArrayList megvalósítások.

3.1. Tömb lista

A Tömb lista Java-ban egy tömb támogatja. Ez segít megérteni a megvalósítás belső logikáját. Átfogóbb útmutató a Tömb lista elérhető ebben a cikkben.

Tehát először koncentráljunk a közös műveletek időbeli összetettségére, magas szinten:

• add () - veszi O (1) idő
• add (index, elem) - átlagosan befut Tovább) idő
• kap() - mindig állandó idő O (1) művelet
• eltávolítás () - lineárisan fut Tovább) idő. Meg kell ismételnünk a teljes tömböt, hogy megtaláljuk az eltávolításra alkalmas elemet
• indexe()- szintén lineáris időben fut. Iterál a belső tömbön keresztül, és minden elemet egyesével ellenőriz. Tehát a művelet időbeli összetettsége mindig megköveteli Tovább) idő
• tartalmaz () - a megvalósítás alapja indexe(). Tehát be is fut Tovább) idő

3.2. CopyOnWriteArrayList

A Lista interfész az nagyon hasznos, ha több szálon futó alkalmazásokkal dolgozunk. Menetbiztos, és ebben az útmutatóban jól elmagyarázzák.

Itt található a Big-O jelölés áttekintése CopyOnWriteArrayList:

• add () - attól függ, hogy milyen pozíciónk adunk hozzá értéket, tehát a komplexitás az Tovább)
• kap() - van O (1) állandó idejű működés
• eltávolítás () - veszi Tovább) idő
• tartalmaz () - ugyanígy a bonyolultság is Tovább)

Mint láthatjuk, ennek a gyűjteménynek a használata a nagyon jellemzői miatt nagyon drága add () módszer.

3.3. LinkedList

LinkedList egy lineáris adatstruktúra, amely egy adatmezőt tartó csomópontokból és egy másik csomópontra való hivatkozásból áll. Többért LinkedList jellemzőit és képességeit, tekintse meg ezt a cikket itt.

Bemutatjuk az alapműveletek elvégzéséhez szükséges idő átlagos becslését:

• add () - támogatja O (1) állandó idejű beillesztés bármely helyzetbe
• kap() - egy elem keresése eltart Tovább) idő
• eltávolítás () - egy elem eltávolítása szintén eltart O (1) műveletet, mivel megadjuk az elem helyzetét
• tartalmaz () - van is Tovább) az idő bonyolultsága

3.4. A JVM bemelegítése

Most, hogy bebizonyítsuk az elméletet, játsszunk a tényleges adatokkal. Pontosabban: bemutatjuk a leggyakoribb gyűjtési műveletek JMH (Java Microbenchmark Harness) teszt eredményeit.

Ha nem ismeri a JMH eszközt, olvassa el ezt a hasznos útmutatót.

Először bemutatjuk benchmark tesztjeink fő paramétereit:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @Warmup (iterációk = 10) public class ArrayListBenchmark {}

Ezután a bemelegedési ismétlések számát állítjuk 10. Azt is szeretnénk, hogy mikroszekundumban jelenítsük meg eredményeink átlagos futási idejét.

3.5. Összehasonlító tesztek

Itt az ideje, hogy lefuttassuk a teljesítménytesztjeinket. Először a Tömb lista:

@State (Scope.Thread) nyilvános statikus osztály MyState {List workerList = new ArrayList (); hosszú iterációk = 100000; Alkalmazott alkalmazott = új alkalmazott (100L, "Harry"); int alkalmazottIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {workerList.add (new Employee (i, "John")); } workerList.add (alkalmazott); workerIndex = workerList.indexOf (alkalmazott); }}

Belül a mi ArrayListBenchmark, hozzáadjuk a Állapot osztály a kezdeti adatok tárolására.

Itt létrehozunk egy Tömb lista nak,-nek Munkavállaló tárgyakat. Utána, azzal inicializáljuk 100.000 tételek a beállít() módszer. A @Állapot azt jelzi, hogy a @Viszonyítási alap a tesztek teljes hozzáféréssel rendelkeznek az ugyanazon szálon belül deklarált változókhoz.

Végül itt az ideje, hogy hozzáadjuk a add (), tartalmaz (), indexOf (), távolítsa el (), és kap() mód:

@Benchmark public void testAdd (ArrayListBenchmark.MyState state) {state.employeeList.add (new Employee (state.iterations + 1, "John")); } @Benchmark public void testAddAt (ArrayListBenchmark.MyState state) {state.employeeList.add ((int) (state.iterations), new Employee (state.iterations, "John")); } @Benchmark nyilvános logikai tesztContains (ArrayListBenchmark.MyState state) {return state.employeeList.contains (state.employee); } @Benchmark public int testIndexOf (ArrayListBenchmark.MyState state) {return state.employeeList.indexOf (state.employee); } @Benchmark public Employee testGet (ArrayListBenchmark.MyState state) {return state.employeeList.get (state.employeeIndex); } @Benchmark nyilvános logikai tesztRemove (ArrayListBenchmark.MyState állapot) {return state.employeeList.remove (state.employee); }

3.6. Vizsgálati eredmények

Az összes eredményt mikroszekundumban mutatjuk be:

Benchmark Mode Cnt Score Error ArrayListBenchmark.testAdd avgt 20 2.296 ± 0.007 ArrayListBenchmark.testAddAt avgt 20 101.092 ± 14.145 ArrayListBenchmark.testCon avgt 20 709.404 ± 64.331 ArrayListBenchmark.testGet avgtay 20 0.007 ± 0.007 ± 0.007 ± 0.007 ± 0.001 624.856 ± 51.101

Az eredményekből megtudhatjuk testContains () és testIndexOf () a módszerek körülbelül ugyanabban az időben futnak. Jól látható a hatalmas különbség is a testAdd (), testGet () a módszer eredményei a többi eredményből származnak. Egy elem hozzáadásához 2 kell.296 és másodpercenként 0,007 másodperc.

Miközben egy elem keresése vagy eltávolítása nagyjából kerül 700 mikroszekundum. Ezek a számok bizonyítják az elméleti részt, ahol ezt megtanultuk add (), és kap() van O (1) az idő bonyolultsága és a többi módszer Tovább). n = 10 000 példáink elemei.

Ugyanígy megírhatjuk ugyanazokat a teszteket CopyOnWriteArrayList Gyűjtemény. Minden amire szükségünk van a Tömb lista a workerList-ben a CopyOnWriteArrayList példa.

Itt vannak a benchmark teszt eredményei:

Benchmark Mode Cnt Score Error CopyOnWriteBenchmark.testAdd avgt 20 652,189 ± 36,641 CopyOnWriteBenchmark.testAddAt avgt 20 897,258 ± 35,363 CopyOnWriteBenchmark.testContains avgt 20 537,098 ± 54,235 CopyOnWriteBenchmark.testGet avgt 20 0,006 ± 0,001 CopyOnWriteBenchmark.testIndexOf avgt 20 547,207 ± 48,904 CopyOnWriteBenchmark.testRemove avgt 20 648,162 ± 138,379

A számok itt is megerősítik az elméletet. Ahogy látjuk, testGet () átlagosan 0,006 ms alatt fut, amelyet úgy tekinthetünk O (1). Összehasonlítva Tömb lista, észrevesszük a jelentős különbséget is testAdd () módszer eredményei. Ahogy itt van Tovább) összetettsége a add () módszer versus Az ArrayList O-ja (1).

Jól láthatjuk az idő lineáris növekedését, ahogyan a teljesítményszámok is 878.166 összehasonlítva 0.051.

Most az LinkedList idő:

Benchmark Cnt Score Hibateszt 20 20 580 ± 0,003 teszt tartalmaz 20 1808,102 ± 68,155 tesztet kap 20 1561,831 ± 70,876 teszt

A pontszámokból láthatjuk, hogy elemek hozzáadása és eltávolítása LinkedList elég gyorsak.

Ezenkívül jelentős teljesítménybeli különbség van az add / remove és a get / tartalmaz műveletek között.

4. Térkép

A legújabb JDK verziókkal a teljesítmény jelentős javulásának lehetünk tanúi Térkép megvalósítások, például a LinkedList kiegyensúlyozott fa csomópontszerkezettel HashMap, LinkedHashMap belső megvalósítások. Ez lerövidíti az elemkeresés legrosszabb esetét Tovább) nak nek O (log (n)) ideje alatt HashMap ütközések.

Ha azonban megfelelő módon valósítjuk meg .egyenlő () és .hash kód() módszerek ütközése nem valószínű.

További információkért HashMap ütközések nézze meg ezt az írást. Az írásból azt is megtudhatjuk, hogy az elemek tárolása és visszakeresése HashMap állandó O (1) idő.

4.1. Tesztelés O (1) Tevékenységek

Mutassunk néhány tényleges számot. Először is a HashMap:

Benchmark Mode Cnt Pontszám hiba

Mint látjuk, a számok bizonyítják a O (1) állandó idő a fent felsorolt ​​módszerek futtatásához. Most végezzük el a HashMap teszt pontszámok a másikkal Térkép példány pontszámok.

Az összes felsorolt ​​módszer esetében nekünk van O (1) mert HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap és ConcurrentHashMap.

Bemutatjuk a fennmaradó teszteredményeket egy táblázat formájában:

Benchmark LinkedHashMap IdentityHashMap WeakHashMap ConcurrentHashMap teszt Tartalmaz kulcsot 0,008 0,009 0,014 0,011 teszt

A kimeneti számokból megerősíthetjük a O (1) az idő bonyolultsága.

4.2. Tesztelés O (log (n)) Tevékenységek

A fa szerkezetéhez TreeMap és ConcurrentSkipListMap a put (), get (), remove (), tartalmaz Key () a műveletek ideje O (log (n)).

Itt, szeretnénk megbizonyosodni arról, hogy a teljesítménytesztjeink hozzávetőleg logaritmikus időben fognak futni. Ezért a n-vel inicializáljuk a térképeket=1000, 10,000, 100,000, 1,000,000 tételek folyamatosan.

Ebben az esetben a végrehajtás teljes ideje érdekel:

tételek száma (n) 1000 10 000 100 000 1 000 000 összes teszt összesített pontszáma 00:03:17 00:03:17 00:03:30 00:05:27 

Mikor n = 1000 megvan az összes 00:03:17 ezredmásodpercek végrehajtási ideje. n = 10 000 az idő szinte változatlan 00:03:18 ms. n = 100 000 kisebb növekedéssel rendelkezik 00:03:30. És végül mikor n = 1 000 000 a futás befejeződik 00:05:27 ms.

Miután összehasonlította a futási számokat a napló (n) funkciója n, megerősíthetjük, hogy mindkét függvény összefüggése megegyezik.

5. Készlet

Általában, Készlet egyedi elemek gyűjteménye. Itt fogjuk megvizsgálni a HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, és ConcurrentSkipListSet a Készlet felület.

Hogy jobban megértsük a HashSet, ez az útmutató a segítségére van.

Most ugorjunk előre, hogy bemutassuk az idő összetettségének számát. Mert HashSet, LinkedHashSet, és EnumSet a Hozzáad eltávolít() és tartalmaz () a műveletek költsége állandó O (1) idő. A belsőnek köszönhetően HashMap végrehajtás.

Hasonlóképpen a TreeSet van O (log (n)) az idő bonyolultsága az előző csoportnál felsorolt ​​műveletekhez. Ez a TreeMap végrehajtás. Az idő összetettsége ConcurrentSkipListSet is O (log (n)) idő, mivel a kihagyási lista adatstruktúráján alapul.

Mert CopyOnWriteArraySet, a Hozzáad eltávolít() és tartalmaz () a módszerek O (n) átlagos idő komplexitással bírnak.

5.1. Vizsgálati módszerek

Most folytassuk az összehasonlító tesztekkel:

@Benchmark public boolean testAdd (SetBenchMark.MyState state) {return state.employeeSet.add (state.employee); } @Benchmark public Boolean testContains (SetBenchMark.MyState state) {return state.employeeSet.contains (state.employee); } @Benchmark nyilvános logikai tesztRemove (SetBenchMark.MyState állapot) {return state.employeeSet.remove (state.employee); }

Ezenkívül a fennmaradó referencia-konfigurációkat hagyjuk úgy, ahogy vannak.

5.2. A számok összehasonlítása

Lássuk a futásidejű végrehajtási pontszám viselkedését HashSet és LinkedHashSet miután n = 1000; 10 000; 100 000 elemeket.

A HashSet, a számok a következők:

1000-es referenciaérték 10 000 100 000 .add () 0,026 0,023 0,024 .eltávolítás () 0,009 0,009 0,009. Tartalmaz () 0,009 0,009 0,010

Hasonlóképpen, a LinkedHashSet vannak:

1000-es referenciaérték 10 000 100 000 .add () 0,022 0,026 0,027 .eltávolítás () 0,008 0,012 0,009. Tartalmaz () 0,008 0,013 0,009

Amint látjuk, az egyes műveletek pontszáma majdnem ugyanaz. Még inkább, ha összehasonlítjuk őket a HashMap teszt kimenetek, ugyanúgy néznek ki.

Ennek eredményeként megerősítjük, hogy az összes tesztelt módszer állandóan működik O (1) idő.

6. Következtetés

Ebben a cikkben, bemutatjuk a Java adatszerkezetek leggyakoribb megvalósításainak időbeli összetettségét.

Külön-külön, a JVM benchmark tesztjein keresztül mutatjuk be az egyes gyűjtemények tényleges futási idejű teljesítményét. Összehasonlítottuk ugyanazon műveletek teljesítményét a különböző gyűjteményekben is. Ennek eredményeként megtanuljuk kiválasztani az igényeinknek megfelelő kollekciót.

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