streamalism.org

1. Pregled

HashSet je kolekcija za pohranu jedinstvenih elemenata.

U ovom uputstvu razgovarat ćemo o izvedbi ukloniti sve() metoda u java.util.HashSet razred.

2. HashSet.removeAll ()

The ukloniti sve metoda uklanja sve elemente koji su sadržani u kolekcija:

Set set = new HashSet (); set.add (1); set.add (2); set.add (3); set.add (4); Zbirka kolekcije = novi ArrayList (); collection.add (1); collection.add (3); set.removeAll (zbirka); Integer [] actualElements = novi Integer [set.size ()]; Cijeli broj [] očekivaniElementi = novi cijeli broj [] {2, 4}; assertArrayEquals (očekivaniElementi, set.toArray (stvarniElementi)); 

Kao rezultat, elementi 1 i 3 uklonit će se iz skupa.

3. Interna implementacija i vremenska složenost

RemoveAll () metoda određuje koja je manja - set ili zbirka. To se postiže pozivanjem na veličina() metoda na setu i kolekciji.

Ako zbirka ima manje elemenata od skupa, a zatim se ponavlja kroz navedenu zbirku s vremenskom složenošću O (n). Također provjerava je li element prisutan u skupu s vremenskom složenošću O (1). A ako je element prisutan, uklanja se iz skupa pomoću ukloniti() metoda skupa, koja opet ima vremensku složenost O (1). Tako ukupna vremenska složenost je O (n).

Ako skup ima manje elemenata od zbirke, zatim se iterira preko ovog skupa pomoću O (n). Zatim provjerava je li svaki element prisutan u zbirci pozivanjem svog sadrži () metoda. A ako je takav element prisutan, tada se element uklanja iz skupa. Dakle, to ovisi o vremenskoj složenosti sadrži () metoda.

U ovom slučaju, ako je zbirka ArrayList, vremenska složenost sadrži () metoda je O (m). Tako ukupna vremenska složenost uklanjanja svih elemenata prisutnih u ArrayList iz skupa je O (n * m).

Ako je zbirka opet HashSet, vremenska složenost sadrži () metoda je O (1). Tako ukupna vremenska složenost uklanjanja svih elemenata prisutnih u HashSet iz skupa je O (n).

4. Izvedba

Da bismo vidjeli razliku u izvedbi između gore navedena 3 slučaja, napišimo jednostavan JMH benchmark test.

Za prvi ćemo slučaj inicijalizirati skup i kolekciju, gdje u skupu imamo više elemenata nego zbirku. U drugom ćemo slučaju inicijalizirati skup i zbirku, gdje u zbirci imamo više elemenata od skupa. I u trećem slučaju, inicijalizirat ćemo 2 skupa, gdje ćemo imati 2. skup koji ima više elemenata od prvog:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) javna klasa HashSetBenchmark {@State (Scope.Thread) javna statička klasa MyState {private Set zaposlenikSet1 = novi HashSet (); privatni popis workerList1 = novi ArrayList (); privatni skup workerSet2 = novi HashSet (); privatni popis workerList2 = novi ArrayList (); privatni skup workerSet3 = novi HashSet (); privatni skup workerSet4 = novi HashSet (); privatno dugo set1Size = 60000; privatni dugi popis1Size = 50000; privatno dugo set2Size = 50000; privatni dugi popis2Size = 60000; privatni long set3Size = 50000; privatni long set4Size = 60000; @Setup (Level.Trial) public void setUp () {// popunjavanje skupova}}}

Nakon toga dodajemo svoje referentne testove:

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

I evo rezultata:

Referentna način CNT rezultat pogrešaka jedinice 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

Možemo vidjeti HashSet.removeAll () izvodi prilično loše kad HashSet ima manje elemenata od Kolekcija, koji se prosljeđuje kao argument ukloniti sve() metoda. Ali kad je opet druga zbirka HashSet, tada je izvedba dobra.

5. Zaključak

U ovom smo članku vidjeli izvedbu ukloniti sve() u HashSetu. Kada set ima manje elemenata od zbirke, tada je izvedba ukloniti sve() ovisi o vremenskoj složenosti sadrži () metoda prikupljanja.

Kao i obično, cjeloviti kôd za ovaj članak dostupan je na GitHubu.