streamalism.org

1. Prehľad

V tomto návode povieme si o výkone rôznych kolekcií z Java Collection API. Keď hovoríme o zbierkach, zvyčajne myslíme na Zoznam, Mapa, a Nastaviť dátové štruktúry a ich spoločné implementácie.

Najskôr sa pozrieme na štatistiku zložitosti Big-O pre bežné operácie a potom ukážeme skutočné počty prevádzkových časov niektorých operácií zhromažďovania.

2. Časová zložitosť

Zvyčajne keď hovoríme o časovej zložitosti, máme na mysli zápis Big-O. Jednoducho povedané, notácia popisuje, ako rastie čas na vykonanie algoritmu s veľkosťou vstupu.

K dispozícii sú užitočné zápisy, kde sa dozviete viac o teórii zápisu Big-O alebo praktických príkladoch jazyka Java.

3. Zoznam

Začnime jednoduchým zoznamom - čo je objednaná zbierka.

Tu sa pozrieme na prehľad výkonnosti ArrayList, LinkedList, a CopyOnWriteArrayList implementácie.

3.1. ArrayList

The ArrayList v Jave je kryté poľom. To pomáha pochopiť vnútornú logiku jeho implementácie. Komplexnejší sprievodca pre ArrayList je k dispozícii v tomto článku.

Poďme sa teda najskôr zamerať na časovú zložitosť bežných operácií na vysokej úrovni:

• pridať () - berie O (1) čas
• pridať (index, prvok) - v priemere beží v O (n) čas
• dostať () - je vždy konštantný čas O (1) prevádzka
• odstrániť () - beží lineárne O (n) čas. Aby sme našli prvok spôsobilý na odstránenie, musíme iterovať celé pole
• indexOf ()- beží tiež v lineárnom čase. Iteruje cez interné pole a kontroluje každý prvok jeden po druhom. Časová zložitosť tejto operácie teda vždy vyžaduje O (n) čas
• obsahuje () - implementácia je založená na indexOf (). Tak to tiež zabehne O (n) čas

3.2. CopyOnWriteArrayList

Táto implementácia Zoznam rozhranie je veľmi užitočné pri práci s viacvláknovými aplikáciami. Je to bezpečné pre vlákna a v tejto príručke je to dobre vysvetlené.

Tu je prehľad výkonu Big-O notácie pre CopyOnWriteArrayList:

• pridať () - záleží na pozícii, ktorej pridáme hodnotu, takže zložitosť je O (n)
• dostať () - je O (1) prevádzka v konštantnom čase
• odstrániť () - berie O (n) čas
• obsahuje () - podobne je to aj so zložitosťou O (n)

Ako vidíme, použitie tejto kolekcie je veľmi drahé kvôli výkonnostným charakteristikám pridať () metóda.

3.3. LinkedList

LinkedList je lineárna dátová štruktúra, ktorá sa skladá z uzlov obsahujúcich dátové pole a odkazu na iný uzol. Pre viac LinkedList funkcií a schopností, pozrite sa na tento článok tu.

Uveďme priemerný odhad času potrebného na vykonanie niekoľkých základných operácií:

• pridať () - podporuje O (1) vkladanie v konštantnom čase do ľubovoľnej polohy
• dostať () - hľadanie prvku trvá - O (n) čas
• odstrániť () - odstránenie prvku tiež trvá O (1) operácia, pretože poskytujeme polohu prvku
• obsahuje () - taktiež má O (n) časová zložitosť

3.4. Zahrievanie JVM

Teraz, aby sme dokázali teóriu, poďme sa pohrať s aktuálnymi údajmi. Presnejšie uvedieme výsledky testu JMH (Java Microbenchmark Harness) najbežnejších operácií zhromažďovania.

Ak nástroj JMH nepoznáte, prečítajte si tohto užitočného sprievodcu.

Najprv predstavíme hlavné parametre našich testovacích testov:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @Warmup (iterácie = 10) verejná trieda ArrayListBenchmark {}

Potom sme nastavili číslo iterácií zahrievania na 10. Prajeme si tiež, aby sa priemerná doba trvania našich výsledkov zobrazila v mikrosekundách.

3.5. Porovnávacie testy

Teraz je čas vykonať testy výkonnosti. Najprv začneme s ArrayList:

@State (Scope.Thread) verejná statická trieda MyState {List employeeList = new ArrayList (); dlhé iterácie = 100000; Zamestnanec zamestnanec = nový zamestnanec (100 L, „Harry“); int zamestnanecIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {employeeList.add (new Employee (i, "John")); } employeeList.add (zamestnanec); employeeIndex = employeeList.indexOf (zamestnanec); }}

Vo vnútri našej ArrayListBenchmark, pridáme Štát triedy na uchovanie počiatočných údajov.

Tu tvoríme ArrayList z Zamestnanec predmety. Po, inicializujeme pomocou 100.000 predmety vo vnútri nastaviť() metóda. The @Štát naznačuje, že @Benchmark testy majú plný prístup k premenným deklarovaným v ňom v rovnakom vlákne.

Na záver je čas pridať testovacie testy pre add (), contains (), indexOf (), remove (), a dostať () metódy:

@Benchmark public void testAdd (ArrayListBenchmark.MyState state) {state.employeeList.add (nový zamestnanec (state.iterations + 1, "John")); } @Benchmark public void testAddAt (ArrayListBenchmark.MyState state) {state.employeeList.add ((int) (state.iterations), new Employee (state.iterations, "John")); } @Benchmark public boolean testContains (ArrayListBenchmark.MyState state) {return state.employeeList.contains (state.employee); } @Benchmark public int testIndexOf (ArrayListBenchmark.MyState state) {návrat state.employeeList.indexOf (state.employee); } @Benchmark public Employee testGet (ArrayListBenchmark.MyState state) {return state.employeeList.get (state.employeeIndex); } @Benchmark public boolean testRemove (ArrayListBenchmark.MyState state) {return state.employeeList.remove (state.employee); }

3.6. Výsledky testu

Všetky výsledky sú uvedené v mikrosekundách:

Benchmark Mode Cnt Score Error ArrayListBenchmark.testAdd avgt 20 2.296 ± 0.007 ArrayListBenchmark.testAddAt avgt 20 101.092 ± 14.145 ArrayListBenchmark.testContains avgt 20 709,404 ± 64,331 ArrayListBenchmark.test Získať priemet 20 0,007 624 856 ± 51,101

Z výsledkov sa môžeme dozvedieť, že testContains () a testIndexOf () metódy prebiehajú približne v rovnakom čase. Vidíme tiež zreteľne vidieť obrovský rozdiel medzi testAdd (), testGet () skóre metódy zo zvyšných výsledkov. Pridanie prvku trvá 2.296 mikrosekúnd a získanie jednej je 0,007 mikrosekundovej operácie.

Pri vyhľadávaní alebo odstraňovaní prvku sú to zhruba náklady 700 mikrosekundy. Tieto čísla sú dôkazom teoretickej časti, kde sme sa to dozvedeli add (), a dostať () má O (1) časová zložitosť a ostatné metódy sú O (n). n = 10 000 prvkov v našom príklade.

Rovnako môžeme napísať rovnaké testy pre CopyOnWriteArrayList zbierka. Všetko, čo potrebujeme, je vymeniť ArrayList v zozname zamestnancov pomocou CopyOnWriteArrayList inštancia.

Tu sú výsledky referenčného testu:

Porovnávací režim Cnt Skóre Chyba 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

Aj tu čísla potvrdzujú teóriu. Ako vidíme, testGet () v priemere beží za 0,006 ms, čo môžeme považovať za O (1). V porovnaní s ArrayList, všimli sme si tiež výrazný rozdiel medzi testAdd () výsledky metódy. Ako tu máme O (n) zložitosť pre pridať () metóda verzus ArrayList je O (1).

Jasne vidíme lineárny rast času, tak ako sú čísla výkonu 878.166 v porovnaní s 0.051.

Teraz je LinkedList čas:

Benchmark Cnt Score Error test Pridajte 20 2,580 ± 0,003 test Obsahuje 20 1808,102 ± 68,155 test Získajte 20 1561 831 ± 70 876 test Odstráňte 20 0,006 ± 0,001

Z výsledkov vidíme, že pridávanie a odstraňovanie prvkov v LinkedList sú dosť rýchle.

Ďalej existuje značná výkonnostná medzera medzi operáciami pridania / odstránenia a získania / obsahuje.

4. Mapa

S najnovšími verziami JDK sme svedkami výrazného zlepšenia výkonu pre Mapa implementácie, ako napríklad výmena LinkedList s vyváženou štruktúrou uzlov stromu v HashMap, LinkedHashMap interné implementácie. Toto skracuje najhorší scenár pri vyhľadávaní prvkov O (n) do O (log (n)) čas počas HashMap kolízie.

Ak však implementujeme správne .equals () a .hashcode () kolízie metód sú nepravdepodobné.

Ak sa chcete dozvedieť viac o HashMap kolízie, pozrite si tento zápis. Z zápisu sa tiež môžeme dozvedieť, že ukladanie a načítanie prvkov z HashMap trvá neustále O (1) čas.

4.1. Testovanie O (1) Operácie

Ukážme niekoľko skutočných čísel. Po prvé, pre HashMap:

Chyba Benchmark Cnt skóre Chyba HashMapBenchmark.testContainsKey priem. 20 0,009 ± 0,002 HashMapBenchmark.test Získať priem. 20 0,011 ± 0,001 HashMapBenchmark.test Vložte priem. 20 0,019 ± 0,002 HashMapBenchmark.testOdstrániť priem. 20 0,010 ± 0,001

Ako vidíme, čísla dokazujú O (1) konštantný čas na spustenie vyššie uvedených metód. Teraz urobme porovnanie HashMap výsledky testov u druhého Mapa inštančné skóre.

Pre všetky uvedené metódy máme O (1) pre HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap a ConcurrentHashMap.

Uveďme výsledky zostávajúcich výsledkov testov vo forme jednej tabuľky:

Benchmark LinkedHashMap IdentityHashMap WeakHashMap ConcurrentHashMap testContainsKey 0,008 0,009 0,014 0,011 testZískať 0,011 0,109 0,019 0,012 testZadať 0,020 0,013 0,020 0,031 testOdstrániť 0,011 0,115 0,021 0,019

Z výstupných čísel môžeme potvrdiť tvrdenia o O (1) časová zložitosť.

4.2. Testovanie O (log (n)) Operácie

Pre stromovú štruktúru TreeMap a ConcurrentSkipListMap the put (), get (), remove (), containsKey () prevádzkový čas je O (log (n)).

Tu, chceme sa uistiť, že naše testy výkonu budú prebiehať približne v logaritmickom čase. Z tohto dôvodu inicializujeme mapy pomocou n=1000, 10,000, 100,000, 1,000,000 položky nepretržite.

V tomto prípade nás zaujíma celková doba vykonania:

počet položiek (n) 1 000 10 000 100 000 1 000 000 všetky testy celkové skóre 00:03:17 00:03:17 00:03:30 00:05:27 

Kedy n = 1 000 máme spolu 00:03:17 milisekundový čas vykonania. n = 10 000 čas je takmer nezmenený 00:03:18 ms. n = 100 000 má malý nárast 00:03:30. A nakoniec, keď n = 1 000 000 beh sa dokončuje 00:05:27 ms.

Po porovnaní runtime čísel s denník (n) funkcie každého n, môžeme potvrdiť, že korelácia oboch funkcií sa zhoduje.

5. Nastaviť

Spravidla Nastaviť je zbierka jedinečných prvkov. Tu preskúmame HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, a ConcurrentSkipListSet implementácie Nastaviť rozhranie.

Pre lepšie pochopenie vnútorných častí HashSet, táto príručka vám pomôže.

Teraz poďme dopredu a predstavme čísla časovej zložitosti. Pre HashSet, LinkedHashSet, a EnumSet the add (), remove () a obsahuje () prevádzkové náklady konštantné O (1) čas. Vďaka internému HashMap implementácia.

Rovnako tak TreeSet má O (log (n)) časová zložitosť pre operácie uvedené pre predchádzajúcu skupinu. Je to kvôli TreeMap implementácia. Časová zložitosť pre ConcurrentSkipListSet je tiež O (log (n)) čas, pretože je založený na dátovej štruktúre zoznamov preskočených.

Pre CopyOnWriteArraySet, the add (), remove () a obsahuje () metódy majú O (n) priemernú časovú zložitosť.

5.1. Skúšobné metódy

Teraz prejdime k našim testom benchmarku:

@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 public boolean testRemove (SetBenchMark.MyState state) {return state.employeeSet.remove (state.employee); }

Ďalej ponecháme zostávajúce konfigurácie referenčných hodnôt tak, ako sú.

5.2. Porovnávanie čísel

Pozrime sa na správanie skóre vykonávania za behu pre HashSet a LinkedHashSet majúce n = 1 000; 10 000; 100 000 položky.

Pre HashSet, čísla sú:

Referenčná hodnota 1 000 10 000 100 000. Pridať () 0,026 0,023 0,024. Odstrániť () 0,009 0,009 0,009 .obsahuje () 0,009 0,009 0,010

Podobne výsledky pre LinkedHashSet sú:

Referenčná hodnota 1 000 10 000 100 000. Pridať () 0,022 0,026 0,027. Odstrániť () 0,008 0,012 0,009 .obsahuje () 0,008 0,013 0,009

Ako vidíme, skóre zostáva pri každej operácii takmer rovnaké. O to viac, keď ich porovnáme s HashMap testovacie výstupy, vyzerajú rovnako.

Vo výsledku potvrdzujeme, že všetky testované metódy prebiehajú konštantne O (1) čas.

6. Záver

V tomto článku uvádzame časovú zložitosť najbežnejších implementácií dátových štruktúr Java.

Samostatne ukazujeme skutočný výkon za behu každého typu kolekcie prostredníctvom testov JVM benchmark. Porovnali sme tiež výkonnosť tých istých operácií v rôznych kolekciách. Vďaka tomu sa naučíme vyberať si správnu kolekciu, ktorá vyhovuje našim potrebám.

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