streamalism.org

1. Oversikt

I denne veiledningen, Vi snakker om ytelsen til forskjellige samlinger fra Java Collection API. Når vi snakker om samlinger, tenker vi vanligvis på Liste, kart, og Sett datastrukturer og deres vanlige implementeringer.

Først og fremst vil vi se på Big-O-kompleksitetsinnsikt for vanlige operasjoner, og etterpå vil vi vise det virkelige antallet av noen innsamlingsoperasjoner.

2. Tidskompleksitet

Som oftest, når vi snakker om tidskompleksitet, viser vi til Big-O-notasjon. Enkelt sagt beskriver notasjonen hvordan tiden for å utføre algoritmen vokser med størrelsen på inngangen.

Nyttige oppskrivninger er tilgjengelige for å lære mer om Big-O-notasjonsteori eller praktiske Java-eksempler.

3. Liste

La oss starte med en enkel liste - som er en bestilt samling.

Her vil vi ta en titt på ytelsesoversikt over ArrayList, LinkedList, og CopyOnWriteArrayList implementeringer.

3.1. ArrayList

De ArrayList i Java støttes av en matrise. Dette bidrar til å forstå den interne logikken i implementeringen. En mer omfattende guide for ArrayList er tilgjengelig i denne artikkelen.

Så la oss først fokusere på tidskompleksiteten til de vanlige operasjonene, på et høyt nivå:

• legge til() - tar O (1) tid
• legg til (indeks, element) - i gjennomsnitt løper inn På) tid
• få() - er alltid en konstant tid O (1) operasjon
• fjerne() - kjører lineært På) tid. Vi må gjenta hele matrisen for å finne elementet som er kvalifisert for fjerning
• oversikt over()- kjører også på lineær tid. Den går gjennom den interne matrisen og sjekker hvert element en etter en. Så tidskompleksiteten for denne operasjonen krever alltid På) tid
• inneholder () - implementering er basert på oversikt over(). Så det vil også løpe inn På) tid

3.2. CopyOnWriteArrayList

Denne implementeringen av Liste grensesnitt er veldig nyttig når du arbeider med applikasjoner med flere tråder. Det er trådsikkert og forklart godt i denne guiden her.

Her er forestillingen Big-O notasjonsoversikt for CopyOnWriteArrayList:

• legge til() - avhenger av posisjonen vi tilfører verdi, så kompleksiteten er På)
• få() - er O (1) konstant tidsdrift
• fjerne() - tar På) tid
• inneholder () - på samme måte er kompleksiteten På)

Som vi kan se, er det veldig dyrt å bruke denne samlingen på grunn av ytelsesegenskapene til legge til() metode.

3.3. LinkedList

LinkedList er en lineær datastruktur som består av noder som holder et datafelt og en referanse til en annen node. For mer LinkedList funksjoner og evner, ta en titt på denne artikkelen her.

La oss presentere det gjennomsnittlige estimatet for tiden vi trenger for å utføre noen grunnleggende operasjoner:

• legge til() - støtter O (1) konstant innsetting i hvilken som helst posisjon
• få() - å søke etter et element tar På) tid
• fjerne() - å fjerne et element tar også O (1) betjening, ettersom vi gir elementets posisjon
• inneholder () - også har På) tidskompleksitet

3.4. Oppvarming av JVM

Nå, for å bevise teorien, la oss leke med faktiske data. For å være mer presis presenterer vi JMH (Java Microbenchmark Harness) testresultater for de vanligste innsamlingsoperasjonene.

Hvis du ikke er kjent med JMH-verktøyet, kan du sjekke ut denne nyttige veiledningen.

Først presenterer vi hovedparametrene for våre referansetester:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @Warmup (iterasjoner = 10) offentlig klasse ArrayListBenchmark {}

Så setter vi oppvarmingsnummeret til 10. Vi ønsker også å se den gjennomsnittlige kjøretiden for resultatene våre vises i mikrosekunder.

3.5. Referansetester

Nå er det på tide å kjøre ytelsestestene våre. Først begynner vi med ArrayList:

@State (Scope.Thread) offentlig statisk klasse MyState {List medarbeiderliste = ny ArrayList (); lange iterasjoner = 100000; Ansatt ansatt = ny ansatt (100L, "Harry"); int medarbeiderIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {employeeList.add (new Employee (i, "John")); } ansatteListe.add (ansatt); ansatteIndex = ansatteliste.indeksOf (ansatt); }}

Inne i vår ArrayListBenchmark, legger vi til Stat klasse for å holde de opprinnelige dataene.

Her lager vi en ArrayList av Ansatt gjenstander. Etter, vi initialiserer den med 100.000 gjenstander inne i setUp () metode. De @Stat indikerer at @Benchmark tester har full tilgang til variablene som er angitt i den innen samme tråd.

Endelig er det på tide å legge til referansetestene for legg til (), inneholder (), indexOf (), fjern (), og få() metoder:

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

3.6. Testresultater

Alle resultatene presenteres i mikrosekunder:

Referansemodus 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.testGet avgt 20 0.008 ± 100 624,856 ± 51,101

Fra resultatene kan vi lære, det testInneholder () og testIndexOf () metoder kjører omtrent samtidig. Vi kan også tydelig se den enorme forskjellen mellom testAdd (), testGet () metodepoeng fra resten av resultatene. Å legge til et element tar 2.296 mikrosekunder og å få en er 0,007 mikrosekund.

Det koster omtrent å søke eller fjerne et element 700 mikrosekunder. Disse tallene er beviset på den teoretiske delen, der vi lærte det legge til(), og få() har O (1) tidskompleksitet og de andre metodene er På). n = 10.000 elementer i vårt eksempel.

På samme måte kan vi skrive de samme testene for CopyOnWriteArrayList samling. Alt vi trenger er å erstatte ArrayList i medarbeiderliste med CopyOnWriteArrayList forekomst.

Her er resultatene av referansetesten:

Referanse Mode Cnt Score Feil 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

Også her bekrefter tallene teorien. Som vi kan se, testGet () i gjennomsnitt kjører i 0,006 ms som vi kan betrakte som O (1). Sammenlignet med ArrayList, merker vi også den betydelige forskjellen mellom testLegg til () metoderesultater. Som vi har her På) kompleksitet for legge til() metode kontra ArrayLists O (1).

Vi kan tydelig se den lineære veksten av tiden, slik ytelsestallene er 878.166 sammenlignet med 0.051.

Nå er det LinkedList tid:

Referanseverdi Cnt Score Feil test Legg til 20 2,580 ± 0,003 test Inneholder 20 1808,102 ± 68,155 test Få 20 1561,831 ± 70,876 test Fjern 20 0,006 ± 0,001

Vi kan se fra poengsummen at det å legge til og fjerne elementer i LinkedList er ganske raske.

Videre er det et betydelig ytelsesgap mellom å legge til / fjerne og få / inneholder operasjoner.

4. Kart

Med de nyeste JDK-versjonene er vi vitne til betydelig ytelsesforbedring for Kart implementeringer, for eksempel å erstatte LinkedList med den balanserte treknutestrukturen i HashMap, LinkedHashMap interne implementeringer. Dette forkorter elementoppslag i verste fall fra På) til O (logg (n)) tid i løpet av HashMap kollisjoner.

Imidlertid hvis vi implementerer riktig .er lik() og .hashcode () metoder kollisjoner er usannsynlig.

For å lære mer om HashMap kollisjoner sjekk ut denne oppskriften. Fra oppskriften kan vi også lære at lagring og henting av elementer fra HashMap tar konstant O (1) tid.

4.1. Testing O (1) Operasjoner

La oss vise noen faktiske tall. Først for HashMap:

Referansemodus Cnt Score Feil 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.testFjern av 20.2010 ± 0.001

Som vi ser, viser tallene O (1) konstant tid for å kjøre metodene som er oppført ovenfor. La oss nå sammenligne HashMap testresultater med den andre Kart forekomstpoeng.

For alle de listede metodene, vi har O (1) til HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap og ConcurrentHashMap.

La oss presentere resultatene av de gjenværende testresultatene i form av en tabell:

ReferanselinketHashMap-identitetHashMap SvakHashMap Samtidig

Fra utgangstallene kan vi bekrefte påstandene om O (1) tidskompleksitet.

4.2. Testing O (logg (n)) Operasjoner

For trestrukturen TreeMap og ConcurrentSkipListMap de put (), get (), remove (), inneholderKey () driftstid er O (logg (n)).

Her, Vi vil sørge for at ytelsestestene våre kjører omtrent på logaritmisk tid. Av den grunn initialiserer vi kartene med n=1000, 10,000, 100,000, 1,000,000 varer kontinuerlig.

I dette tilfellet er vi interessert i den totale tiden for utførelse:

antall artikler (n) 1000 10.000 100.000 1.000.000 alle tester total score 00:03:17 00:03:17 00:03:30 00:05:27 

Når n = 1000 vi har totalt 00:03:17 millisekunders utførelsestid. n = 10.000 tiden er nesten uendret 00:03:18 ms. n = 100.000 har mindre økning 00:03:30. Og til slutt, når n = 1.000.000 løpeturen fullføres i 00:05:27 ms.

Etter å ha sammenlignet kjøretidstallene med logg (n) funksjon av hver n, kan vi bekrefte at korrelasjonen til begge funksjonene stemmer overens.

5. Sett

Som regel, Sett er en samling av unike elementer. Her skal vi undersøke HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, og ConcurrentSkipListSet implementeringer av Sett grensesnitt.

For bedre å forstå det indre av HashSet, denne guiden er her for å hjelpe.

La oss nå gå frem for å presentere tidskompleksitetstallene. Til HashSet, LinkedHashSet, og EnumSet de Legg til fjern() og inneholder () drift koster konstant O (1) tid. Takket være det interne HashMap gjennomføring.

Likeledes, den TreeSet har O (logg (n)) tidskompleksitet for operasjonene som er oppført for forrige gruppe. Det er på grunn av TreeMap gjennomføring. Tidenes kompleksitet for ConcurrentSkipListSet er også O (logg (n)) tid, da den er basert på datastrukturen over skiplisten.

Til CopyOnWriteArraySet, de Legg til fjern() og inneholder () metoder har O (n) gjennomsnittlig tidskompleksitet.

5.1. Testmetoder

La oss nå gå til våre referansetester:

@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); }

Videre lar vi de gjenværende referansekonfigurasjonene være som de er.

5.2. Sammenligning av tallene

La oss se oppførselen til runtime kjøringsscore for HashSet og LinkedHashSet har n = 1000; 10.000; 100.000 gjenstander.

For HashSet, tallene er:

Referanseindeks 1000 10.000 100.000 .add () 0.026 0.023 0.024 .fjern () 0.009 0.009 0.009. Inneholder () 0.009 0.009 0.010

Tilsvarende er resultatene for LinkedHashSet er:

Referanseindeks 1000 10.000 100.000 .add () 0.022 0.026 0.027 .fjern () 0.008 0.012 0.009. Inneholder () 0.008 0.013 0.009

Som vi ser, er poengene nesten de samme for hver operasjon. Enda mer når vi sammenligner dem med HashMap testutganger, de ser også like ut.

Som et resultat bekrefter vi at alle de testede metodene kjører konstant O (1) tid.

6. Konklusjon

I denne artikkelen, vi presenterer tidskompleksiteten til de vanligste implementeringene av Java datastrukturer.

Separat viser vi den faktiske kjøretidsytelsen for hver type samling gjennom JVM-testene. Vi har også sammenlignet ytelsen til de samme operasjonene i forskjellige samlinger. Som et resultat lærer vi å velge riktig samling som passer våre behov.

Som vanlig er den komplette koden for denne artikkelen tilgjengelig på GitHub.