streamalism.org

1. Oversikt

HashSet er en samling for lagring av unike elementer.

I denne opplæringen vil vi diskutere ytelsen til Fjern alle() metoden i java.util.HashSet klasse.

2. HashSet.removeAll ()

De Fjern alle metoden fjerner alle elementene som finnes i samling:

Sett sett = nytt HashSet (); set.add (1); set.add (2); set.add (3); set.add (4); Samlingssamling = ny ArrayList (); collection.add (1); collection.add (3); set.removeAll (samling); Heltall [] actualElements = nytt Heltall [set.size ()]; Heltall [] expectElements = nytt Heltall [] {2, 4}; assertArrayEquals (expectedElements, set.toArray (actualElements)); 

Som et resultat blir elementene 1 og 3 fjernet fra settet.

3. Intern implementering og tidskompleksitet

The removeAll () metoden bestemmer hvilken som er mindre - settet eller samlingen. Dette gjøres ved å påkalle størrelse() metode på settet og samlingen.

Hvis samlingen har færre elementer enn settet, så går det over den spesifiserte samlingen med tidskompleksiteten O (n). Den sjekker også om elementet er tilstede i settet med tidskompleksiteten O (1). Og hvis elementet er til stede, fjernes det fra settet ved hjelp av fjerne() metoden til settet, som igjen har en tidskompleksitet på O (1). Så den totale tidskompleksiteten er O (n).

Hvis settet har færre elementer enn samlingen, så går det over dette settet ved hjelp av O (n). Deretter sjekker den om hvert element er tilstede i samlingen ved å påkalle det inneholder () metode. Og hvis et slikt element er til stede, blir elementet fjernet fra settet. Så dette avhenger av tidskompleksiteten til inneholder () metode.

Nå i dette tilfellet, hvis samlingen er en ArrayList, tidskompleksiteten til inneholder () metoden er O (m). Så total tidskompleksitet for å fjerne alle elementene som er tilstede i ArrayList fra settet er O (n * m).

Hvis samlingen er igjen HashSet, tidskompleksiteten til inneholder () metoden er O (1). Så total tidskompleksitet for å fjerne alle elementene som er tilstede i HashSet fra settet er O (n).

4. Ytelse

For å se ytelsesforskjellen mellom de tre tilfellene ovenfor, la oss skrive en enkel JMH-referansetest.

For det første vil vi initialisere settet og samlingen, der vi har flere elementer i settet enn samlingen. I det andre tilfellet initialiserer vi settet og samlingen, hvor vi har flere elementer i samlingen enn settet. Og i det tredje tilfellet initialiserer vi to sett, hvor vi har andre sett med flere antall elementer enn det første:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterasjoner = 5) offentlig klasse HashSetBenchmark {@State (Scope.Thread) offentlig statisk klasse MyState {privat Sett medarbeiderSet1 = ny HashSet (); private List ansatteList1 = ny ArrayList (); private Set ansatteSet2 = nye HashSet (); private List ansatteList2 = ny ArrayList (); private Set ansatteSet3 = nye HashSet (); private Set ansatteSet4 = nye HashSet (); privat lang sett1Size = 60000; privat lang liste1Size = 50000; privat lang set2Size = 50000; privat lang liste2Size = 60000; privat lang sett3Size = 50000; privat lang set4Size = 60000; @Setup (Level.Trial) public void setUp () {// populating sets}}}

Etterpå legger vi til våre referansetester:

@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 resultatene:

Referansemodus Cnt Score feilenheter HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns / op HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 nash / nash

Vi kan se HashSet.removeAll () utfører ganske dårlig når HashSet har færre elementer enn Samling, som sendes som et argument til Fjern alle() metode. Men når den andre samlingen er igjen HashSet, så er ytelsen god.

5. Konklusjon

I denne artikkelen så vi ytelsen til Fjern alle() i HashSet. Når settet har færre elementer enn samlingen, blir ytelsen til Fjern alle() avhenger av tidskompleksiteten til inneholder () metoden for samlingen.

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