streamalism.org

1. Pregled

U ovom ćemo članku razmotriti različite načine pretraživanja polja za određenu vrijednost.

Također ćemo usporediti njihov učinak pomoću JMH (Java Microbenchmark Harness) kako bismo utvrdili koja metoda najbolje djeluje.

2. Postavljanje

Za naše primjere koristit ćemo niz koji sadrži nasumično generirane Žice za svaki test:

String [] seedArray (int length) {String [] stringovi = novi String [length]; Slučajna vrijednost = novo Random (); for (int i = 0; i <length; i ++) {string [i] = String.valueOf (value.nextInt ()); } vratiti nizove; }

Da bismo ponovno koristili niz u svakoj referentnoj vrijednosti, proglasit ćemo unutarnju klasu koja sadrži niz i count kako bismo mogli proglasiti njegov opseg za JMH:

@State (Scope.Benchmark) javna statička klasa SearchData {static int count = 1000; statički niz [] nizovi = seedArray (1000); } 

3. Osnovno pretraživanje

Tri najčešće korištene metode pretraživanja niza su kao Popis, a Postavi, ili s petljom koja ispituje svakog člana dok ne pronađe podudarnost.

Počnimo s tri metode koje implementiraju svaki algoritam:

boolean searchList (String [] stringovi, String searchString) {return Arrays.asList (SearchData.strings) .contains (searchString); } boolean searchSet (String [] stringovi, String searchString) {Set stringSet = new HashSet (Arrays.asList (SearchData.strings)); return stringSet.contains (searchString); } boolean searchLoop (String [] stringovi, String searchString) {for (String string: SearchData.strings) {if (string.equals (searchString)) return true; } return false; }

Koristit ćemo ove bilješke klase da kažemo JMH-u da izbaci prosječno vrijeme u mikrosekundama i pokrene pet iteracija zagrijavanja kako bi osigurao pouzdanost naših testova:

@BenchmarkMode (Mode.AverageTime) @Warmup (iteracije = 5) @OutputTimeUnit (TimeUnit.MICROSECONDS) 

I pokrenite svaki test u petlji:

@Benchmark javna praznina searchArrayLoop () {for (int i = 0; i <SearchData.count; i ++) {searchLoop (SearchData.strings, "T"); }} @Benchmark javna praznina searchArrayAllocNewList () {for (int i = 0; i <SearchData.count; i ++) {searchList (SearchData.strings, "T"); }} @Benchmark javna praznina searchArrayAllocNewSet () {for (int i = 0; i <SearchData.count; i ++) {searchSet (SearchData.strings, "S"); }} 

Kada pokrenemo 1000 pretraživanja za svaku metodu, naši rezultati izgledaju otprilike ovako:

SearchArrayTest.searchArrayAllocNewList avgt 20 937.851 ± 14.226 us / op SearchArrayTest.searchArrayAllocNewSet avgt 20 14309.122 ± 193.844 us / op SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 933.860 us / 9 

Pretraživanje petlje učinkovitije je od ostalih. Ali to je barem djelomično zbog načina na koji koristimo zbirke.

Stvaramo novi Popis primjer sa svakim pozivom na searchList () i novi Popis i novi HashSet sa svakim pozivom na searchSet (). Stvaranje ovih objekata stvara dodatni trošak koji petljanje kroz niz nema.

4. Učinkovitije pretraživanje

Što se događa kada stvorimo pojedinačne primjerke Popis i Postavi a zatim ih ponovno upotrijebiti za svako pretraživanje?

Pokušajmo:

public void searchArrayReuseList () {Popis asList = Arrays.asList (SearchData.strings); for (int i = 0; i <SearchData.count; i ++) {asList.contens ("T"); }} public void searchArrayReuseSet () {Set asSet = new HashSet (Arrays.asList (SearchData.strings)); for (int i = 0; i <SearchData.count; i ++) {asSet.contens ("T"); }} 

Izvršit ćemo ove metode s istim JMH bilješkama kao gore, a za usporedbu ćemo uključiti rezultate za jednostavnu petlju.

Vidimo vrlo različite rezultate:

SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 9.433 us / op SearchArrayTest.searchArrayReuseList avgt 20 837.265 ± 11.283 us / op SearchArrayTest.searchArrayReuseSet avgt 20 14.030 ± 0.197 us / op 

Tijekom pretraživanja Popis je neznatno brži nego prije, Postavi pada na manje od 1 posto vremena potrebnog za petlju!

Sad kad smo iz svakog pretraživanja uklonili vrijeme potrebno za stvaranje novih zbirki, ovi rezultati imaju smisla.

Pretražujući hash tablicu, strukturu koja stoji u osnovi a HashSet, ima vremensku složenost 0 (1), dok niz koji je u osnovi ArrayList je 0 (n).

5. Binarno pretraživanje

Druga metoda pretraživanja niza je binarno pretraživanje. Iako je vrlo učinkovito, binarno pretraživanje zahtijeva da se niz sortira unaprijed.

Razvrstajmo niz i isprobajmo binarno pretraživanje:

@Benchmark javna praznina searchArrayBinarySearch () {Arrays.sort (SearchData.strings); for (int i = 0; i <SearchData.count; i ++) {Arrays.binarySearch (SearchData.strings, "T"); }} 

SearchArrayTest.searchArrayBinarySearch prosj. 20 26.527 ± 0,376 us / op 

Binarno pretraživanje je vrlo brzo, iako manje učinkovito od HashSet: najlošija izvedba binarnog pretraživanja je 0 (log n), koja svoju izvedbu postavlja između pretraživanja niza i hash tablice.

6. Zaključak

Vidjeli smo nekoliko metoda pretraživanja niza.

Na temelju naših rezultata, a HashSet najbolje djeluje za pretraživanje popisa vrijednosti. Međutim, moramo ih stvoriti unaprijed i pohraniti u Postavi.

Kao i uvijek, puni izvorni kod primjera dostupan je na GitHub-u.