Versión optimizada de strstr (la búsqueda tiene longitud constante)

Question

Mi programa C tenía muchas llamadas de función strstr. La biblioteca estándar strstr ya es rápida, pero en mi caso la cadena de búsqueda siempre tiene una longitud de 5 caracteres. Me lo reemplazó con una versión especial para ganar algo de velocidad:

 
int strstr5(const char *cs, const char *ct) 
{ 
    while (cs[4]) { 

     if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4]) 
      return 1; 

     cs++; 
    } 

    return 0; 
} 

La función devuelve un entero porque es suficiente para saber si ct ocurre en cs. Mi función es simple y más rápida que strstr estándar en este caso especial, pero estoy interesado en saber si alguien tiene algunas mejoras de rendimiento que podrían aplicarse. Incluso pequeñas mejoras son bienvenidas.

Resumen:

• cs tiene longitud de> = 10, pero lo contrario puede variar. La longitud se conoce antes (no se usa en mi función). Duración del CS es generalmente de 100 a 200.
• ct tiene una longitud de 5
• contenido de cadenas puede ser cualquier cosa

---

Editar: Gracias por todas las respuestas y comentarios. Tengo que estudiar y probar ideas para ver qué funciona mejor. Comenzaré con la idea de MAK sobre el sufijo trie.

Answer 1

Hay varios string search algorithms rápidos. Intente mirar Boyer-Moore (como ya lo sugirió Greg Hewgill), Rabin-Karp y KMP algoritmos.

Si necesita buscar muchos patrones pequeños en el mismo cuerpo grande de texto, también puede intentar implementar un suffix tree o un suffix array. Pero estos son en mi humilde opinión algo más difíciles de comprender e implementar correctamente.

Pero ten cuidado, estas técnicas son muy rápidas, pero solo te dan una aceleración apreciable si las cadenas involucradas son muy grandes. Es posible que no vea una aceleración apreciable para cadenas de menos de 1.000 caracteres de longitud.

EDIT:

Si usted está buscando en el mismo texto una y otra vez (es decir, el valor de cs es siempre/a menudo las mismas llamadas de diámetro), obtendrá un gran aumento de velocidad mediante el uso de un trie de sufijo (Básicamente, un trie de sufijos). Debido a que su texto es tan pequeño como 100 o 200 caracteres, puede usar el método O (n^2) más simple para construir el trie y luego realizar múltiples búsquedas rápidas en él. Cada búsqueda requeriría solo 5 comparaciones en lugar de las 5 * 200 habituales.

Editar 2:

Como se ha mencionado por el comentario de CAF, el algoritmo de C strstr es implementaciones dependiente. glibc usa un algoritmo de tiempo lineal que debería ser más o menos tan rápido en la práctica como cualquiera de los métodos que he mencionado.Mientras que el método OP es asintóticamente más lento (O (N * m) en lugar de O (n)), es más rápido, probablemente debido al hecho de que tanto n como m (las longitudes del patrón y el texto) son muy pequeños y no tiene que hacer ninguno de los preprocesamientos largos en la versión glibc.

Answer 2

Su código puede acceder cs más allá de los límites de su asignación si cs tiene menos de 4 caracteres.

Una optimización común para la cadena de búsqueda es utilizar el algoritmo Boyer-Moore donde empezar a buscar en cs desde el extremo de lo que sería ct. Consulte la página vinculada para obtener una descripción completa del algoritmo.

Answer 3

Reducir el número de comparaciones aumentará la velocidad de la búsqueda. Mantenga una int en ejecución de la cadena y compárela con una int fija para el término de búsqueda. Si coincide compare el último carácter.

uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3]; 
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3]; 
int i = 0; 

do { 
    if (term == walk && ct[4] == cs[4]) { return i; } // or return cs or 1 
    walk = (walk << 8) | cs[4]; 
    cs += 1; 
    i += 1; 
} while (cs[4]); // assumes original cs was longer than ct 
// return failure 

Agregue cheques para un corto cs.

Editar:

Correcciones añadidas de los comentarios. Gracias.

Esto podría adoptarse fácilmente para usar valores de 64 bits. Puede almacenar cs [4] y ct [4] en variables locales en lugar de asumir que el compilador lo hará por usted. Puede agregar 4 a cs y ct antes del bucle y usar cs [0] y ct [0] en el bucle.

Answer 4

La interfaz de strstr impone algunas limitaciones que se pueden superar. Toma cadenas terminadas en nulo, y cualquier competidor que primero hace un "strlen" de su objetivo perderá. No requiere un argumento de "estado", por lo que los costos de configuración no se pueden amortizar en muchas llamadas con (por ejemplo) el mismo objetivo o patrón. Se espera que trabaje en una amplia gama de entradas, incluidos objetivos/patrones muy cortos, y datos patológicos (considere buscar "ABABAC" en una cadena de "ABABABABAB ... C"). libc ahora también depende de la plataforma. En el mundo x86-64, SSE2 tiene siete años, y strlen y strchr de libc usando SSE2 son 6-8 veces más rápidos que los algoritmos ingenuos. En las plataformas Intel que admiten SSE4.2, strstr usa la instrucción PCMPESTRI. Pero puedes vencer eso, también.

Boyer-Moore's (y Turbo B-M, y Oracle Backward Matching, et al) tienen un tiempo de configuración que prácticamente los anula, incluso sin contar el problema de cadena terminada en nulo. Horspool es un B-M restringido que funciona bien en la práctica, pero no funciona bien en los bordes. Lo mejor que he encontrado en ese campo es BNDM ("Concordancia no determinista hacia atrás-Aciclic-Word-Graph Matching"), cuya implementación es más pequeña que su nombre :-)

Aquí hay un par de fragmentos de código que podrían ser de interesar. Intelligent SSE2 beats naive SSE4.2, y maneja el problema de terminación nula. A BNDM implementation muestra una forma de mantener los costos de configuración. Si está familiarizado con Horspool, notará la similitud, excepto que BNDM usa máscaras de bits en lugar de omisiones. Estoy a punto de publicar cómo resolver el problema del terminador nulo (de manera eficiente) para algoritmos de sufijo como Horspool y BNDM.

Un atributo común de todas las buenas soluciones es la división en diferentes algoritmos para diferentes longitudes de argumento. Un ejemplo de Sanmayce es "Railgun" function.

Answer 5

No superará una buena implementación en una computadora x86 moderna.

procesadores

Nueva Intel tienen una instrucción que lleva 16 bytes de la cadena que se está examinando, hasta 16 bytes de la cadena de búsqueda, y en un solo rendimientos de instrucciones que es la primera posición de byte en la cadena de búsqueda podría ser (o si no hay ninguno). Por ejemplo, si busca "Hola" en la cadena "abcdefghijklmnHexyz", la primera instrucción indicará que la cadena "Hola" podría comenzar en el desplazamiento 14 (porque al leer 16 bytes, el procesador tiene los bytes H, e, desconocido que podría ser la ubicación de "Hola". La siguiente instrucción que comienza en el desplazamiento 14 indica que la cadena no está allí. Y sí, sabe acerca de cero bytes finales.

Eso es dos instrucciones para encontrar que una cadena de cinco caracteres no está presente en una cadena de 19 caracteres. Intenta superarlo con cualquier código de caso especial. (Obviamente, esto está específicamente diseñado para strstr, strcmp e instrucciones similares).