streamalism.org

1. Uvod

U ovom kratkom vodiču, razgovarat ćemo o izvedbi sadrži () metoda dostupna u java.util.HashSet i java.util.ArrayList. Obje su zbirke za pohranu i manipulaciju objektima.

HashSet je kolekcija za pohranu jedinstvenih elemenata. Da biste saznali više o HashSet, pogledajte ovaj link.

ArrayList je popularna provedba java.util.Popis sučelje.

Imamo prošireni članak o ArrayList dostupno ovdje.

2. HashSet.contens ()

Interno, HashSet provedba se temelji na a HashMap primjer. The sadrži () pozivi metode HashMap.containsKey (objekt).

Ovdje provjerava je li objekt nalazi se na internoj karti ili ne. Interna karta pohranjuje podatke unutar čvorova, poznatih kao segmenti. Svaki segment odgovara hash kodu generiranom s hashCode () metoda. Tako sadrži () zapravo koristi hashCode () metoda za pronalaženje objekt mjesto.

Sada odredimo složenost vremena pretraživanja. Prije nego što krenete naprijed, provjerite jeste li upoznati s oznakom Big-O.

U prosjeku, the sadrži () od HashSet uleti O (1) vrijeme. Dobivanje objekt položaj kante je konstantna vremenska operacija. Uzimajući u obzir moguće sudare, vrijeme traženja može se povećati zapisnik (n) jer je unutarnja struktura kante a TreeMap.

Ovo je poboljšanje u odnosu na Javu 7 koja je koristila a LinkedList za unutarnju strukturu kante. Općenito, kolizije hash koda su rijetke. Dakle, složenost pretraživanja elemenata možemo smatrati kao O (1).

3. ArrayList.czadržava ()

Interno, ArrayList koristi indexOf (objekt) metoda za provjeru nalazi li se objekt na popisu. The indexOf (objekt) metoda ponavlja čitav niz i uspoređuje svaki element s jednako (objekt) metoda.

Vraćajući se analizi složenosti, ArrayList.sadrži () metoda zahtijeva Na) vrijeme. Dakle, vrijeme koje trošimo na pronalaženje određenog predmeta ovdje ovisi o broju predmeta koje imamo u nizu.

4. Benchmark testiranje

Sada, zagrijmo JVM testom mjerenja performansi. Koristit ćemo JMH (Java Microbenchmark Harness) OpenJDK proizvod. Da biste saznali više o postavljanju i izvođenju, pogledajte naš korisni vodič.

Za početak, stvorimo jednostavan Zbirke Benchmark razred:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) javna klasa CollectionsBenchmark {@State (Scope.Thread) javna statička klasa MyState {private Set zaposlenikSet = novi HashSet (); privatni popis workerList = novi ArrayList (); privatne duge iteracije = 1000; privatni zaposlenik zaposlenik = novi zaposlenik (100 L, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {workerSet.add (new Employee (i, "John")); workerList.add (novi zaposlenik (i, "John")); } workerList.add (zaposlenik); workerSet.add (zaposlenik); }}}

Ovdje stvaramo i inicijaliziramo HashSet i an ArrayList od Zaposlenik objekti:

zaposlenik u javnoj klasi {private Long id; privatni naziv niza; // postavljači konstruktora i gettera idite ovdje}

Dodamo zaposlenik = novi zaposlenik (100 L, "Harry") primjer kao posljednji elementi obje zbirke. Pa testiramo zaposlenik traženje objekta za najgori mogući slučaj.

@OutputTimeUnit (TimeUnit.NANOSECONDS) označava da rezultate želimo u nanosekundama. Zadani broj @Zagrijati se ponavljanja su 5 u našem slučaju. The @BenchmarkMode postavljeno je na Način rada. Prosječno vrijeme, što znači da nas zanima izračunavanje prosječnog vremena rada. Za prvo izvršenje smo stavili iteracija = 1000 predmeta u našim kolekcijama.

Nakon toga dodajemo naše referentne metode u Zbirke Benchmark razred:

@Benchmark javni logički testArrayList (stanje MyState) {return state.employeeList.contains (state.employee); }

Ovdje provjeravamo je li popisa zaposlenika sadrži zaposlenik objekt.

Isto tako, imamo poznati test za zaposlenikSet:

@Benchmark javni logički testHashSet (stanje MyState) {return state.employeeSet.contains (state.employee); }

Napokon, možemo pokrenuti test:

public static void main (String [] args) baca iznimku {Options options = new OptionsBuilder () .include (CollectionsBenchmark.class.getSimpleName ()) .forks (1) .build (); novi Runner (opcije) .run (); }

Evo rezultata:

Benchmark Mode Cnt Score Pogreška Jedinice CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns / op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns / op

Jasno možemo vidjeti da testArrayList metoda ima 4035.646 ns prosječni rezultat pretraživanja, dok je testHashSet brže izvodi sa 9.456 ns U prosjeku.

Povećamo sada broj elemenata u našem testu i pokrenimo ga za iteracije = 10.000 predmeta:

Benchmark Mode Cnt Score Greške Jedinice Jedinice CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns / op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns / op

Ovdje također, sadrži () u HashSet ima veliku prednost u izvedbi u odnosu na ArrayList.

5. Zaključak

Ovo brzo objašnjenje objašnjava performanse sadrži () metoda HashSet i ArrayList zbirke. Uz pomoć JMH benčmarkinga predstavili smo izvedbu sadrži () za svaku vrstu kolekcije.

Kao zaključak možemo to naučiti the sadrži () metoda brže djeluje u HashSet u usporedbi s an ArrayList.

Kao i obično, kompletan kôd za ovaj članak gotov je na projektu GitHub.