Optimiser un algorithme de recherche en C

Question

Les performances de cet algorithme de recherche séquentielle (tiré deLa pratique de la programmation) être amélioré à l'aide de l'un des utilitaires natifs de C, par ex.si je définis la variable i comme variable de registre ?

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

Oui, mais seulement très légèrement.Une amélioration bien plus importante des performances peut être obtenue en utilisant de meilleurs algorithmes (par exemple en gardant la liste triée et en effectuant une recherche binaire).

En général, l’optimisation d’un algorithme donné ne vous mène pas loin.Choisir un meilleur algorithme (même s'il n'est pas complètement optimisé) peut vous apporter une amélioration considérable (de l'ordre de grandeur) des performances.

Answer 2

Je pense que cela ne fera pas beaucoup de différence.Le compilateur l'optimisera déjà dans ce sens.

De plus, la variable i n'a pas beaucoup d'impact, le mot reste constant tout au long de la fonction et le reste est trop volumineux pour tenir dans n'importe quel registre.La seule question est de savoir quelle est la taille du cache et si l'ensemble du tableau peut y tenir.

Les comparaisons de chaînes sont plutôt coûteuses en termes de calcul.

Pouvez-vous peut-être utiliser une sorte de hachage pour le tableau avant de rechercher ?

Answer 3

Il existe une technique bien connue comme méthode sentinelle.Pour utiliser la méthode sentinal, vous devez connaître la longueur de "array[]".Vous pouvez supprimer la comparaison "array[i] != NULL" en utilisant 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 vous lisez TPOP, vous verrez ensuite comment ils rendent cette recherche plusieurs fois plus rapide avec différentes structures de données et algorithmes.

Mais vous pouvez rendre les choses un peu plus rapides en remplaçant des éléments comme

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

avec

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

S'il y a une valeur connue à la fin du tableau (par ex.NULL), vous pouvez éliminer le compteur de boucles :

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

Bonne chance, c'est un super livre !

Answer 5

Pour optimiser ce code, le mieux serait de réécrire la routine strcmp puisque vous vérifiez uniquement l'égalité et n'avez pas besoin d'évaluer le mot entier.

A part ça, vous ne pouvez pas faire grand chose d'autre.Vous ne pouvez pas trier car il semble que vous recherchez du texte dans un texte plus grand.La recherche binaire ne fonctionnera pas non plus car il est peu probable que le texte soit trié.

Mon 2p (C-psuedocode) :

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

Marc Harrison :Votre boucle for ne se terminera jamais !(++p est en retrait, mais n'est pas réellement dans le for :-)

De plus, le basculement entre les pointeurs et l'indexation n'aura généralement aucun effet sur les performances, pas plus que l'ajout de mots-clés de registre (comme mat le mentionne déjà) - le compilateur est suffisamment intelligent pour appliquer ces transformations le cas échéant, et si vous lui en dites suffisamment sur l'architecture de votre processeur. , il fera un meilleur travail que les pseudo-micro-optimisations manuelles.

Answer 7

Un moyen plus rapide de faire correspondre les chaînes serait de les stocker dans le style Pascal.Si vous n'avez pas besoin de plus de 255 caractères par chaîne, stockez-les à peu près comme ceci, avec le nombre dans le premier octet :

char s[] = "\x05Hello";

Ensuite vous pouvez faire :

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;
    }
}

Et pour aller très vite, ajoutez des indices de prélecture de mémoire pour le début de chaîne + 64, + 128 et le début de la chaîne suivante.Mais c'est juste fou.:-)

Answer 8

Un autre moyen rapide de le faire est de demander à votre compilateur d'utiliser un memcmp optimisé pour SSE2.Utilisez des tableaux de caractères de longueur fixe et alignez-les pour que la chaîne commence sur un alignement de 64 octets.Ensuite, je pense que vous pouvez obtenir les bonnes fonctions memcmp si vous transmettez const char match[64] au lieu de const char *match dans la fonction, ou strncpy match dans un tableau de 64 128 256 octets, quel que soit le tableau.

En y réfléchissant un peu plus, ces fonctions de correspondance SSE2 pourraient faire partie de packages tels que les bibliothèques d'accélérateurs d'Intel et d'AMD.Vérifie-les.

Answer 9

En réalité, définir I comme variable de registre ne fera rien que le compilateur ne ferait déjà.

Si vous êtes prêt à consacrer du temps au prétraitement du tableau de référence, vous devez rechercher sur Google "Le programme de Scrabble le plus rapide au monde" et l'implémenter.Divulgacher:c'est un DAG optimisé pour la recherche de personnages.

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;
}