streamalism.org

1. Oversigt

I denne vejledning Vi taler om præstationen af ​​forskellige samlinger fra Java Collection API. Når vi taler om samlinger, tænker vi normalt på Liste, kort, og Sæt datastrukturer og deres fælles implementeringer.

Først og fremmest vil vi se på Big-O-kompleksitetsindsigt for almindelige operationer, og derefter viser vi det reelle antal af nogle indsamlingsoperationers driftstid.

2. Tidskompleksitet

Som regel, når vi taler om tidskompleksitet, henviser vi til Big-O notation. Kort sagt beskriver notationen, hvordan tiden til at udføre algoritmen vokser med størrelsen på input.

Nyttige opskrivninger er tilgængelige for at lære mere om Big-O-notationsteori eller praktiske Java-eksempler.

3. Liste

Lad os starte med en simpel liste - som er en ordnet samling.

Her vil vi se på et ydeevneoversigt over ArrayList, LinkedList, og CopyOnWriteArrayList implementeringer.

3.1. ArrayList

Det ArrayList i Java er bakket op af en matrix. Dette hjælper med at forstå den interne logik i dens implementering. En mere omfattende guide til ArrayList er tilgængelig i denne artikel.

Så lad os først fokusere på tidskompleksiteten af ​​de fælles operationer på et højt niveau:

• tilføje() - tager O (1) tid
• tilføj (indeks, element) - i gennemsnit løber ind På) tid
• få() - er altid en konstant tid O (1) operation
• fjerne() - kører lineært På) tid. Vi er nødt til at gentage hele arrayet for at finde det element, der kvalificerer sig til fjernelse
• indeks af()- kører også i lineær tid. Det gentager sig gennem det interne array og kontrollerer hvert element en efter en. Så tidskompleksiteten for denne operation kræver altid På) tid
• indeholder() - implementering er baseret på indeks af(). Så det løber også ind På) tid

3.2. CopyOnWriteArrayList

Denne gennemførelse af Liste interface er meget nyttigt, når du arbejder med applikationer med flere tråde. Det er trådsikkert og forklares godt i denne vejledning her.

Her er forestillingen Big-O notationsoversigt til CopyOnWriteArrayList:

• tilføje() - afhænger af den position, vi tilføjer værdi, så kompleksiteten er På)
• få() - er O (1) konstant tidsdrift
• fjerne() - tager På) tid
• indeholder() - ligeledes er kompleksiteten På)

Som vi kan se, er det meget dyrt at bruge denne samling på grund af ydeevneegenskaberne for tilføje() metode.

3.3. LinkedList

LinkedList er en lineær datastruktur, der består af noder, der indeholder et datafelt og en henvisning til en anden node. For mere LinkedList funktioner og funktioner, se denne artikel her.

Lad os præsentere det gennemsnitlige skøn over den tid, vi har brug for til at udføre nogle grundlæggende operationer:

• tilføje() - bakker op O (1) konstant tidsindsættelse i enhver position
• få() - at søge efter et element tager På) tid
• fjerne() - fjernelse af et element tager også O (1) betjening, da vi giver elementets position
• indeholder() - har også På) tidskompleksitet

3.4. Opvarmning af JVM

Lad os lege med faktiske data for at bevise teorien. For at være mere præcis præsenterer vi JMH (Java Microbenchmark Harness) testresultater for de mest almindelige indsamlingshandlinger.

Hvis du ikke er bekendt med JMH-værktøjet, skal du tjekke denne nyttige guide.

For det første præsenterer vi de vigtigste parametre i vores benchmarktest:

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

Derefter indstiller vi opvarmningsnummeret til 10. Vi ønsker også at se den gennemsnitlige driftstid for vores resultater vist i mikrosekunder.

3.5. Benchmark-tests

Nu er det tid til at køre vores præstationstest. Først starter vi med ArrayList:

@State (Scope.Thread) offentlig statisk klasse MyState {List medarbejderliste = ny ArrayList (); lange iterationer = 100000; Medarbejdermedarbejder = ny medarbejder (100L, "Harry"); int medarbejderIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {medarbejderList.add (ny medarbejder (i, "John")); } medarbejderliste.add (medarbejder); medarbejderIndex = medarbejderListe.indexOf (medarbejder); }}

Inde i vores ArrayListBenchmark, vi tilføjer Stat klasse til at indeholde de oprindelige data.

Her opretter vi en ArrayList af Medarbejder genstande. Efter, vi initialiserer det med 100.000 genstande inde i Opsætning() metode. Det @Stat angiver, at @Benchmark test har fuld adgang til de variabler, der er angivet i den inden for samme tråd.

Endelig er det tid til at tilføje benchmarktest til tilføj (), indeholder (), indexOf (), fjern (), og få() metoder:

@Benchmark public void testAdd (ArrayListBenchmark.MyState state) {state.employeeList.add (ny medarbejder (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. Test resultater

Alle resultater præsenteres i mikrosekunder:

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

Fra de resultater, vi kan lære, det testContains () og testIndexOf () metoder kører omtrent på samme tid. Vi kan også tydeligt se den enorme forskel mellem testAdd (), testGet () metode scorer fra resten af ​​resultaterne. Tilføjelse af et element tager 2.296 mikrosekunder og at få en er 0,007 mikrosekund.

Mens du søger eller fjerner et element, koster det groft 700 mikrosekunder. Disse tal er beviset for den teoretiske del, hvor vi lærte det tilføje(), og få() har O (1) tidskompleksitet og de andre metoder er På). n = 10.000 elementer i vores eksempel.

På samme måde kan vi skrive de samme tests til CopyOnWriteArrayList kollektion. Alt, hvad vi har brug for, er at erstatte ArrayList i medarbejderliste med CopyOnWriteArrayList eksempel.

Her er resultaterne af benchmark-testen:

Benchmark tilstand Cnt Score Fejl 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

Her bekræfter tallene igen teorien. Som vi kan se, testGet () kører i gennemsnit 0,006 ms, hvilket vi kan betragte som O (1). Sammenligner med ArrayList, bemærker vi også den markante forskel mellem testTilføj () metode resultater. Som vi har her På) kompleksitet for tilføje() metode versus ArrayLists O (1).

Vi kan tydeligt se den lineære vækst af tiden, som præstationstal er 878.166 sammenlignet med 0.051.

Nu er det LinkedList tid:

Benchmark Cnt Score Fejltest Tilføj 20 2.580 ± 0,003 test Indeholder 20 1808,102 ± 68,155 test Få 20 1561,831 ± 70,876 test Fjern 20 0,006 ± 0,001

Vi kan se fra scores, at tilføjelse og fjernelse af elementer i LinkedList er ret hurtige.

Derudover er der en betydelig præstationsforskel mellem tilføj / fjern og få / indeholder operationer.

4. Kort

Med de nyeste JDK-versioner er vi vidne til en betydelig forbedring af ydeevnen for Kort implementeringer, såsom udskiftning af LinkedList med den afbalancerede træknudestruktur i HashMap, LinkedHashMap interne implementeringer. Dette forkorter elementopslag i værste tilfælde fra På) til O (log (n)) tid i løbet af HashMap kollisioner.

Men hvis vi implementerer korrekt .lige med() og .hashcode () metoder kollisioner er usandsynlige.

For at lære mere om HashMap kollisioner tjek denne opskrivning. Fra opskrivningen kan vi også lære, at lagring og hentning af elementer fra HashMap tager konstant O (1) tid.

4.1. Testning O (1) Operationer

Lad os vise nogle faktiske tal. For det første til HashMap:

Benchmark Mode Cnt Score Error 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 avgt 20 0.010 ± 0.001

Som vi ser, viser tallene, at O (1) konstant tid til at køre ovennævnte metoder. Lad os nu sammenligne HashMap testresultater med den anden Kort eksempel score.

For alle de anførte metoder, vi har O (1) til HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap og ConcurrentHashMap.

Lad os præsentere resultaterne af de resterende testresultater i form af en tabel:

Benchmark LinkedHashMap IdentityHashMap SvagHashMap SamtidigHashMap test IndeholderTast 0,008 0,009 0,014 0,011 testFå 0,011 0,109 0,019 0,012 testSæt 0,020 0,013 0,020 0,031 testFjern 0,011 0,115 0,021 0,019

Fra outputnumrene kan vi bekræfte påstandene om O (1) tidskompleksitet.

4.2. Testning O (log (n)) Operationer

Til træstrukturen TreeMap og ConcurrentSkipListMap det put (), get (), remove (), containKey () driftstiden er O (log (n)).

Her, Vi vil sikre os, at vores præstationstest kører omtrent på logaritmisk tid. Af den grund initialiserer vi kortene med n=1000, 10,000, 100,000, 1,000,000 varer kontinuerligt.

I dette tilfælde er vi interesseret i den samlede tid for udførelse:

antal varer (n) 1000 10.000 100.000 1.000.000 alle tests samlede score 00:03:17 00:03:17 00:03:30 00:05:27 

Hvornår n = 1000 vi har det samlede antal 00:03:17 udførelsestid for millisekunder. n = 10.000 tiden er næsten uændret 00:03:18 ms. n = 100.000 har mindre stigning 00:03:30. Og endelig, hvornår n = 1.000.000 løbet løber i 00:05:27 ms.

Efter at have sammenlignet runtime-numrene med log (n) funktion af hver n, kan vi bekræfte, at sammenhængen mellem begge funktioner stemmer overens.

5. Sæt

Generelt, Sæt er en samling af unikke elementer. Her skal vi undersøge HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, og ConcurrentSkipListSet implementeringer af Sæt interface.

For bedre at forstå det indre af HashSet, denne guide er her for at hjælpe.

Lad os nu springe frem for at præsentere tidskompleksitetstallene. Til HashSet, LinkedHashSet, og EnumSet det tilføj (), fjern () og indeholder() drift koster konstant O (1) tid. Takket være det interne HashMap implementering.

Ligeledes TreeSet har O (log (n)) tidskompleksitet for de operationer, der er angivet for den foregående gruppe. Det er på grund af TreeMap implementering. Tidenes kompleksitet for ConcurrentSkipListSet er også O (log (n)) tid, da den er baseret på skipstistdatastruktur.

Til CopyOnWriteArraySet, det tilføj (), fjern () og indeholder() metoder har O (n) gennemsnitlig tidskompleksitet.

5.1. Testmetoder

Lad os nu springe til vores benchmark-tests:

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

Desuden forlader vi de resterende benchmark-konfigurationer, som de er.

5.2. Sammenligning af numrene

Lad os se opførelsen af ​​runtime-eksekveringsscore for HashSet og LinkedHashSet at have n = 1000; 10.000; 100.000 genstande.

Til HashSet, tallene er:

Benchmark 1000 10.000 100.000. Tilføj () 0,026 0,023 0,024. Fjern () 0,009 0,009 0,009. Indeholder () 0,009 0,009 0,010

Tilsvarende er resultaterne for LinkedHashSet er:

Benchmark 1000 10.000 100.000. Tilføj () 0,022 0,026 0,027. Fjern () 0,008 0,012 0,009. Indeholder () 0,008 0,013 0,009

Som vi ser, forbliver scorerne næsten de samme for hver operation. Endnu mere, når vi sammenligner dem med HashMap test output ser de også ud.

Som et resultat bekræfter vi, at alle de testede metoder kører konstant O (1) tid.

6. Konklusion

I denne artikel vi præsenterer tidskompleksiteten af ​​de mest almindelige implementeringer af Java-datastrukturer.

Separat viser vi den faktiske runtime-ydeevne for hver type samling gennem JVM-benchmarktestene. Vi har også sammenlignet udførelsen af ​​de samme operationer i forskellige samlinger. Som et resultat lærer vi at vælge den rigtige samling, der passer til vores behov.

Som sædvanlig er den komplette kode til denne artikel tilgængelig på GitHub.