Ellenőrizze, hogy a Java tömb tartalmaz-e értéket

1. Áttekintés

Ebben a cikkben megvizsgáljuk, hogyan lehet egy tömbben keresni egy megadott értéket.

Összehasonlítjuk továbbá ezek teljesítményét a JMH (Java Microbenchmark Harness) használatával, hogy meghatározzuk, melyik módszer működik a legjobban.

2. Beállítás

Példáinkhoz egy tömböt fogunk használni, amely véletlenszerűen generált Húrok minden tesztre:

String [] seedArray (int hossz) {String [] karakterlánc = új String [hossz]; Véletlenszerű érték = new Véletlenszerű (); for (int i = 0; i <hossz; i ++) {karakterláncok [i] = String.valueOf (érték.nextInt ()); } visszatérési húrok; }

Az egyes benchmarkokban található tömb újrafelhasználásához deklarálunk egy belső osztályt, amely megtartja a tömböt és a számlálást, így kijelenthetjük annak hatókörét a JMH számára:

@State (Scope.Benchmark) public static class SearchData {static int count = 1000; statikus karakterlánc [] karakterláncok = seedArray (1000); } 

3. Alapvető keresés

A tömb keresésére három általánosan használt módszer a Lista, a Készlet, vagy hurokkal amely megvizsgálja az egyes tagokat, amíg talál egyezést.

Kezdjünk három módszerrel, amelyek mindegyik algoritmust megvalósítják:

logikai searchList (String [] karakterláncok, String searchString) {return Arrays.asList (SearchData.strings) .contains (searchString); } logikai keresésSet (String [] karakterláncok, String searchString) {Set stringSet = új HashSet (Arrays.asList (SearchData.strings)); return stringSet.contains (searchString); } logikai keresési ciklus (String [] karakterláncok, String searchString) {for (String string: SearchData.strings) {if (string.equals (searchString)) true értékkel tér vissza; } return false; }

Ezekkel az osztályjegyzetekkel közöljük a JMH-val, hogy adja ki az átlagos időt mikroszekundumokban, és futtasson öt bemelegítési iterációt a tesztek megbízhatóságának biztosítása érdekében:

@BenchmarkMode (Mode.AverageTime) @Warmup (iterációk = 5) @OutputTimeUnit (TimeUnit.MICROSECONDS) 

És minden tesztet hurokban futtasson:

@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"); }} 

Ha 1000 keresést futtatunk az egyes módszerekhez, eredményeink így néznek ki:

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 ± 9.433 us / op 

A hurokkeresés hatékonyabb, mint mások. De ez legalább részben annak köszönhető, hogy miként használjuk a gyűjteményeket.

Készítünk egy újat Lista példány minden egyes híváskor searchList () és egy új Lista és egy új HashSet minden hívással searchSet (). Ezeknek az objektumoknak a létrehozása többletköltséget jelent, amelyet a tömbön keresztüli hurok nem.

4. Hatékonyabb keresés

Mi történik, ha egyetlen példányt hozunk létre Lista és Készlet és aztán újra felhasználja őket minden egyes keresésre?

Próbáljuk meg:

public void searchArrayReuseList () {List asList = Arrays.asList (SearchData.strings); for (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.szám; i ++) {asSet.contains ("T"); }} 

Ezeket a módszereket ugyanazokkal a JMH kommentárokkal futtatjuk, mint a fentiek, és összehasonlítás céljából belefoglaljuk az egyszerű hurok eredményeit.

Nagyon különböző eredményeket látunk:

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 

Miközben a Lista kissé gyorsabb, mint korábban, Készlet a ciklushoz szükséges idő kevesebb mint 1 százalékára csökken!

Most, hogy minden keresésből eltávolítottuk az új Gyűjtemények létrehozásához szükséges időt, ezeknek az eredményeknek van értelme.

Hash tábla keresése, az a mögöttes szerkezet HashSet, az idő bonyolultsága 0 (1), míg egy tömb, amely az Tömb lista értéke 0 (n).

5. Bináris keresés

A tömb másik keresési módja a bináris keresés. Bár a bináris keresés nagyon hatékony, a tömböt előre el kell rendezni.

Rendezzük a tömböt, és próbáljuk ki a bináris keresést:

@Benchmark public void searchArrayBinarySearch () {Arrays.sort (SearchData.strings); for (int i = 0; i <SearchData.count; i ++) {Arrays.binarySearch (SearchData.strings, "T"); }} 
SearchArrayTest.searchArrayBinarySearch avgt 20 26.527 ± 0.376 us / op 

A bináris keresés nagyon gyors, bár kevésbé hatékony, mint a HashSet: a bináris keresés legrosszabb esete a 0 (log n), amely a tömb keresés és a hash tábla teljesítményét helyezi el.

6. Következtetés

Számos módszert láthattunk egy tömbön keresztül történő keresésre.

Eredményeink alapján a HashSet akkor működik a legjobban, ha értéklistán keres. Előre kell azonban hoznunk őket, és a Készlet.

Mint mindig, a példák teljes forráskódja elérhető a GitHubon.