Výkon funkcie removeAll () v skupine HashSet

1. Prehľad

HashSet je kolekcia na ukladanie jedinečných prvkov.

V tomto výučbe sa budeme zaoberať výkonnosťou odobrať všetky() metóda v java.util.HashSet trieda.

2. HashSet.removeAll ()

The odobrať všetky metóda odstráni všetky prvky, ktoré sú obsiahnuté v zbierka:

Set set = new HashSet (); set.add (1); set.add (2); set.add (3); set.add (4); Zbierka zbierka = nový ArrayList (); zbierka.pridat (1); zbierka.pridat (3); set.removeAll (kolekcia); Celé číslo [] actualElements = nové celé číslo [set.size ()]; Celé číslo [] expectElements = nové celé číslo [] {2, 4}; assertArrayEquals (expectElements, set.toArray (actualElements)); 

Vo výsledku budú prvky 1 a 3 odstránené zo súpravy.

3. Interná implementácia a časová zložitosť

RemoveAll () metóda určuje, ktorý z nich je menší - sada alebo kolekcia. To sa deje vyvolaním súboru veľkosť () metóda na súbore a zbierka.

Ak má kolekcia menej prvkov ako množina, potom iteruje nad zadanou kolekciou s časovou zložitosťou O (n). Tiež kontroluje, či je prvok v množine s časovou zložitosťou O (1). A ak je prvok prítomný, bude odstránený z množiny pomocou znaku odstrániť () metóda množiny, ktorá má opäť časovú zložitosť O (1). Takže celková časová zložitosť je O (n).

Ak má súprava menej prvkov ako kolekcia, potom iteruje cez túto množinu pomocou O (n). Potom skontroluje, či je každý prvok v kolekcii, a to vyvolaním jeho obsahuje () metóda. A ak je taký prvok prítomný, potom sa prvok odstráni zo súpravy. To teda závisí od časovej zložitosti súboru obsahuje () metóda.

Teraz v tomto prípade, ak je zbierka ArrayList, časová zložitosť obsahuje () metóda je O (m). Takže celková časová zložitosť na odstránenie všetkých prvkov prítomných v ArrayList zo súpravy je O (n * m).

Ak je zbierka opäť HashSet, časová zložitosť obsahuje () metóda je O (1). Takže celková časová zložitosť na odstránenie všetkých prvkov prítomných v HashSet zo súpravy je O (n).

4. Výkon

Ak si chcete pozrieť výkonový rozdiel medzi vyššie uvedenými 3 prípadmi, napíšme jednoduchý test JMH.

V prvom prípade inicializujeme množinu a kolekciu, kde máme v množine viac prvkov ako kolekcie. V druhom prípade inicializujeme množinu a kolekciu, kde máme v kolekcii viac prvkov ako množiny. A v treťom prípade inicializujeme 2 sady, kde budeme mať 2. sadu s väčším počtom prvkov ako tá prvá:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) verejná trieda HashSetBenchmark {@State (Scope.Thread) verejná statická trieda MyState {súkromná sada employeeSet1 = nový HashSet (); private List employeeList1 = nový ArrayList (); private Set employeeSet2 = new HashSet (); private List employeeList2 = nový ArrayList (); private Set employeeSet3 = new HashSet (); private Set employeeSet4 = new HashSet (); súkromná dlhá sada1Veľkosť = 60000; súkromný dlhý zoznam1Veľkosť = 50 000; súkromná dlhá sada2Veľkosť = 50 000; súkromný dlhý zoznam2Veľkosť = 60000; súkromná dlhá sada3Veľkosť = 50 000; súkromná dlhá sada4Veľkosť = 60000; @Setup (Level.Trial) public void setUp () {// vyplnenie súborov}}}

Potom pridáme naše testovacie testy:

@Benchmark public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance (štát MyState) {návratový štát.employeeSet1.removeAll (state.employeeList1); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance (stav MyState) {return state.employeeSet2.removeAll (state.employeeList2); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance (štát MyState) {návrat state.employeeSet3.removeAll (state.employeeSet4); }

A tu sú výsledky:

Porovnávací režim Cnt Skóre Chyba jednotky 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

Môžeme vidieť HashSet.removeAll () funguje dosť zle, keď HashSet má menej prvkov ako Zbierka, ktorý sa predkladá ako argument odobrať všetky() metóda. Ale keď bude opäť druhá zbierka HashSet, potom je výkon dobrý.

5. Záver

V tomto článku sme videli výkonnosť odobrať všetky() v HashSet. Keď má sada menej prvkov ako kolekcia, potom výkon odobrať všetky() závisí od časovej zložitosti obsahuje () spôsob zberu.

Úplný kód tohto článku je ako obvykle k dispozícii na serveri GitHub.


$config[zx-auto] not found$config[zx-overlay] not found