1. Información general
En este artículo, veremos diferentes formas de buscar una matriz para un valor específico.
También compararemos cómo funcionan con JMH (Java Microbenchmark Harness) para determinar qué método funciona mejor.
2. Configuración
Para nuestros ejemplos, usaremos una matriz que contiene cadenas generadas aleatoriamente para cada prueba:
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; }Para reutilizar la matriz en cada punto de referencia, declararemos una clase interna para contener la matriz y el recuento para que podamos declarar su alcance para JMH:
@State(Scope.Benchmark) public static class SearchData { static int count = 1000; static String[] strings = seedArray(1000); } 3. Búsqueda básica
Tres métodos comúnmente usados para buscar una matriz son como una Lista, un Conjunto o con un bucle que examina cada miembro hasta que encuentra una coincidencia.
Comencemos con tres métodos que implementan cada 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; }Usaremos estas anotaciones de clase para decirle a JMH que genere el tiempo promedio en microsegundos y se ejecute durante cinco iteraciones de calentamiento para garantizar que nuestras pruebas sean confiables:
@BenchmarkMode(Mode.AverageTime) @Warmup(iterations = 5) @OutputTimeUnit(TimeUnit.MICROSECONDS) Y ejecuta cada prueba en un bucle:
@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"); } } Cuando ejecutamos 1000 búsquedas para cada método, nuestros resultados se ven así:
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 búsqueda de bucle es más eficiente que otras. Pero esto se debe, al menos en parte, a cómo usamos las colecciones.
Estamos creando una nueva instancia de List con cada llamada a searchList () y una nueva List y un nuevo HashSet con cada llamada a searchSet () . La creación de estos objetos crea un costo adicional que no se genera al recorrer la matriz.
4. Búsqueda más eficiente
¿Qué sucede cuando creamos instancias únicas de List y Set y luego las reutilizamos para cada búsqueda?
Hagamos un intento:
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"); } } Ejecutaremos estos métodos con las mismas anotaciones JMH que las anteriores e incluiremos los resultados del ciclo simple para compararlos.
Vemos resultados muy diferentes:
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 Si bien la búsqueda en la Lista es un poco más rápida que antes, Set se reduce a menos del 1 por ciento del tiempo requerido para el ciclo.
Ahora que hemos eliminado el tiempo necesario para crear nuevas colecciones de cada búsqueda, estos resultados tienen sentido.
La búsqueda de una tabla hash, la estructura subyacente a un HashSet , tiene una complejidad de tiempo de 0 (1), mientras que una matriz, que subyace a ArrayList, es 0 (n).
5. Búsqueda binaria
Otro método para buscar una matriz es una búsqueda binaria. Si bien es muy eficiente, una búsqueda binaria requiere que la matriz se ordene de antemano.
Ordenemos la matriz e intentemos la búsqueda 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 búsqueda binaria es muy rápida, aunque menos eficiente que el HashSet: el peor rendimiento de una búsqueda binaria es 0 (log n), que coloca su rendimiento entre el de una búsqueda de matriz y una tabla hash.
6. Conclusión
Hemos visto varios métodos de búsqueda a través de una matriz.
Según nuestros resultados, un HashSet funciona mejor para buscar en una lista de valores. Sin embargo, debemos crearlos con anticipación y almacenarlos en el conjunto.
Como siempre, el código fuente completo de los ejemplos está disponible en GitHub.