streamalism.org

1. Oversigt

I denne artikel ser vi på forskellige måder at søge i en matrix efter en bestemt værdi.

Vi sammenligner også, hvordan disse fungerer ved hjælp af JMH (Java Microbenchmark Harness) for at bestemme, hvilken metode der fungerer bedst.

2. Opsætning

I vores eksempler bruger vi en matrix, der indeholder tilfældigt genereret Strenge for hver test:

String [] seedArray (int længde) {String [] strings = ny streng [længde]; Tilfældig værdi = ny tilfældig (); for (int i = 0; i <længde; i ++) {strings [i] = String.valueOf (value.nextInt ()); } returnere strenge }

For at genbruge arrayet i hvert benchmark, erklærer vi en indre klasse, der holder arrayet og optællingen, så vi kan erklære dets anvendelsesområde for JMH:

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

3. Grundlæggende søgning

Tre almindeligt anvendte metoder til søgning i en matrix er som en Liste, -en Sæt, eller med en løkke der undersøger hvert medlem, indtil det finder et match.

Lad os starte med tre metoder, der 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 bruger disse klassekommentarer til at fortælle JMH at output gennemsnitstid i mikrosekunder og køre til fem opvarmnings-iterationer for at sikre, at vores test er pålidelige:

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

Og kø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 kører med 1000 søgninger efter hver metode, ser vores resultater sådan ud:

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 

Loop-søgningen er mere effektiv end andre. Men dette skyldes i det mindste delvis, hvordan vi bruger samlinger.

Vi opretter et nyt Liste eksempel med hvert opkald til søgeliste () og en ny Liste og en ny HashSet med hvert opkald til searchSet (). Oprettelse af disse objekter skaber en ekstra omkostning, som ikke løber gennem arrayet.

4. Mere effektiv søgning

Hvad sker der, når vi opretter enkeltforekomster af Liste og Sæt og derefter genbruge dem til hver søgning?

Lad os prøve:

offentlig ugyldig 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 kører disse metoder med de samme JMH-kommentarer som ovenfor og inkluderer resultaterne for den enkle løkke til sammenligning.

Vi ser meget forskellige 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øger på Liste er marginalt hurtigere end før, Sæt falder til mindre end 1 procent af den nødvendige tid til sløjfen!

Nu hvor vi har fjernet den tid, der kræves til oprettelse af nye samlinger fra hver søgning, giver disse resultater mening.

Søgning efter en hash-tabel, strukturen bagved a HashSet, har en tidskompleksitet på 0 (1), mens en matrix, der ligger til grund for ArrayList er 0 (n).

5. Binær søgning

En anden metode til søgning i en matrix er en binær søgning. Selvom det er meget effektivt, kræver en binær søgning, at arrayet sorteres på forhånd.

Lad os sortere arrayet og prøve den binære søgning:

@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 os / op 

Binær søgning er meget hurtig, men mindre effektiv end HashSet: den værste tilfælde ydeevne for en binær søgning er 0 (log n), som placerer dens ydeevne mellem en array-søgning og en hash-tabel.

6. Konklusion

Vi har set flere metoder til at søge gennem en matrix.

Baseret på vores resultater, a HashSet fungerer bedst til at søge gennem en liste over værdier. Vi skal dog oprette dem på forhånd og gemme dem i Sæt.

Som altid er den fulde kildekode for eksemplerne tilgængelig på GitHub.