Vérifier si un tableau Java contient une valeur

1. Vue d'ensemble

Dans cet article, nous examinerons différentes manières de rechercher dans un tableau une valeur spécifiée.

Nous comparerons également leurs performances à l'aide de JMH (Java Microbenchmark Harness) pour déterminer quelle méthode fonctionne le mieux.

2. Configuration

Pour nos exemples, nous utiliserons un tableau contenant des chaînes générées aléatoirement pour chaque 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; }

Pour réutiliser le tableau dans chaque benchmark, nous déclarerons une classe interne pour contenir le tableau et le nombre afin que nous puissions déclarer sa portée pour JMH:

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

3. Recherche de base

Trois méthodes couramment utilisées pour rechercher un tableau sont une liste, un ensemble ou une boucle qui examine chaque membre jusqu'à ce qu'il trouve une correspondance.

Commençons par trois méthodes qui implémentent chaque algorithme:

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

Nous utiliserons ces annotations de classe pour indiquer à JMH de générer le temps moyen en microsecondes et d'exécuter cinq itérations de préchauffage pour garantir la fiabilité de nos tests:

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

Et exécutez chaque test en boucle:

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

Lorsque nous exécutons 1000 recherches pour chaque méthode, nos résultats ressemblent à ceci:

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 recherche en boucle est plus efficace que les autres. Mais c'est au moins en partie à cause de la façon dont nous utilisons les collections.

Nous créons une nouvelle instance de List avec chaque appel à searchList () et une nouvelle List et un nouveau HashSet avec chaque appel à searchSet () . La création de ces objets crée un coût supplémentaire que la boucle dans le tableau ne le fait pas.

4. Recherche plus efficace

Que se passe-t-il lorsque nous créons des instances uniques de List et Set , puis que nous les réutilisons pour chaque recherche?

Essayons:

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

Nous exécuterons ces méthodes avec les mêmes annotations JMH que ci-dessus et inclurons les résultats de la boucle simple à des fins de comparaison.

Nous voyons des résultats très différents:

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 

Alors que la recherche dans la liste est légèrement plus rapide qu'avant, Set tombe à moins de 1 pour cent du temps requis pour la boucle!

Maintenant que nous avons supprimé le temps nécessaire pour créer de nouvelles collections à chaque recherche, ces résultats ont du sens.

La recherche dans une table de hachage, la structure sous-jacente à un HashSet , a une complexité temporelle de 0 (1), tandis qu'un tableau, qui sous-tend ArrayList, est 0 (n).

5. Recherche binaire

Une autre méthode pour rechercher un tableau est une recherche binaire. Bien que très efficace, une recherche binaire nécessite que le tableau soit trié à l'avance.

Trions le tableau et essayons la recherche binaire:

@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 recherche binaire est très rapide, bien que moins efficace que le HashSet: le pire des cas pour une recherche binaire est 0 (log n), ce qui place ses performances entre celles d'une recherche de tableau et d'une table de hachage.

6. Conclusion

Nous avons vu plusieurs méthodes de recherche dans un tableau.

Sur la base de nos résultats, un HashSet fonctionne mieux pour rechercher dans une liste de valeurs. Cependant, nous devons les créer à l'avance et les stocker dans l' ensemble.

Comme toujours, le code source complet des exemples est disponible à l'adresse over sur GitHub.