Tijdscomplexiteit van Java-verzamelingen

1. Overzicht

In deze tutorial we zullen het hebben over de prestaties van verschillende collecties van de Java Collection API. Als we het over collecties hebben, denken we meestal aan de Lijst, kaart, en Set datastructuren en hun gemeenschappelijke implementaties.

Allereerst kijken we naar Big-O-complexiteitsinzichten voor veelvoorkomende bewerkingen, en daarna laten we de werkelijke cijfers zien van de looptijd van sommige verzamelingsbewerkingen.

2. Tijdscomplexiteit

Meestal als we het hebben over tijdcomplexiteit, verwijzen we naar de Big-O-notatie. Simpel gezegd, de notatie beschrijft hoe de tijd om het algoritme uit te voeren toeneemt met de grootte van de invoer.

Er zijn nuttige artikelen beschikbaar om meer te weten te komen over de Big-O-notatietheorie of praktische Java-voorbeelden.

3. Lijst

Laten we beginnen met een eenvoudige lijst: een geordende verzameling.

Hier bekijken we een prestatieoverzicht van de ArrayList, LinkedList, en CopyOnWriteArrayList implementaties.

3.1. ArrayList

De ArrayList in Java wordt ondersteund door een array. Dit helpt om de interne logica van de implementatie ervan te begrijpen. Een meer uitgebreide gids voor de ArrayList is beschikbaar in dit artikel.

Laten we ons dus eerst concentreren op de tijdcomplexiteit van de gebruikelijke bewerkingen, op een hoog niveau:

  • toevoegen() - neemt O (1) tijd
  • add (index, element) - gemiddeld binnenkomt Aan) tijd
  • krijgen() - is altijd een constante tijd O (1) operatie
  • verwijderen() - loopt lineair Aan) tijd. We moeten de hele array herhalen om het element te vinden dat in aanmerking komt voor verwijdering
  • index van()- loopt ook in lineaire tijd. Het doorloopt de interne array en controleert elk element een voor een. Dus de tijdcomplexiteit voor deze operatie vereist altijd Aan) tijd
  • bevat () - implementatie is gebaseerd op index van(). Het loopt dus ook naar binnen Aan) tijd

3.2. CopyOnWriteArrayList

Deze implementatie van de Lijst interface is erg handig bij het werken met multi-threaded applicaties. Het is thread-safe en goed uitgelegd in deze gids hier.

Hier is het prestatie-Big-O-notatieoverzicht voor CopyOnWriteArrayList:

  • toevoegen() - hangt af van de functie waar we waarde aan toevoegen, dus de complexiteit is Aan)
  • krijgen() - is O (1) constante tijd werking
  • verwijderen() - neemt Aan) tijd
  • bevat () - evenzo is de complexiteit Aan)

Zoals we kunnen zien, is het gebruik van deze collectie erg duur vanwege de prestatiekenmerken van de toevoegen() methode.

3.3. LinkedList

LinkedList is een lineaire gegevensstructuur die bestaat uit knooppunten die een gegevensveld bevatten en een verwijzing naar een ander knooppunt. Voor meer LinkedList functies en mogelijkheden, bekijk dit artikel hier.

Laten we de gemiddelde schatting geven van de tijd die we nodig hebben om enkele basisbewerkingen uit te voeren:

  • toevoegen() - ondersteunt O (1) constante tijd inbrengen op elke positie
  • krijgen() - zoeken naar een element takes Aan) tijd
  • verwijderen() - het verwijderen van een element neemt ook O (1) werking, aangezien we de positie van het element aangeven
  • bevat () - heeft ook Aan) tijd complexiteit

3.4. De JVM opwarmen

Laten we, om de theorie te bewijzen, spelen met feitelijke gegevens. Om preciezer te zijn, presenteren we de JMH-testresultaten (Java Microbenchmark Harness) van de meest voorkomende verzamelbewerkingen.

Als u niet bekend bent met de JMH-tool, bekijk dan deze handige gids.

Eerst presenteren we de belangrijkste parameters van onze benchmarktests:

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

Vervolgens stellen we het aantal opwarmings-iteraties in op 10. We willen ook dat de gemiddelde looptijd van onze resultaten wordt weergegeven in microseconden.

3.5. Benchmark-tests

Nu is het tijd om onze prestatietests uit te voeren. Eerst beginnen we met de ArrayList:

@State (Scope.Thread) openbare statische klasse MyState {List employeeList = new ArrayList (); lange iteraties = 100000; Werknemer werknemer = nieuwe werknemer (100L, "Harry"); int employeeIndex = -1; @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {employeeList.add (nieuwe medewerker (i, "John")); } employeeList.add (medewerker); employeeIndex = employeeList.indexOf (medewerker); }}

Binnenkant van ons ArrayListBenchmarkvoegen we de Staat klasse om de initiële gegevens vast te houden.

Hier maken we een ArrayList van Werknemer voorwerpen. Na, we initialiseren het met 100.000 items in de opstelling() methode. De @Staat geeft aan dat de @Benchmark tests hebben volledige toegang tot de variabelen die erin zijn gedeclareerd binnen dezelfde thread.

Eindelijk is het tijd om de benchmarktests toe te voegen voor de add (), bevat (), indexOf (), remove (), en krijgen() methoden:

@Benchmark public void testAdd (ArrayListBenchmark.MyState state) {state.employeeList.add (nieuwe werknemer (state.iterations + 1, "John")); } @Benchmark public void testAddAt (ArrayListBenchmark.MyState state) {state.employeeList.add ((int) (state.iterations), nieuwe werknemer (state.iterations, "John")); } @Benchmark openbare booleaanse testContains (ArrayListBenchmark.MyState state) {return state.employeeList.contains (state.employee); } @Benchmark openbare int testIndexOf (ArrayListBenchmark.MyState staat) {terugkeer state.employeeList.indexOf (state.employee); } @Benchmark openbare Werknemer testGet (ArrayListBenchmark.MyState staat) {terugkeer state.employeeList.get (state.employeeIndex); } @Benchmark openbare boolean testRemove (ArrayListBenchmark.MyState state) {terugkeer state.employeeList.remove (state.employee); }

3.6. Test resultaten

Alle resultaten worden in microseconden gepresenteerd:

Benchmark-modus Cnt Score Fout ArrayListBenchmark.testAdd gemiddelde 20 2.296 ± 0.007 ArrayListBenchmark.testAddAt gemiddelde 20 101.092 ± 14.145 ArrayListBenchmark.testContains gemiddelde 20709.404 ± 64.331 ArrayListBenchmark.testGet 20 gemiddelde waarde-index. 624.856 ± 51.101

Van de resultaten kunnen we leren dat testContains () en testIndexOf () methoden worden in ongeveer dezelfde tijd uitgevoerd. We kunnen ook duidelijk het enorme verschil zien tussen de testAdd (), testGet () methode scores van de rest van de resultaten. Het toevoegen van een element duurt 2.296 microseconden en het verkrijgen ervan is een operatie van 0,007 microseconde.

Bij het zoeken of verwijderen van een element kost het grofweg 700 microseconden. Deze cijfers zijn het bewijs van het theoretische gedeelte, waarin we dat hebben geleerd toevoegen(), en krijgen() heeft O (1) tijdcomplexiteit en de andere methoden zijn Aan). n = 10.000 elementen in ons voorbeeld.

Evenzo kunnen we dezelfde tests schrijven voor CopyOnWriteArrayList verzameling. Het enige dat we nodig hebben, is het vervangen van het ArrayList in employeeList met de CopyOnWriteArrayList voorbeeld.

Hier zijn de resultaten van de benchmarktest:

Benchmarkmodus Cnt Score Fout CopyOnWriteBenchmark.testAdd gemiddelde 20652.189 ± 36.641 CopyOnWriteBenchmark.testAddAt gemiddelde 20897.258 ± 35.363 CopyOnWriteBenchmark.testContains gemiddelde 20 537.098 ± 54.235 CopyOnWrite ± 36.641Gemiddelde waarde 0.007xBenchmark. 648.162 ± 138.379

Ook hier bevestigen de cijfers de theorie. Zoals we kunnen zien, testGet () loopt gemiddeld in 0,006 ms, wat we kunnen beschouwen als O (1). Vergelijken met ArrayListmerken we ook het significante verschil tussen testAdd () methode resultaten. Zoals we hier hebben Aan) complexiteit voor de toevoegen() methode versus ArrayList's O (1).

We kunnen duidelijk de lineaire groei van de tijd zien, net als de prestatieaantallen 878.166 in vergelijking tot 0.051.

Nu is het LinkedList tijd:

Benchmark Cnt Score Fout test Toevoegen 20 2.580 ± 0.003 test Bevat 20 1808.102 ± 68.155 test Get 20 1561.831 ± 70.876 test Verwijderen 20 0.006 ± 0.001

We kunnen aan de scores zien dat het toevoegen en verwijderen van elementen in LinkedList zijn vrij snel.

Bovendien is er een aanzienlijke prestatiekloof tussen bewerkingen toevoegen / verwijderen en ophalen / bevat.

4. Kaart

Met de nieuwste JDK-versies zijn we getuige van een aanzienlijke prestatieverbetering voor Kaart implementaties, zoals het vervangen van de LinkedList met de gebalanceerde boomknooppuntstructuur in HashMap, LinkedHashMap interne implementaties. Dit verkort het worstcasescenario voor het opzoeken van elementen van Aan) naar O (logboek (n)) tijd tijdens de Hash kaart botsingen.

Als we echter correct implementeren .equals () en .hashcode () methoden botsingen zijn onwaarschijnlijk.

Om meer te weten te komen over Hash kaart botsingen bekijk dit artikel. Uit het artikel kunnen we ook leren dat het opslaan en ophalen van elementen uit de Hash kaart neemt constant O (1) tijd.

4.1. Testen O (1) Operaties

Laten we enkele echte cijfers laten zien. Ten eerste voor de Hash kaart:

Benchmarkmodus Cnt Score Fout HashMapBenchmark.testContainsKey gemiddelde 20 0,009 ± 0,002 HashMapBenchmark.testGet gemiddelde 20 0,011 ± 0,001 HashMapBenchmark.testPut gemiddelde 20 0,019 ± 0,002 HashMapBenchmark.test Verwijder gemiddelde 20 0,010 ± 0,001

Zoals we zien, bewijzen de cijfers de O (1) constante tijd voor het uitvoeren van de hierboven genoemde methoden. Laten we nu een vergelijking maken van de Hash kaart test scores met de andere Kaart instantie scores.

Voor alle vermelde methoden, we hebben O (1) voor HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap en ConcurrentHashMap.

Laten we de resultaten van de resterende testscores presenteren in de vorm van één tabel:

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 testVerwijder 0.011 0.115 0.021 0.019

Aan de hand van de outputnummers kunnen we de beweringen van O (1) tijd complexiteit.

4.2. Testen O (logboek (n)) Operaties

Voor de boomstructuur TreeMap en ConcurrentSkipListMap de put (), get (), remove (), containsKey () operatietijd is O (log (n)).

Hier, we willen ervoor zorgen dat onze prestatietests ongeveer in logaritmische tijd worden uitgevoerd. Om die reden initialiseren we de kaarten met n=1000, 10,000, 100,000, 1,000,000 items continu.

In dit geval zijn we geïnteresseerd in de totale uitvoeringstijd:

aantal items (n) 1000 10.000 100.000 1.000.000 alle tests totaalscore 00:03:17 00:03:17 00:03:30 00:05:27 

Wanneer n = 1000 we hebben het totaal van 00:03:17 milliseconden uitvoeringstijd. n = 10.000 de tijd is nagenoeg ongewijzigd 00:03:18 ms. n = 100.000 heeft een kleine stijging 00:03:30. En tot slot, wanneer n = 1.000.000 de run is voltooid in 00:05:27 ms.

Na het vergelijken van de looptijdnummers met de logboek (n) functie van elk nkunnen we bevestigen dat de correlatie van beide functies overeenkomt.

5. Set

Over het algemeen, Set is een verzameling unieke elementen. Hier gaan we het HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, en ConcurrentSkipListSet implementaties van de Set koppel.

Om de binnenkant van het HashSet, deze gids is hier om u te helpen.

Laten we nu vooruit springen om de getallen van de tijdcomplexiteit te presenteren. Voor HashSet, LinkedHashSet, en EnumSet de toevoegen verwijderen() en bevat () operationele kosten constant O (1) tijd. Dankzij de interne Hash kaart implementatie.

Evenzo is het TreeSet heeft O (logboek (n)) tijd complexiteit voor de bewerkingen die zijn vermeld voor de vorige groep. Dat komt door de TreeMap implementatie. De tijdcomplexiteit voor ConcurrentSkipListSet is ook O (logboek (n)) tijd, omdat het is gebaseerd op de datastructuur van de lijst met overslaan.

Voor CopyOnWriteArraySet, de toevoegen verwijderen() en bevat () methoden hebben een O (n) gemiddelde tijdcomplexiteit.

5.1. Testmethoden

Laten we nu naar onze benchmarktests springen:

@Benchmark openbare boolean testAdd (staat SetBenchMark.MyState) {terugkeer staat.werknemerSet.add (staat.werknemer); } @Benchmark openbare Boolean testContains (SetBenchMark.MyState staat) {terugkeer state.employeeSet.contains (state.employee); } @Benchmark openbare boolean testRemove (SetBenchMark.MyState staat) {terugkeer state.employeeSet.remove (state.employee); }

Bovendien laten we de resterende benchmarkconfiguraties zoals ze zijn.

5.2. De cijfers vergelijken

Laten we eens kijken naar het gedrag van de uitvoeringsscore voor HashSet en LinkedHashSet hebben n = 1000; 10.000; 100.000 items.

Voor de HashSet, de nummers zijn:

Benchmark 1000 10.000 100.000 .add () 0,026 0,023 0,024 .remove () 0,009 0,009 0,009. Bevat () 0,009 0,009 0,010

Evenzo zijn de resultaten voor LinkedHashSet zijn:

Benchmark 1000 10.000 100.000 .add () 0,022 0,026 0,027 .remove () 0,008 0,012 0,009. Bevat () 0,008 0,013 0,009

Zoals we zien, blijven de scores voor elke operatie nagenoeg hetzelfde. Sterker nog, als we ze vergelijken met de Hash kaart testoutputs zien ze er ook hetzelfde uit.

Als resultaat bevestigen we dat alle geteste methoden constant werken O (1) tijd.

6. Conclusie

In dit artikel, we presenteren de tijdcomplexiteit van de meest voorkomende implementaties van de Java-datastructuren.

Afzonderlijk laten we de werkelijke runtime-prestaties van elk type verzameling zien via de JVM-benchmarktests. We hebben ook de prestaties van dezelfde bewerkingen in verschillende collecties vergeleken. Hierdoor leren we de juiste collectie te kiezen die past bij onze wensen.

Zoals gewoonlijk is de volledige code voor dit artikel beschikbaar op GitHub.