streamalism.org

1. Prehľad

V tomto článku sa pozrieme na rôzne spôsoby vyhľadávania zadanej hodnoty v poli.

Porovnáme tiež ich výkon pomocou JMH (Java Microbenchmark Harness), aby sme určili, ktorá metóda funguje najlepšie.

2. Inštalácia

Pre naše príklady použijeme pole, ktoré obsahuje náhodne vygenerované Struny pre každú skúšku:

String [] seedArray (int length) {String [] strings = new String [length]; Náhodná hodnota = nová Náhodná (); for (int i = 0; i <length; i ++) {strings [i] = String.valueOf (value.nextInt ()); } návratové reťazce; }

Ak chcete pole znova použiť v každej referenčnej hodnote, deklarujeme vnútornú triedu, ktorá drží pole a počet, aby sme mohli deklarovať jeho rozsah pre JMH:

@State (Scope.Benchmark) verejná statická trieda SearchData {static int count = 1000; statický reťazec [] reťazce = seedArray (1000); } 

3. Základné vyhľadávanie

Tri bežne používané metódy na hľadanie v poli sú ako a Zoznam, a Sada, alebo so slučkou ktorá skúma každého člena, kým nenájde zhodu.

Začnime s tromi metódami, ktoré implementujú každý algoritmus:

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

Tieto anotácie triedy použijeme na to, aby sme povedali JMH, aby vyprodukoval priemerný čas v mikrosekundách a spustil päť iterácií zahrievania, aby sme zaistili spoľahlivosť našich testov:

@BenchmarkMode (Mode.AverageTime) @Warmup (iterácie = 5) @OutputTimeUnit (TimeUnit.MICROSECONDS) 

A spustite každý test v slučke:

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

Keď spustíme 1000 vyhľadávaní pre každú metódu, naše výsledky vyzerajú asi takto:

SearchArrayTest.searchArrayAllocNewList priem. 20 937,851 ± 14,226 us / op SearchArrayTest.searchArrayAllocNewSet priem. 20 14309,122 ± 193,844 us / op SearchArrayTest.searchArrayLoop priem. 20 758,060 ± 9,433 us / op 

Vyhľadávanie slučiek je efektívnejšie ako iné. Ale je to aspoň čiastočne kvôli tomu, ako používame zbierky.

Vytvárame nový Zoznam napríklad s každým volaním na searchList () a nový Zoznam a nový HashSet s každým volaním na searchSet (). Vytváranie týchto objektov vytvára ďalšie náklady, ktoré opakovanie poľa nemá.

4. Efektívnejšie vyhľadávanie

Čo sa stane, keď vytvoríme jednotlivé inštancie Zoznam a Nastaviť a potom ich znova použiť na každé vyhľadávanie?

Vyskúšajme to:

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

Spustíme tieto metódy s rovnakými anotáciami JMH ako vyššie a pre porovnanie uvedieme výsledky pre jednoduchú slučku.

Vidíme veľmi odlišné výsledky:

SearchArrayTest.searchArrayLoop priem. 20 758,060 ± 9,433 us / op SearchArrayTest.searchArrayReuseList priem. 20 837,265 ± 11 283 us / op SearchArrayTest.searchArrayReuseSet priem. 

Pri prehľadávaní Zoznam je o niečo rýchlejší ako predtým, Nastaviť klesne na menej ako 1 percento času potrebného na vytvorenie slučky!

Teraz, keď sme z každého vyhľadávania odstránili čas potrebný na vytvorenie nových zbierok, majú tieto výsledky zmysel.

Hľadanie hashovacej tabuľky, štruktúra, z ktorej vychádza a HashSet, má časovú zložitosť 0 (1), zatiaľ čo pole, ktoré je základom ArrayList je 0 (n).

5. Binárne vyhľadávanie

Ďalším spôsobom vyhľadávania poľa je binárne vyhľadávanie. Aj keď je binárne vyhľadávanie veľmi efektívne, vyžaduje, aby bolo pole vopred zoradené.

Poďme zoradiť pole a skúsiť binárne vyhľadávanie:

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

SearchArrayTest.searchArrayBinarySearch priem. 20 26 527 ± 0,376 us / op 

Binárne vyhľadávanie je veľmi rýchle, aj keď menej efektívne ako HashSet: najhorší výkon pre binárne vyhľadávanie je 0 (log n), ktorý umiestňuje jeho výkon medzi výkonnosť hľadania poľa a hash tabuľku.

6. Záver

Videli sme niekoľko metód prehľadávania poľa.

Na základe našich výsledkov, a HashSet funguje najlepšie pri prehľadávaní zoznamu hodnôt. Musíme ich však vopred vytvoriť a uložiť do priečinka Nastaviť.

Celý zdrojový kód príkladov je ako vždy k dispozícii na serveri GitHub.