Controlla se un array Java contiene un valore

1. Panoramica

In questo articolo, esamineremo diversi modi per cercare un array per un valore specificato.

Confronteremo anche come questi si comportano usando JMH (il Java Microbenchmark Harness) per determinare quale metodo funziona meglio.

2. Configurazione

Per i nostri esempi, utilizzeremo un array che contiene stringhe generate casualmente per ogni test:

String[] seedArray(int length) { String[] strings = new String[length]; Random value = new Random(); for (int i = 0; i < length; i++) { strings[i] = String.valueOf(value.nextInt()); } return strings; }

Per riutilizzare l'array in ogni benchmark, dichiareremo una classe interna per contenere l'array e il conteggio in modo da poter dichiarare il suo ambito per JMH:

@State(Scope.Benchmark) public static class SearchData { static int count = 1000; static String[] strings = seedArray(1000); } 

3. Ricerca di base

Tre metodi comunemente utilizzati per la ricerca un array sono come un elenco, un insieme, o con un'ansa che esamina ogni membro finché non trova una corrispondenza.

Cominciamo con tre metodi che implementano ogni algoritmo:

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; }

Useremo queste annotazioni di classe per dire a JMH di produrre il tempo medio in microsecondi e di eseguire cinque iterazioni di riscaldamento per garantire che i nostri test siano affidabili:

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

Ed esegui ogni test in un ciclo:

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

Quando eseguiamo 1000 ricerche per ogni metodo, i nostri risultati assomigliano a questo:

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 

La ricerca in loop è più efficiente di altre. Ma questo è almeno in parte dovuto al modo in cui utilizziamo le raccolte.

Stiamo creando una nuova istanza di List con ogni chiamata a searchList () e un nuovo List e un nuovo HashSet con ogni chiamata a searchSet () . La creazione di questi oggetti crea un costo aggiuntivo che il ciclo attraverso l'array non fa.

4. Ricerca più efficiente

Cosa succede quando creiamo singole istanze di List e Set e poi le riutilizziamo per ogni ricerca?

Proviamolo:

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

Eseguiremo questi metodi con le stesse annotazioni JMH di cui sopra e includeremo i risultati per il ciclo semplice per il confronto.

Vediamo risultati molto diversi:

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 

Mentre la ricerca nell'elenco è leggermente più veloce di prima, Set scende a meno dell'1 percento del tempo richiesto per il ciclo!

Ora che abbiamo rimosso il tempo necessario per creare nuove raccolte da ogni ricerca, questi risultati hanno senso.

La ricerca in una tabella hash, la struttura sottostante un HashSet , ha una complessità temporale pari a 0 (1), mentre un array, che sta alla base di ArrayList, è 0 (n).

5. Ricerca binaria

Un altro metodo per cercare un array è una ricerca binaria. Sebbene molto efficiente, una ricerca binaria richiede che l'array sia ordinato in anticipo.

Ordiniamo l'array e proviamo la ricerca binaria:

@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 

La ricerca binaria è molto veloce, anche se meno efficiente dell'HashSet: la prestazione peggiore per una ricerca binaria è 0 (log n), che pone le sue prestazioni tra quella di una ricerca in array e una tabella hash.

6. Conclusione

Abbiamo visto diversi metodi di ricerca in un array.

In base ai nostri risultati, un HashSet funziona meglio per la ricerca in un elenco di valori. Tuttavia, dobbiamo crearli in anticipo e memorizzarli nel Set.

Come sempre, il codice sorgente completo degli esempi è disponibile su GitHub.