streamalism.org

1. Oversigt

HashSet er en samling til opbevaring af unikke elementer.

I denne vejledning diskuterer vi ydeevnen af Fjern alt() metode i java.util.HashSet klasse.

2. HashSet.removeAll ()

Det Fjern alt metoden fjerner alle de elementer, der er indeholdt i kollektion:

Sæt sæt = nyt HashSet (); sæt. tilføj (1); sæt.tilsæt (2); sæt.add (3); sæt.tilsæt (4); Samlingssamling = ny ArrayList (); collection.add (1); collection.add (3); set.removeAll (samling); Heltal [] actualElements = nyt Heltal [set.size ()]; Heltal [] expectElements = nyt Heltal [] {2, 4}; assertArrayEquals (expectElements, set.toArray (actualElements)); 

Som et resultat fjernes element 1 og 3 fra sættet.

3. Intern implementering og tidskompleksitet

RemoveAll () metode bestemmer, hvilken der er mindre - sættet eller samlingen. Dette gøres ved at påberåbe sig størrelse() metode på sættet og samlingen.

Hvis samlingen har færre elementer end sættet, så gentager det sig over den specificerede samling med tidskompleksiteten O (n). Det kontrollerer også, om elementet er til stede i sættet med tidskompleksiteten O (1). Og hvis elementet er til stede, fjernes det fra sættet ved hjælp af fjerne() metode til sættet, som igen har en tidskompleksitet på O (1). Så den samlede tidskompleksitet er O (n).

Hvis sættet har færre elementer end samlingen, så gentages det over dette sæt ved hjælp af O (n). Derefter kontrolleres det, om hvert element er til stede i samlingen ved at påberåbe det indeholder() metode. Og hvis et sådant element er til stede, fjernes elementet fra sættet. Så dette afhænger af tidens kompleksitet indeholder() metode.

Nu i dette tilfælde, hvis samlingen er en ArrayList, tidens kompleksitet af indeholder() metode er O (m). Så samlet tidskompleksitet for at fjerne alle elementer, der er til stede i ArrayList fra sættet er O (n * m).

Hvis samlingen er igen HashSet, tidens kompleksitet af indeholder() metoden er O (1). Så den samlede tidskompleksitet for at fjerne alle elementer, der findes i HashSet fra sættet er O (n).

4. Ydeevne

For at se præstationsforskellen mellem de ovennævnte 3 tilfælde, lad os skrive en simpel JMH benchmark test.

I det første tilfælde initialiserer vi sættet og samlingen, hvor vi har flere elementer i sættet end samlingen. I det andet tilfælde initialiserer vi sættet og samlingen, hvor vi har flere elementer i samlingen end sættet. Og i det tredje tilfælde initialiserer vi 2 sæt, hvor vi har 2. sæt med flere antal elementer end det første:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterationer = 5) offentlig klasse HashSetBenchmark {@State (Scope.Thread) offentlig statisk klasse MyState {privat Set medarbejderSet1 = ny HashSet (); privat liste medarbejderliste1 = ny ArrayList (); privat sæt medarbejderSet2 = nyt HashSet (); privat liste medarbejderliste2 = ny ArrayList (); privat sæt medarbejderSet3 = nyt HashSet (); privat sæt medarbejderSet4 = nyt HashSet (); privat langt sæt1Size = 60000; privat lang liste1Size = 50000; privat langt set2Size = 50000; privat lang liste2Size = 60000; privat langt sæt3Size = 50000; privat lang set4Size = 60000; @Setup (Level.Trial) public void setUp () {// populating sets}}}

Derefter tilføjer vi vores benchmarktest:

@Benchmark public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance (MyState state) {return state.employeeSet1.removeAll (state.employeeList1); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance (MyState state) {return state.employeeSet2.removeAll (state.employeeList2); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance (MyState state) {return state.employeeSet3.removeAll (state.employeeSet4); }

Og her er resultaterne:

Benchmark Mode Cnt Score Fejlenheder HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns / op HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 ns. Hash

Vi kan se HashSet.removeAll () fungerer ret dårligt, når HashSet har færre elementer end Kollektion, der sendes som et argument til Fjern alt() metode. Men når den anden samling er igen HashSet, så er præstationen god.

5. Konklusion

I denne artikel så vi udførelsen af Fjern alt() i HashSet. Når sættet har færre elementer end samlingen, så er præstationen af Fjern alt() afhænger af tidens kompleksitet indeholder() metode til indsamling.

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