por - ¿Cuál es el método de búsqueda de subcadenas más rápido en Java?

manejo de cadenas en java

Question

Necesito implementar una forma de buscar subcadenas (agujas) en una lista de cadenas (pajar) usando Java.

Más específicamente, mi aplicación tiene una lista de perfiles de usuario. Si escribo algunas letras, por ejemplo, "Ja", y luego busco, aparecerán todos los usuarios cuyo nombre contenga "ja". Por ejemplo, el resultado podría ser "Jack", "Jackson", "Jason", "Dijafu".

En Java, como sé, hay 3 métodos de compilación para ver la subcadena de búsqueda en una cadena.

1. string.contains ()

2. string.indexOf ()

3. expresión regular. es algo así como string.matches ("ja"))

Mi pregunta es: ¿Cuáles son los tiempos de ejecución de cada método anterior? cuál es la forma más rápida o más eficiente o más popular de comprobar si la lista de cadenas contiene una subcadena determinada.

Sé que existen algunos algoritmos que hacen lo mismo, como el algoritmo de búsqueda de cadenas Boyer-Moore, el algoritmo Knuth-Morris-Pratt, etc. No quiero usarlos porque solo tengo una pequeña lista de cadenas, y creo que usarlas es un poco exagerado para mí en este momento. También tengo que escribir una gran cantidad de codificación adicional para dicho algoritmo no incorporado. Si crees que mis pensamientos no son correctos, por favor no dudes en corregirme.

Answer 1

En cuanto a los tres sobre los que preguntaste, una expresión regular va a ser mucho más lenta porque requiere armar una máquina de estado completa cuando tienes un objetivo mucho más simple. Para contains vs indexOf ...

2114 public boolean contains(CharSequence s) {
2115     return indexOf(s.toString()) > -1;
2116 }

(es decir, contains solo llamadas indexOf , pero puede incurrir en una creación de String adicional en cada invocación. Esta es solo una implementación de contains , pero dado que el contrato de contains es una simplificación de indexOf , esta es probablemente la forma en que funcionará cada implementación).

Answer 2

Esto depende de la marca / versión JRE (e incluso JDK) específica. También depende / podría depender de factores como la longitud de la cadena, la probabilidad de estar contenido, en qué posición, etc. La única forma de obtener datos de rendimiento precisos es configurar su contexto exacto.

Sin embargo, en general, aString.contains() y aString.indexOf() deberían ser exactamente iguales. E incluso si una expresión regular estuviese magníficamente optimizada, no superaría el rendimiento de las dos primeras.

No, Java tampoco usa algoritmos extremadamente especializados.

Answer 3

Por el ejemplo en su pregunta, supongo que quiere hacer comparaciones insensibles a mayúsculas y minúsculas. Esos ralentizan el proceso considerablemente. Por lo tanto, si puede vivir con algunas imprecisiones, que pueden depender de la configuración regional en la que necesita hacer la comparación, y su texto largo se busca una y otra vez, podría tener sentido convertir el texto largo una vez en mayúscula, y la cadena de búsqueda también, y luego la búsqueda no distingue entre mayúsculas y minúsculas.

Answer 4

    String[] names = new String[]{"jack", "jackson", "jason", "dijafu"};
    long start = 0;
    long stop = 0;

    //Contains
    start = System.nanoTime();
    for (int i = 0; i < names.length; i++){
        names[i].contains("ja");
    }
    stop = System.nanoTime();
    System.out.println("Contains: " + (stop-start));

    //IndexOf
    start = System.nanoTime();
    for (int i = 0; i < names.length; i++){
        names[i].indexOf("ja");
    }
    stop = System.nanoTime();
    System.out.println("IndexOf: " + (stop-start));

    //Matches
    start = System.nanoTime();
    for (int i = 0; i < names.length; i++){
        names[i].matches("ja");
    }
    stop = System.nanoTime();
    System.out.println("Matches: " + (stop-start));

Salida:

Contains: 16677
IndexOf: 4491
Matches: 864018

Answer 5

La respuesta aceptada no es correcta y no está completa.

• indexOf() realiza una búsqueda ingeniosa de cadenas utilizando retroceso en desajustes. Esto es bastante rápido en patrones / textos pequeños pero muestra un rendimiento muy bajo en textos grandes
• contains("ja") debe ser comparable a indexOf (porque le delega)
• matches("ja") no arrojará el resultado correcto, porque busca una coincidencia exacta (solo la cadena "ja" coincidirá exactamente)
• Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find(); sería la forma correcta de encontrar textos con expresiones regulares. En la práctica (usando textos grandes) será la forma más eficiente usando solo la api de Java. Esto se debe a que un patrón constante (como "ja" ) no será procesado por el motor de expresiones regulares (que es lento) sino por un Boyer-Moore-Algorithm (que es rápido)

Answer 6

Si está buscando una gran cantidad de cadenas que he leído, el algoritmo Aho-Corasick es bastante rápido, pero está implementado de forma nativa en Java. Es el mismo algoritmo utilizado por GREP en los sistemas basados ​​en Unix si eso ayuda y es bastante eficiente. Aquí hay una implementación de Java cortesía de Berkley.

Ver también: https://.com/a/1765616/59087