comparación de cadenas rápido en C

Question

que actualmente tiene este tipo de bucle

while(1) 
{ 
    generate_string(&buffer); 

    for(int i = 0; i < filelines; i++) 
    { 
     if(strcmp(buffer,line[i]) == 0) 
     { 
      /* do something */ 
     } 
    } 
} 

Tengo un archivo con unos pocos millones de cuerdas (que esperemos que ser cortados a la mitad en algún momento pronto), el número de todas estas cadenas es almacenado en filelines

línea [i] es básicamente donde se almacena la cadena.

Actualmente, debido a la comparación de estos millones de cadenas, la función genera_cadena (& búfer); se ejecuta alrededor de 42 veces por segundo. ¿Existe alguna forma más rápida de hacer una comparación de cadenas en C?

Answer 1

strcmp suele ser optimizado por todos los proveedores. Sin embargo, si usted no está satisfecho con esto usted puede intentar:

• búsqueda Burst Tries
• Utilice un árbol de sufijos para la comparación de cadenas rápida - ver this artículo
• Dependiendo del tamaño de las cadenas en su aplicación puede escribir un comparador de cuerdas personalizado. Por ejemplo, GNU libc solía tener esta optimización para cadenas pequeñas donde probaban cadenas de menos de cinco bytes como números enteros. MS cl también tiene algunas optimizaciones para cadenas pequeñas (busque).

Pero lo más importante asegurarse de strcmp es su verdadera cuello de botella.

Answer 2

No sé que hay un camino más rápido que llamar strcmp hacer comparaciones de cadenas, pero tal vez pueda evitar llamando strcmp tanto. Use una tabla hash para almacenar sus cadenas y luego puede verificar si la cadena en buffer está en la tabla hash. Si el índice de un hit es importante cuando "haces algo", la tabla puede asignar cadenas a los índices.

Answer 3

Puede probar algo "barato" como el análisis basado en el primer carácter. Si los primeros caracteres no coinciden, las cadenas no pueden ser iguales. Si coinciden, entonces llama a strcmp para comparar toda la cadena. Es posible que desee considerar un algoritmo mejor si es apropiado para su situación; los ejemplos serían ordenar el archivo/líneas y hacer una búsqueda binaria, usando una tabla hash, o técnicas de tabla de cuerdas similares.

Answer 4

puede que pueda pasar con una comparación binaria en este caso porque su programa no es en realidad tipo, pero se puede comparar para la igualdad.

también puede mejorar las velocidades de comparación aquí mediante la determinación de las longitudes de antelación (siempre que, por supuesto, varían lo suficiente). cuando la longitud no coincida aquí, do something no sucederá.

Por supuesto, hash aquí sería otra consideración dependiendo de cuántas veces lea el valor hash.

Answer 5

Si recibo su pregunta correctamente, debe comprobar si hay una cadena a lo largo de todas las líneas leídas hasta el momento. Yo propondría usar un TRIE o incluso mejor un Patricia tree desde las líneas de archivo.De esta forma, en lugar de recorrer todas las líneas, puedes verificar linealmente si tu cadena está presente (y con un poco más de esfuerzo, dónde).

Answer 6

Ya está compilando con optimización, ¿verdad?

Si tiene una estructura de datos de Trie o hashtable en el lugar, lista para usar, entonces debería.

En su defecto, un cambio bastante fácil que probablemente acelerará las cosas es ordenar su matriz line una vez, antes de comenzar a generar cadenas para buscar. Luego búsqueda binaria para buffer en la matriz ordenada. Es fácil porque las dos funciones que necesita son estándar: qsort y bsearch.

una búsqueda binaria en un arreglo ordenado sólo tiene que hacer al respecto registro (filelines) comparaciones de cadenas, en lugar de sobre filelines. Entonces, en su caso, eso es una comparación de cadenas de 20 y tantos por llamada a generate_string en lugar de unos pocos millones. De las cifras que ha dado, creo que razonablemente puede esperar que sea 20-25 veces más rápido, aunque no prometo nada.

Answer 7

Puedo asegurarle, la función strcmp es ABSOLUTAMENTE NO el cuello de botella. Normalmente, strcmp está bien optimizado y puede hacer comparaciones de 32 o 64 bits para cadenas de más de 4/8 bytes, dependiendo de la arquitectura. Tanto newlib como GNU libc hacen esto. Pero incluso si tuvieras que mirar cada byte en ambas cadenas 20 veces, no importa tanto como las opciones de estructura de datos de algo & aquí.

El cuello de botella real es el algoritmo de búsqueda O (N). Un solo pase O (N log N) en el archivo podría usarse en una estructura de datos apropiada (ya sea una BST normal, una trie o simplemente una matriz ordenada simple) para realizar búsquedas O (log N).

Tenga paciencia aquí - muchas matemáticas siguen. Pero creo que esta es una buena oportunidad para ilustrar por qué la elección de la estructura de datos del algoritmo & a veces es mucho más importante que el método de comparación de cadenas. Steve toca esto, pero quería explicarlo un poco más.

Con N = 1e6, log (1e6, 2) = 19.9, así que redondee hasta 20 comparaciones en una estructura de datos ideal.

Actualmente realiza una búsqueda de peor caso de operaciones O (N) o 1e6.

Digamos que acaba de construir un árbol rojo-negro con O (log N) tiempo de inserción e inserta N elementos, ese es el tiempo O (N log N) para construir el árbol. Así que eso es 1e6 x 20 o 20e6 operaciones necesarias para construir su árbol.

En su enfoque actual, la construcción de la estructura de datos es O (N), o operaciones 1e6, pero su peor tiempo de búsqueda de casos es O (N) también. Entonces, cuando lee el archivo y hace solo 20 operaciones de búsqueda, alcanza el peor caso teórico de 21,000,000 de operaciones. En comparación, su peor caso con un árbol rojo oscuro y 20 búsquedas es 20,000,400 operaciones, o 999,600 operaciones MEJOR que la búsqueda O (N) en una matriz no ordenada. Entonces, en 20 búsquedas, estás en el primer punto donde una estructura de datos más sofisticada realmente vale la pena. Pero mire lo que sucede en 1000 búsquedas:

array no ordenado = inicialización + 1000 x tiempo de búsqueda = O (N) + 1000 * O (N) = 1,000,000 + 2,000,000,000 = 2,001,000,000 operaciones.

Rojo-negro = inicialización + 1000 x tiempo de búsqueda = O (N log N) + 1000 * O (log N) = 20,000,000 + 20,000 = 20,020,000 operaciones.

2.001.000.000/20.020.000 ~ = 100x como muchas operaciones para el O (N) de búsqueda.

En 1e6 búsquedas, eso es (1e6 + 1e6 * 1e6)/(20e6 + 1e6 * 20) = 25,000x tantas operaciones.

Suponga que su equipo puede manejar las operaciones 40e6 '' que se necesita para hacer las búsquedas de registro N en 1 minuto. Tomaría 25,000 minutos o 17 DÍAS para hacer el mismo trabajo con su algoritmo actual. O bien, otra forma de observar es que el algoritmo de búsqueda O (N) solo puede manejar 39 búsquedas en el tiempo que el algoritmo O (log N) puede hacer 1,000,000. Y cuantas más búsquedas hagas, más feo será.

Ver las respuestas de Steve y dirkgently para varias opciones mejores de estructuras de datos & algoritmos. Mi única precaución adicional sería que qsort() sugerido por Steve fuerza tienen un peor caso de complejidad de O (N * N), que es mucho, mucho peor que el de O (N log N) se obtiene con un heapsort o varios estructuras parecidas a árboles.

Answer 8

Optimization of Computer Programs in C

Usted puede ahorrar un poco de tiempo marcando los primeros caracteres de las cadenas en cuestión antes de hacer la llamada. Obviamente, si los primeros caracteres son diferentes, no hay ninguna razón para llamar a strcmp para verificar el resto. Debido a la distribución no uniforme de las letras en los idiomas naturales, el resultado no es 26: 1, sino más bien 15: 1 para los datos en mayúsculas.

#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \ 
    (int) ((unsigned char) *(a) - \ 
     (unsigned char) *(b)) : \ 
    strcmp((a), (b))) 

Si el diccionario de palabras que está utilizando están bien definidas (que significa que no importa la forma valor de retorno strcmp pero el 0 == igual), por ejemplo, un conjunto de argumentos de línea de comandos que comienza con el mismo prefijo, ex: tcp-accept, tcp-reject que puede reescribir la macro y hacer algo de aritmética del puntero para comparar no el 1er pero el Nth char, en este caso, el 4º char, ej:

#define QUICKIE_STRCMP(a, b, offset) \ 
      (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))