example - list string[]> java

Encontrar si una cadena contiene alguna cadena en una colección.

Question

Estoy intentando mejorar el rendimiento de una función de Java que tengo para determinar si una cadena de búsqueda dada contiene> 0 de las cadenas de una colección. Esto podría parecer una optimización prematura, pero la función se llama MUCHO, por lo que cualquier aceleración sería muy beneficiosa.

El código actualmente se ve así:

public static boolean containsAny(String searchString, List<String> searchCollection) {
    int size = searchCollection.size();
    for (int i = 0; i < size; i++) {
        String stringInCollection = searchCollection.get(i);
        if (!Util.isNullOrEmpty(stringInCollection)) {
            // This is a performance optimization of contains.
            if (searchString.indexOf(stringInCollection, 0) > -1) {
                return true;
            }
        }
    }
    return false;
}

La lista suele tener unos 30 elementos y la misma colección se reutiliza mucho entre cada llamada.

El código de arriba es una búsqueda lineal bastante sencilla. No creo que pueda mejorarse significativamente a menos que cambiemos la estructura de datos para hacerlo mejor que O (n). ¿Hay alguna estructura de datos que me permita hacer eso?

Answer 1

¿Puedes probar con esta solución?

    final String[] searchList = searchCollection.toArray(new String[0]);
    Arrays.sort(searchList, new Comparator<String>() {
        @Override
        public int compare(final String o1, final String o2) {
            if (o1 == null && o2 == null) {
                return 0;
            }
            if (o1 == null || o1.isEmpty()) {
                return 1;
            }
            if (o2 == null || o2.isEmpty()) {
                return -1;
            }
            return o1.compareTo(o2);
        }
    });
    final int result = Arrays.binarySearch(searchList, searchString);
    return result >= 0 ? true : false;

Answer 2

@Yrlec a partir de su comentario, en el que se puede considerar que la searchCollection es constante sin muchas modificaciones, puede ordenar el arraylist y guardarlo en la memoria caché o puede implementar una clase de lista personalizada que almacene una referencia a los elementos ordenados que se le agregan.

La razón de esto es que si tiene su searchCollection ordenado, puede usar el método de cadena Comparable y reducir el número de iteraciones, mejorando así el rendimiento de su método hasta cierto punto.

public static boolean containsAny(String searchString, List<String> searchCollectionSorted) {
    int size = searchCollectionSorted.size();
    for (int i = 0; i < size; i++) {
            String stringInCollection = searchCollectionSorted.get(i);
            if (!Util.isNullOrEmpty(stringInCollection)) {
                if(stringInCollection.compareToIgnoreCase(searchString) > 0) {
                    if (searchString.startsWith(stringInCollection) {
                            return true;
                    } else {
                              // No point of iterating if we reach here as the searchstring is greater and hence iterations are saved improving performance
                            break;
                    }
                }
            }
        }    return false;
}

Answer 3

Como muchas otras personas han respondido, hay mejores estructuras de datos en general para almacenar y buscar cadenas. El problema en su caso es que su lista solo tiene 30 entradas. La sobrecarga agregada mediante el uso de una estructura de datos y un algoritmo más complejos fácilmente podría superar la ganancia que obtendría de ella.

No me malinterpretes, tu cuello de botella es la línea indexOf. Parece que representa el 95% del procesamiento. Pero si otras estructuras de datos no ayudan (probé un Aho-Corasick Trie comercial y fue dos veces más lento), aquí hay algo para verificar ...

El comentario sobre el uso de indexOf en lugar de contiene es cuestionable. En mis pruebas. Vi alrededor de 1.5 millones de búsquedas por segundo con "contiene" y solo alrededor de 700K con indexOf. Si tienes los mismos resultados, eso duplicará tu velocidad allí mismo.

Cambio

// This is a performance optimization of contains.
if (searchString.indexOf(stringInCollection, 0) > -1) {

[de regreso

if (searchString.contains(stringInCollection)) {

Si estás interesado, el trie con el que probé está aquí: http://ahocorasick.org/ y el código es bastante simple. El problema que vi es que no tiene una función para salir temprano después de encontrar la primera coincidencia. Analiza toda la cadena y encuentra todas las coincidencias. Fue más rápido que indexOf () en los casos en que no hubo coincidencias (830 K / s), pero aún más lento que el contenido en ().

Answer 4

Compare con esto una especie de versión invertida y optimizada:

  public static boolean containsAny(String searchString, List<String> searchCollection) {
    for (int offset = 0; offset < searchString.length(); offset++) {
      for (String sought: searchCollection) {
        int remainder = searchString.length() - offset;
        if (remainder >= sought.length && searchString.startsWith(sought, offset)) {
          return true;
        }
      }
    }
    return false;
  }

Tenga en cuenta el uso de startsWith con offset.

Answer 5

Creo que la estructura de datos más adecuada para esto es un árbol de sufijo . Para una cadena de tamaño n , la construcción del árbol toma Theta(n) , y la búsqueda de una subcadena de longitud m en ella, toma O(m) .

Esta es una de esas estructuras de datos que están muy bien adaptadas (y pretenden) para buscar cadenas. Es una estructura de datos muy común con muchas implementaciones en línea.

Answer 6

Es posible acelerarlo significativamente con el algoritmo de Aho-Corasick.

Puede crear un autómata Aho-Corasick para una colección utilizando el tiempo y el espacio O (longitud total de todas las cadenas de una colección). Entonces será posible verificar si una de las cadenas en una colección es una subcadena de una cadena S dada en el tiempo O (S.lenght) atravesando este autómata.

Answer 7

Esta es una operación intensiva de la CPU y no es de larga ejecución ni está bloqueada en E / S. Si está utilizando Java 8, puede usar secuencias paralelas para hacer el procesamiento en paralelo como se muestra a continuación. El método se ha cambiado para usar Collection lugar de List para mantenerlo más flexible.

public static boolean containsAny(final String searchString,
        final Collection<String> searchCollection) {
    return searchCollection.stream().parallel()
            .anyMatch(x -> searchString.indexOf(x) > -1);
}

Además, en lugar de utilizar la List , se debe usar un Set como la estructura de datos subyacente para que se eliminen las entradas duplicadas, si las hubiera.

Answer 8

Puede utilizar la estructura de datos HashSet. Pero un conjunto de hash no permitirá duplicados. Por ejemplo, no puede tener la cadena "foo" dos veces en el HashSet.

En el lado positivo, la complejidad debe ser O (1).

http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

Answer 9

TreeSet, HashSet o PrefixTree son soluciones bastante buenas. Debería preferir PrefixTree si necesita buscar si existe un prefijo determinado en la colección (complejidad O (longitud (S)); de lo contrario, use HashSet. Http://docs.oracle.com/javase/7/docs/api http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

Answer 10

Puede completar su búsqueda en aproximadamente 2/3 del tiempo utilizando el algoritmo de Aho Corasick.

La respuesta aceptada de @ user2040251 entre otros (yo incluido) sugirió el algoritmo de Aho Corasick.

Por sus comentarios, puedo ver que no está buscando una solución general sino una solución que funciona bien en un caso de uso particular.

@Vlad creó un posible conjunto de pruebas para evaluar algunas de las soluciones propuestas.

Las pruebas realizadas por @ Marco13 de la implementación de Java en http://ahocorasick.org/ indican que su implementación inicial fue más rápida.

Sus comentarios han proporcionado importantes detalles adicionales sobre el problema que está tratando de resolver:

• Aproximadamente 30 cuerdas para buscar
• Las cadenas a buscar son de 10 a 40 caracteres de largo.
• La cadena para buscar suele tener unos 100 caracteres.
• La cadena que está buscando es una ruta de archivo.

Hice un par de modificaciones rápidas a la esencia de @ Vlad para que coincidiera mejor con los detalles del problema que describiste.

Anteriormente había comentado que la implementación de Aho-Corasick que otros habían probado estaba encontrando todas las posibles coincidencias. Un método que regresó una vez que se encontró la primera coincidencia debería ser mucho más rápido. Para ver si mi intuición era correcta, creé una rama de http://ahocorasick.org/ de http://ahocorasick.org/ . ¡Esta rama ahora se ha fusionado en Aho-Corasick!

• Completo 100000 contiene todos en 4337 ms (promedio 0 ms)
• Completó 100000 contieneAnyWithRegex en 41153 ms (promedio 0 ms)
• Completó 100000 contieneAnyWithOffset en 23624 ms (promedio 0 ms)
• Completo 100000 contieneAnyAhoCorasickDotOrg en 7956 ms (promedio 0 ms)
• Completa 100000 contieneAnyAhoCorasickDotOrgMatches en 5351 ms (promedio 0 ms)
• Se completaron 100000 contenidos de AnnyAhoCorasickDYoo en 2948 ms (promedio 0 ms)
• Completo 100000 contieneAnyHospool en 7052 ms (promedio 0 ms)
• Completó 100000 contieneAnyRaita en 5397 ms (promedio 0 ms)
• Completo 100000 contieneAnyJava8StreamParallel en 8285 ms (promedio 0 ms)

También implementé un método que realizaba cada búsqueda en su propio hilo. Esa implementación fue horrible y se realizó aproximadamente 10 veces más lento.

Actualización: Desde mi prueba inicial encontré una implementación de Aho-Corasick aún más rápida.

Incluí un punto de referencia en la implementación de flujo paralelo de Java 8 sugerido por @GladwinB así como dos implementaciones de com.eaio.stringsearch .

Todavía puede haber ganancias que se tendrán. Este documento, por ejemplo, describe una variación de juego de Aho-Corasick que suena apropiada para su problema. Hacia una concordancia de cadenas más rápida para la detección de intrusiones

Answer 11

// Make a regex pattern (once only):
StringBuilder pattern = new StringBuilder();
for (String sought : searchCollection) {
    if (!Util.isNullOrEmpty(sought)) {
        if (pattern.length() != 0) {
            pattern.append(''|'');
        }
        pattern.append(Pattern.quote(sought));
    }
}
final Pattern PATTERN = Pattern.compile("(" + pattern + ")");

Esto crea un patrón de alternativas como "(abc|def|ghi)" . Podría considerar una búsqueda insensible a mayúsculas y minúsculas.

Y en la función containsAny :

Matcher m = PATTERN.matcher(searchString);
return m.find();

La compilación de Regex es relativamente inteligente. Sería comparable a usar un árbol de búsqueda de su colección de palabras buscadas: "agent" and "agitator" to ("ag", ("ent", "itator"))