streamalism.org

1. Oversikt

I denne artikkelen vil vi se på forskjellige måter å søke i en matrise etter en spesifisert verdi.

Vi vil også sammenligne hvordan disse fungerer med JMH (Java Microbenchmark Harness) for å bestemme hvilken metode som fungerer best.

2. Oppsett

For eksemplene våre bruker vi en matrise som inneholder tilfeldig generert Strenger for hver test:

Streng [] seedArray (int-lengde) {Streng [] strenger = ny streng [lengde]; Tilfeldig verdi = ny Tilfeldig (); for (int i = 0; i <lengde; i ++) {strenger [i] = String.valueOf (value.nextInt ()); } returnere strenger; }

For å gjenbruke matrisen i hvert mål, vil vi erklære en indre klasse for å holde matrisen og tellingen, slik at vi kan erklære omfanget av JMH:

@State (Scope.Benchmark) offentlig statisk klasse SearchData {statisk intall = 1000; statisk streng [] strenger = seedArray (1000); } 

3. Grunnleggende søk

Tre vanlige metoder for å søke i en matrise er som en Liste, en Sett, eller med en løkke som undersøker hvert medlem til det finner en kamp.

La oss starte med tre metoder som implementerer hver algoritme:

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

Vi bruker disse klassekommentarene for å fortelle JMH å sende gjennomsnittlig tid i mikrosekunder og løpe for fem oppvarmingsoppgaver for å sikre at testene våre er pålitelige:

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

Og kjør hver test i en løkke:

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

Når vi kjører med 1000 søk etter hver metode, ser resultatene våre slik ut:

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 

Sløyfesøket er mer effektivt enn andre. Men dette er i det minste delvis på grunn av hvordan vi bruker samlinger.

Vi lager et nytt Liste forekomst med hver samtale til søkeliste () og en ny Liste og en ny HashSet med hver samtale til searchSet (). Å lage disse objektene skaper en ekstra kostnad som ikke går gjennom matrisen.

4. Mer effektivt søk

Hva skjer når vi oppretter enkeltforekomster av Liste og Sett og deretter bruke dem på nytt for hvert søk?

La oss gi det en sjanse:

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.count; i ++) {asSet.contains ("T"); }} 

Vi kjører disse metodene med de samme JMH-merknadene som ovenfor, og inkluderer resultatene for den enkle sløyfen til sammenligning.

Vi ser veldig forskjellige resultater:

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 

Mens du søker i Liste er marginalt raskere enn før, Sett faller til mindre enn 1 prosent av tiden som kreves for løkken!

Nå som vi har fjernet tiden som kreves for å lage nye samlinger fra hvert søk, gir disse resultatene mening.

Søke i en hash-tabell, strukturen som ligger til grunn for a HashSet, har en tidskompleksitet på 0 (1), mens en matrise som ligger til grunn for ArrayList er 0 (n).

5. Binært søk

En annen metode for å søke i en matrise er et binært søk. Selv om det er veldig effektivt, krever et binært søk at matrisen sorteres på forhånd.

La oss sortere matrisen og prøve det binære søket:

@Benchmark offentlig ugyldig 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 

Binært søk er veldig raskt, men mindre effektivt enn HashSet: worst case-ytelsen for et binært søk er 0 (log n), som plasserer ytelsen mellom en array-søk og en hash-tabell.

6. Konklusjon

Vi har sett flere metoder for å søke gjennom en matrise.

Basert på resultatene våre, a HashSet fungerer best for å søke gjennom en liste over verdier. Vi må imidlertid lage dem på forhånd og lagre dem i Sett.

Som alltid er hele kildekoden til eksemplene tilgjengelig på GitHub.