Az removeAll () teljesítménye egy HashSet-ben

1. Áttekintés

HashSet gyűjtemény egyedi elemek tárolására.

Ebben az oktatóanyagban a összes eltávolítása() módszer a java.util.HashSet osztály.

2. HashSet.removeAll ()

A összes eltávolítása metódus eltávolítja az összes elemet, amely a Gyűjtemény:

Set set = new HashSet (); set.add (1); set.add (2); set.add (3); set.add (4); Gyűjtemény gyűjtemény = new ArrayList (); gyűjtemény.add (1); gyűjtemény.add (3); set.removeAll (gyűjtemény); Egész szám [] aktuális Elemek = új Egész szám [halmaz.méret ()]; Egész szám [] vártElementek = új egész szám [] {2, 4}; assertArrayEquals (vártElementek, set.toArray (ténylegesElementek)); 

Ennek eredményeként az 1. és a 3. elem eltávolításra kerül a készletből.

3. Belső megvalósítás és időbeli komplexitás

Az removeAll () módszer meghatározza, hogy melyik kisebb - a halmaz vagy a gyűjtemény. Ez a méret() módszer a készleten és a gyűjteményen.

Ha a gyűjtemény kevesebb elemet tartalmaz, mint a halmaz, majd az O (n). Azt is ellenőrzi, hogy az elem jelen van-e a halmazban az O (1) idő komplexitással. És ha az elem jelen van, akkor az a segítségével eltávolításra kerül a készletből eltávolítás () a halmaz metódusa, amelynek időbeli összetettsége ismét O (1). Így az idő bonyolultsága O (n).

Ha a halmaz kevesebb elemet tartalmaz, mint a gyűjtemény, akkor az O (n). Ezután annak meghívásával ellenőrzi, hogy minden elem szerepel-e a gyűjteményben tartalmaz () módszer. És ha van ilyen elem, akkor az elemet eltávolítják a halmazból. Tehát ez függ a tartalmaz () módszer.

Most ebben az esetben, ha a gyűjtemény egy Tömb lista, az idő bonyolultsága tartalmaz () módszer O (m). Így - az idő összetettsége a Tömb lista a halmazból O (n * m).

Ha a gyűjtemény ismét HashSet, az idő bonyolultsága tartalmaz () módszer O (1). Így - az idő összetettsége a HashSet a halmazból O (n).

4. Teljesítmény

A fenti 3 eset közötti teljesítménykülönbség megtekintéséhez írjunk egy egyszerű JMH benchmark tesztet.

Az első esetben inicializáljuk a halmazt és a gyűjteményt, ahol több elem van a halmazban, mint a gyűjtemény. A második esetben inicializáljuk a halmazt és a gyűjteményt, ahol több elem van a gyűjteményben, mint a halmaz. A harmadik esetben inicializálunk 2 halmazt, ahol lesz egy második halmazunk, amelynek több eleme van, mint az elsőnek:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterációk = 5) public class HashSetBenchmark {@State (Scope.Thread) public static class MyState {private Set workerSet1 = new HashSet (); private List workerList1 = new ArrayList (); private Set workerSet2 = új HashSet (); private List workerList2 = new ArrayList (); private Set workerSet3 = új HashSet (); private Set workerSet4 = új HashSet (); privát hosszú set1Size = 60000; private long list1Size = 50000; privát hosszú set2Size = 50000; private long list2Size = 60000; privát hosszú set3Size = 50000; privát hosszú set4Size = 60000; @Setup (Level.Trial) public void setUp () {// halmazok feltöltése}}}

Ezután hozzáadjuk a benchmark tesztjeinket:

@Benchmark public boolean megadott_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance (MyState state) {return state.employeeSet1.removeAll (state.employeeList1); } @Benchmark public boolean megadott_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); }

És itt vannak az eredmények:

Benchmark Mode Cnt Score Error egységek HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns / op HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 ns / op HashSetBenchmark.testHashSetSmallerThanOtherHashset avgt 20 2672757.784 ± 224505.866 ns / op

Láthatjuk a HashSet.removeAll () elég rosszul teljesít, ha a HashSet kevesebb elem van, mint az Gyűjtemény, amelyet érvként adunk át a összes eltávolítása() módszer. De amikor a másik gyűjtemény újra HashSet, akkor a teljesítmény jó.

5. Következtetés

Ebben a cikkben a összes eltávolítása() a HashSet-ben. Ha a halmaz kevesebb elemet tartalmaz, mint a gyűjtemény, akkor a összes eltávolítása() függ az idő bonyolultságától tartalmaz () a gyűjtés módszere.

Szokás szerint a cikk teljes kódja elérhető a GitHubon.