Optimización de un algoritmo de búsqueda en C

Question

¿Puede el rendimiento de este algoritmo de búsqueda secuencial (tomado deLa práctica de la programación) se puede mejorar utilizando cualquiera de las utilidades nativas de C, p.¿Si configuro la variable i para que sea una variable de registro?

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

Answer 1

Sí, pero sólo muy ligeramente.Se puede lograr una mejora de rendimiento mucho mayor utilizando mejores algoritmos (por ejemplo, manteniendo la lista ordenada y realizando una búsqueda binaria).

En general, optimizar un algoritmo determinado sólo te lleva hasta cierto punto.Elegir un algoritmo mejor (incluso si no está completamente optimizado) puede brindarle una mejora considerable (de orden de magnitud) en el rendimiento.

Answer 2

Creo que no hará mucha diferencia.El compilador ya lo optimizará en esa dirección.

Además, la variable i no tiene mucho impacto, la palabra permanece constante a lo largo de la función y el resto es demasiado grande para caber en ningún registro.Sólo es cuestión de qué tan grande sea el caché y si toda la matriz cabe allí.

Las comparaciones de cadenas son bastante costosas desde el punto de vista computacional.

¿Quizás puedas usar algún tipo de hash para la matriz antes de buscar?

Answer 3

Existe una técnica bien conocida como método centinela.Para utilizar el método sentinal, debe conocer la longitud de "matriz []".Puede eliminar "array[i]! = NULL" comparando usando sentinal.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

Answer 4

Si estás leyendo TPOP, verás a continuación cómo hacen que esta búsqueda sea mucho más rápida con diferentes estructuras de datos y algoritmos.

Pero puedes hacer las cosas un poco más rápidas reemplazando cosas como

for (i = 0; i < n; ++i)
    foo(a[i]);

con

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

Si hay un valor conocido al final de la matriz (p. ej.NULL) puedes eliminar el contador de bucle:

for (p = a; *p != NULL; ++p)
    foo(*p)

¡Buena suerte, es un gran libro!

Answer 5

Para optimizar ese código, la mejor opción sería reescribir la rutina strcmp ya que solo está verificando la igualdad y no necesita evaluar la palabra completa.

Aparte de eso, no puedes hacer mucho más.No puedes ordenar porque parece que estás buscando texto dentro de un texto más grande.La búsqueda binaria tampoco funcionará ya que es poco probable que el texto esté ordenado.

Mi 2p (psuedocódigo C):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

Answer 6

Marcos Harrison:¡Tu bucle for nunca terminará!(++p tiene sangría, pero en realidad no está dentro del for :-)

Además, cambiar entre punteros e indexación generalmente no tendrá ningún efecto en el rendimiento, ni tampoco agregar palabras clave de registro (como ya menciona mat): el compilador es lo suficientemente inteligente como para aplicar estas transformaciones cuando corresponda, y si le informa lo suficiente sobre el arco de su CPU , hará un mejor trabajo que las psuedomicrooptimizaciones manuales.

Answer 7

Una forma más rápida de hacer coincidir cadenas sería almacenarlas al estilo Pascal.Si no necesita más de 255 caracteres por cadena, guárdelos más o menos así, con el recuento en el primer byte:

char s[] = "\x05Hello";

Entonces puedes hacer:

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

Y para ser realmente rápido, agregue sugerencias de captación previa de memoria para el inicio de la cadena + 64, + 128 y el inicio de la siguiente cadena.Pero eso es una locura.:-)

Answer 8

Otra forma rápida de hacerlo es hacer que su compilador utilice un memcmp optimizado para SSE2.Utilice matrices de caracteres de longitud fija y alinee de modo que la cadena comience con una alineación de 64 bytes.Entonces creo que puede obtener buenas funciones memcmp si pasa const char match[64] en lugar de const char *match a la función, o strncpy match a una matriz de 64,128,256, cualquier matriz de bytes.

Pensando un poco más en esto, estas funciones de coincidencia SSE2 podrían ser parte de paquetes como las bibliotecas de aceleradores de Intel y AMD.Échales un vistazo.

Answer 9

De manera realista, configurar I como una variable de registro no hará nada que el compilador no haría ya.

Si está dispuesto a dedicar algo de tiempo a preprocesar la matriz de referencia, debe buscar en Google "El programa de Scrabble más rápido del mundo" e implementarlo.Revelación:es un DAG optimizado para búsquedas de personajes.

Answer 10

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}