streamalism.org

1. Pregled

U ovom vodiču, razgovarat ćemo o izvedbi različitih kolekcija iz API-ja Java Collection. Kada govorimo o kolekcijama, obično razmišljamo o Popis, karta, i Postavi strukture podataka i njihove uobičajene implementacije.

Prije svega, pogledati ćemo uvide u složenost Big-O-a za uobičajene operacije, a nakon, prikazat ćemo stvarni broj vremena rada operacija prikupljanja.

2. Složenost vremena

Obično, kad govorimo o vremenskoj složenosti, mislimo na Big-O notaciju. Jednostavno rečeno, notacija opisuje kako vrijeme izvođenja algoritma raste s veličinom unosa.

Dostupni su korisni upisi za učenje više o teoriji notacija Big-O ili praktičnim primjerima Java.

3. Popis

Počnimo s jednostavnim popisom - koji je uređena zbirka.

Ovdje ćemo pogledati pregled izvedbe ArrayList, LinkedList, i CopyOnWriteArrayList implementacije.

3.1. ArrayList

The ArrayList u Javi je podržan nizom. To pomaže razumjeti unutarnju logiku njegove provedbe. Sveobuhvatniji vodič za ArrayList dostupan je u ovom članku.

Dakle, usredotočimo se prvo na vremensku složenost uobičajenih operacija, na visokoj razini:

• dodati() - uzima O (1) vrijeme
• dodaj (indeks, element) - u prosjeku uleti Na) vrijeme
• dobiti() - uvijek je stalno vrijeme O (1) operacija
• ukloniti() - radi linearno Na) vrijeme. Moramo ponoviti čitav niz kako bismo pronašli element koji ispunjava uvjete za uklanjanje
• indexOf ()- također radi u linearnom vremenu. Pregledava unutarnji niz i provjerava svaki element jedan po jedan. Dakle, vremenska složenost za ovu operaciju uvijek zahtijeva Na) vrijeme
• sadrži () - provedba se temelji na indexOf (). Tako će i uletjeti Na) vrijeme

3.2. CopyOnWriteArrayList

Ova provedba Popis sučelje je vrlo korisno pri radu s aplikacijama s više niti. Sigurno je za nit i dobro je objašnjeno u ovom vodiču ovdje.

Evo pregleda performansi Big-O notacije za CopyOnWriteArrayList:

• dodati() - ovisi o položaju kojem dodamo vrijednost, pa je složenost Na)
• dobiti() - je O (1) konstantan vremenski rad
• ukloniti() - uzima Na) vrijeme
• sadrži () - isto tako, složenost je Na)

Kao što vidimo, upotreba ove kolekcije vrlo je skupa zbog karakteristika performansi dodati() metoda.

3.3. LinkedList

LinkedList je linearna struktura podataka koja se sastoji od čvorova koji sadrže podatkovno polje i reference na drugi čvor. Za više LinkedList značajke i mogućnosti, pogledajte ovaj članak ovdje.

Predstavimo prosječnu procjenu vremena koje nam je potrebno za obavljanje nekih osnovnih operacija:

• dodati() - podupirači O (1) konstantno umetanje u bilo kojem položaju
• dobiti() - traženje elementa traje Na) vrijeme
• ukloniti() - uklanjanje elementa također traje O (1) operacija, jer pružamo položaj elementa
• sadrži () - također ima Na) složenost vremena

3.4. Zagrijavanje JVM-a

Sada, da dokažemo teoriju, poigrajmo se stvarnim podacima. Da budemo precizniji, predstavit ćemo rezultate testa JMH (Java Microbenchmark Harness) najčešćih operacija prikupljanja.

U slučaju da niste upoznati s JMH alatom, pogledajte ovaj korisni vodič.

Prvo predstavljamo glavne parametre naših referentnih testova:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @Warmup (iteracije = 10) javna klasa ArrayListBenchmark {}

Zatim smo postavili broj iteracija zagrijavanja na 10. Također, želimo vidjeti prosječno vrijeme izvođenja naših rezultata prikazano u mikrosekundama.

3.5. Referentni testovi

Sada je vrijeme da pokrenemo naše testove performansi. Prvo započinjemo s ArrayList:

@State (Scope.Thread) javna statička klasa MyState {Popis workerList = novi ArrayList (); duge iteracije = 100000; Zaposlenik zaposlenik = novi zaposlenik (100L, "Harry"); int workerIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {workerList.add (new Employee (i, "John")); } workerList.add (zaposlenik); workerIndex = workerList.indexOf (zaposlenik); }}

Unutar našeg ArrayListBenchmark, dodajemo država razred za čuvanje početnih podataka.

Ovdje kreiramo ArrayList od Zaposlenik predmeta. Nakon, inicijaliziramo s 100.000 stavke unutar postaviti() metoda. The @Država ukazuje na to da @Benchmark testovi imaju puni pristup varijablama deklariranim u njemu unutar iste niti.

Napokon, vrijeme je da dodamo referentne testove za add (), contains (), indexOf (), remove (), i dobiti() metode:

@Benchmark javna void testAdd (ArrayListBenchmark.MyState state) {state.employeeList.add (novi zaposlenik (state.iterations + 1, "John")); } @Benchmark javna void testAddAt (ArrayListBenchmark.MyState state) {state.employeeList.add ((int) (state.iterations), novi zaposlenik (state.iterations, "John")); } @Benchmark javni logički testContains (ArrayListBenchmark.MyState state) {return state.employeeList.contains (state.employee); } @Benchmark public int testIndexOf (ArrayListBenchmark.MyState state) {return state.employeeList.indexOf (state.employee); } @Benchmark javni zaposlenik testGet (ArrayListBenchmark.MyState state) {return state.employeeList.get (state.employeeIndex); } @Benchmark javni logički testRemove (ArrayListBenchmark.MyState state) {return state.employeeList.remove (state.employee); }

3.6. Rezultati ispitivanja

Svi rezultati su predstavljeni u mikrosekundama:

Benchmark Mode Cnt Rezultat greške 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.testGet avg.ArtGraft. 624,856 ± 51,101

Iz rezultata koje možemo naučiti, to testContains () i testIndexOf () metode se izvode u približno isto vrijeme. Također možemo jasno vidjeti veliku razliku između testAdd (), testGet () metoda ocjenjuje iz ostalih rezultata. Dodavanje elementa traje 2.296 mikrosekundi i dobivanje jedne je 0,007 mikrosekunde.

Dok pretraživanje ili uklanjanje elementa grubo košta 700 mikrosekundi. Ti su brojevi dokaz teorijskog dijela, gdje smo to naučili dodati(), i dobiti() ima O (1) složenost vremena i ostale metode su Na). n = 10.000 elementi u našem primjeru.

Isto tako, možemo napisati iste testove za CopyOnWriteArrayList kolekcija. Sve što trebamo je zamijeniti ArrayList u popisu zaposlenika s CopyOnWriteArrayList primjer.

Evo rezultata referentnog testa:

Benchmark način CNT rezultat Greška 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

Ovdje, opet, brojke potvrđuju teoriju. Kao što vidimo, testGet () u prosjeku radi za 0,006 ms što možemo smatrati O (1). Uspoređujući s ArrayList, također primjećujemo značajnu razliku između testAdd () rezultati metode. Kao što imamo ovdje Na) složenost za dodati() metoda nasuprot ArrayList's O (1).

Jasno možemo vidjeti linearni rast vremena, kakav je i broj izvedbi 878.166 u usporedbi sa 0.051.

Sad je LinkedList vrijeme:

Benchmark Cnt Ocjena pogreške testDodaj 20 2.580 ± 0.003 testSadrži 20 1808.102 ± 68.155 testGet 20 1561.831 ± 70.876 testUkloni 20 0.006 ± 0.001

Iz rezultata možemo vidjeti da dodavanje i uklanjanje elemenata u LinkedList su prilično brzi.

Nadalje, postoji značajan jaz u izvedbi između operacija dodavanja / uklanjanja i dobivanja / sadržavanja.

4. Karta

S najnovijim verzijama JDK svjedoci smo značajnog poboljšanja performansi za Karta implementacije, poput zamjene LinkedList s uravnoteženom strukturom čvorova stabla u HashMap, LinkedHashMap interne implementacije. Ovo skraćuje traženje elementa u najgorem slučaju iz Na) do O (log (n)) vrijeme tijekom HashMap sudara.

Međutim, ako provedemo pravilno .equals () i .hashcode () metode sudara su malo vjerojatne.

Da biste saznali više o HashMap sudari provjeriti ovaj zapis. Iz zapisa također možemo naučiti da spremanje i dohvaćanje elemenata iz HashMap traje konstantno O (1) vrijeme.

4.1. Testiranje O (1) Operacije

Pokažimo neke stvarne brojeve. Prvo, za HashMap:

Pogreška Benchmark Mode Cnt Rezultat HashMapBenchmark.testContainsKey avgt 20 0,009 ± 0,002 HashMapBenchmark.testGet avgt 20 0,011 ± 0,001 HashMapBenchmark.testPut avgt 20 0,019 ± 0,002 HashMapBenchmark.testUkloni prosjek 20 0,010

Kao što vidimo, brojevi dokazuju O (1) konstantno vrijeme za pokretanje gore navedenih metoda. Sada, napravimo usporedbu HashMap rezultate testa s drugim Karta instance ocjene.

Za sve navedene metode, imamo O (1) za HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap i ConcurrentHashMap.

Predstavimo rezultate preostalih rezultata na testu u obliku jedne tablice:

Benchmark LinkedHashMap IdentityHashMap WeakHashMap ConcurrentHashMap testContainsKey 0,008 0,009 0,014 0,011 testGet 0,011 0,109 0,019 0,012 testPut 0,020 0,013 0,020 0,031 testUkloni 0,011 0,115 0,021 0,019

Iz izlaznih brojeva možemo potvrditi tvrdnje od O (1) složenost vremena.

4.2. Testiranje O (log (n)) Operacije

Za strukturu stabla TreeMap i ConcurrentSkipListMap the put (), get (), remove (), containsKey () vrijeme operacija je O (log (n)).

Ovdje, želimo biti sigurni da će se naši testovi performansi izvoditi približno u logaritamskom vremenu. Iz tog razloga karte inicijaliziramo s n=1000, 10,000, 100,000, 1,000,000 predmeta kontinuirano.

U ovom nas slučaju zanima ukupno vrijeme izvršenja:

broj predmeta (n) 1000 10 000 100 000 1 000 000 svi testovi ukupni rezultat 00:03:17 00:03:17 00:03:30 00:05:27 

Kada n = 1000 imamo ukupno 00:03:17 vrijeme izvršenja u milisekundama. n = 10.000 vrijeme je gotovo nepromijenjeno 00:03:18 ms. n = 100 000 ima manji porast 00:03:30. I konačno, kada n = 1.000.000 trčanje se dovršava 00:05:27 ms.

Nakon usporedbe vremena izvođenja s brojem zapisnik (n) funkcija svakog n, možemo potvrditi da se korelacija obje funkcije podudara.

5. Postavi

Općenito, Postavi je kolekcija jedinstvenih elemenata. Ovdje ćemo ispitati HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, i ConcurrentSkipListSet implementacije Postavi sučelje.

Da bismo bolje razumjeli unutrašnjost HashSet, ovaj vodič je ovdje da vam pomogne.

Sada, krenimo naprijed kako bismo predstavili brojeve vremenske složenosti. Za HashSet, LinkedHashSet, i EnumSet the dodaj (), ukloni () i sadrži () konstanta troškova poslovanja O (1) vrijeme. Zahvaljujući unutarnjem HashMap provedba.

Isto tako, TreeSet ima O (log (n)) složenost vremena za operacije navedene za prethodnu skupinu. To je zbog TreeMap provedba. Složenost vremena za ConcurrentSkipListSet Također O (log (n)) vrijeme, jer se temelji na strukturi podataka preskočiti popis.

Za CopyOnWriteArraySet, the dodaj (), ukloni () i sadrži () metode imaju O (n) prosječnu vremensku složenost.

5.1. Ispitne metode

Sada, krenimo na naše referentne testove:

@Benchmark javni logički testAdd (SetBenchMark.MyState state) {return state.employeeSet.add (state.employee); } @Benchmark javni logički testContains (SetBenchMark.MyState state) {return state.employeeSet.contains (state.employee); } @Benchmark javni logički testRemove (SetBenchMark.MyState state) {return state.employeeSet.remove (state.employee); }

Nadalje, preostale referentne konfiguracije ostavljamo takve kakve jesu.

5.2. Usporedba brojeva

Pogledajmo ponašanje rezultata izvršenja izvršavanja za HashSet i LinkedHashSet imajući n = 1000; 10.000; 100.000 predmeta.

Za HashSet, brojevi su:

Mjerilo 1000 10 000 100 000 .dodaj () 0,026 0,023 0,024 .ukloni () 0,009 0,009 0,009 .sadrži () 0,009 0,009 0,010

Slično tome, rezultati za LinkedHashSet su:

Mjerilo 1000 10 000 100 000 .dodaj () 0,022 0,026 0,027 .ukloni () 0,008 0,012 0,009 .sadrži () 0,008 0,013 0,009

Kao što vidimo, rezultati ostaju gotovo isti za svaku operaciju. Čak i više, kada ih usporedimo s HashMap testni izlazi, i oni izgledaju isto.

Kao rezultat, potvrđujemo da sve testirane metode rade konstantno O (1) vrijeme.

6. Zaključak

U ovom članku, predstavljamo vremensku složenost najčešćih implementacija Java struktura podataka.

Zasebno prikazujemo stvarne performanse izvršavanja svake vrste kolekcije kroz JVM referentne testove. Također smo uspoređivali izvedbu istih operacija u različitim zbirkama. Kao rezultat toga, naučimo odabrati pravu kolekciju koja odgovara našim potrebama.

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