Rapide comparaison de chaînes de caractères en C

J'ai actuellement ce genre de boucle

while(1)
{
    generate_string(&buffer);

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

J'ai un fichier avec quelques millions de chaînes de caractères(qui, espérons-le, devrait être réduit de moitié prochainement), le nombre de toutes ces chaînes sont stockées dans filelines

ligne[i] est fondamentalement où la chaîne est stockée.

Actuellement, en raison de la comparaison de ces millions de chaînes de caractères, la fonction generate_string(&buffer); est exécuté environ 42 fois par seconde.
Est-il un moyen plus rapide de faire de comparaison de chaînes de caractères en C?

Si vous pouvez trier les lignes, c'est sûr.
Si vous pouvez hachage, hash.
non, parce que la vraie question ici n'est pas "comment faire pour comparer deux chaînes de caractères", c'est "comment tester une chaîne de confinement dans un grand ensemble de cordes".
Seulement si les chaînes tailles sont les mêmes, vous pourriez faire si((buffer[0] == ligne[0]) && (tampon[1] = = [1]) && ...). Qui est plus rapide que d'appeler strcmp().
J'ai juste couru un profil sur wakkerbot: il utilise 200ms à faire 2M recherches dans une 500K dictionnaire de mots connus. Une dernière strcmp() à la mise en correspondance table de hachage entrée.

OriginalL'auteur farmdve | 2012-05-23

  1. 11

    strcmp est généralement optimisé par tous les fournisseurs. Toutefois, si vous n'êtes pas satisfait avec ce que vous pouvez essayer:

    • De recherche Rafale Tente
    • Utiliser un suffixe de l'arbre pour une rapide comparaison de chaînes de caractères -- voir cette article
    • En fonction de la taille des chaînes dans votre application, vous pouvez écrire une chaîne personnalisée comparateur. E. g: GNU libc l'habitude d'avoir cette optimisation pour les petites chaînes où ils ont testé des chaînes plus petites que les cinq octets comme des nombres entiers. MS cl a aussi quelques optimisations pour les petites chaînes (ne chercher).

    Mais plus important encore, assurez-vous que strcmp est votre réel goulot d'étranglement.

    Oui, strcmp est le goulot d'étranglement. Retrait de la strcmp appel, la fonction est exucted plus d'un millier de fois par seconde, même 1100 dans certains cas.
    Votre "voir cet article" le lien n'est plus liée à un article, mais juste le prof de la page d'accueil.

    OriginalL'auteur dirkgently

  2. 5

    Je peux vous assurer, la fonction strcmp est ABSOLUMENT PAS le goulot d'étranglement. Généralement, strcmp est bien optimisé et peut faire 32 ou 64 bits comparaisons de chaînes de plus de 4/8 octets en fonction de l'architecture. Les deux newlib et de la GNU libc ce faire. Mais même si vous avez été à regarder chaque octet dans les deux chaînes de 20 fois, il n'a pas d'importance autant que l'algo & structure de données choix faits ici.

    Le véritable goulot de bouteille est en O(N) de l'algorithme de recherche. Un seul O(N log N) de passer au fichier peut être utilisé pour le cas échéant, la structure de données (si c'est une étape normale de la STB, un trie, ou juste un simple tableau trié) pour faire en O(log N) les recherches.

    Ours avec moi, ici, beaucoup de maths suit. Mais je pense que c'est une bonne occasion pour illustrer pourquoi le choix de l'algorithme & structure de données sont parfois BEAUCOUP plus importante que la méthode de comparaison de chaînes de caractères. Steve touche sur ce sujet, mais je voulais expliquer un peu plus en profondeur.

    Avec N=1e6, log(1e6, 2) = 19.9, si rond jusqu'à 20 comparaisons sur un idéal structure de données.

    Actuellement, vous êtes en train de faire un pire cas de recherche de O(N), ou 1e6 opérations.

    Donc dire que vous venez de construire un rouge-noir arbre avec O(log N) au moment de l'insertion, et vous insérez N éléments, c'est O(N log N) le temps de construire l'arbre. Donc, c'est 1e6 x 20 ou 20e6 opérations nécessaires pour construire votre arbre.

    Dans votre approche actuelle, la construction de la structure de données est O(N), ou 1e6 opérations, mais votre pire des cas le temps de recherche est O(N). Donc, le temps de le lire et de le faire juste 20 opérations de recherche, vous êtes à la hauteur théorique pire des cas de 21,000,000 opérations. Par comparaison, votre pire des cas avec un rouge-noir arbre et 20 recherches est 20,000,400 opérations, ou 999,600 opérations de MIEUX que O(N) de recherche sur un tableau non-trié. À 20 recherches, vous êtes au premier point où, en plus sophistiqué structure de données est vraiment rentable. Mais regardez ce qui se passe à 1000 recherches:

    Non triés array = initialisation + 1000 x temps de recherche = O(N) + 1000 * O(N) = 1 000 000 de + 2,000,000,000 = 2,001,000,000 opérations.

    Rouge-noir = initialisation + 1000 x temps de recherche = O(N log N) + 1000 * O(log N) = 20 000 000 de + de 20 000 = 20,020,000 opérations.

    2,001,000,000 /20,020,000 ~= 100x autant d'opérations pour le O(N) de recherche.

    À 1e6 recherches, c'est (1e6 + 1e6 * 1e6) /(20e6 + 1e6 * 20 ) = de 25 000 x comme de nombreuses opérations.

    Supposons que votre ordinateur peut gérer la 40e6 des 'opérations' il faut pour faire le journal N recherche en 1 minute. Il faudrait de 25 000 minutes, soit 17 JOURS pour faire le même travail avec votre algorithme actuel. Ou une autre façon de regarder est que le O(N) de l'algorithme de recherche ne peuvent gérer 39 recherches en temps O(log N) algorithme peut faire de 1 000 000. Et le plus de recherches que vous faites, le plus laid qu'il obtient.

    Voir les réponses de Steve et dirkgently pour plusieurs de meilleurs choix de structures de données & algorithmes. Ma seule précaution supplémentaire serait que qsort() proposé par Steve pourrait ont le pire des cas, la complexité de O(N*N), ce qui est loin, loin, pire que le O(N log N), on obtient avec un heapsort ou diverses structures arborescentes.

    OriginalL'auteur Brian McFarland

  3. 4

    L'optimisation des Programmes d'Ordinateur en C

    Vous pouvez économiser un peu de temps en cochant le ou les premiers caractères des chaînes en question avant de faire l'appel. Évidemment, si les premiers caractères différents, il n'y a aucune raison de l'appeler strcmp pour vérifier le reste. En raison de la non-homogénéité de la distribution des lettres dans les langues naturelles, le paiement n'est pas 26:1, mais plus comme 15:1 pour la majuscule de données.

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

    Si Le dictionnaire de mots que vous utilisez sont bien définis (ce qui signifie que vous n'avez pas l'esprit la valeur de retour de formulaire strcmp mais 0=égal (=), par exemple, un ensemble d'arguments de ligne de commande qui commence avec le même préfixe, ex: tcp-accepter, tcp-rejeter que vous pouvez réécrire la macro, et faire de l'arithmétique des pointeurs de comparer non pas le 1er mais le Nième char, dans ce cas, la 4ème char, ex:

       #define QUICKIE_STRCMP(a, b, offset) \
            (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))
    Je doute vraiment que la macro en comparant les premiers caractères donne de meilleurs résultats pour les compilateurs modernes et les bibliothèques.

    OriginalL'auteur user2402133

  4. 2

    Si je reçois votre question correctement, vous devez vérifier si une chaîne est le long de toutes les lignes de lu jusqu'à présent. Je propose à l'aide d'un TRIE ou encore mieux, un Patricia arbre de l'lignes du fichier. De cette façon, au lieu d'aller tous les plus de toutes les lignes que vous pouvez vérifier de façon linéaire si votre chaîne est présente(et avec un peu plus d'effort - où).

    OriginalL'auteur Ivaylo Strandjev

  5. 1

    Vous êtes déjà de la compilation avec l'optimisation, à droite?

    Si vous avez un Trie ou de la table de hachage des données de structure située autour de la place, prêt à l'emploi, alors vous devriez.

    À défaut, assez facile, changement qui va probablement accélérer les choses est de trier votre tableau line une fois, avant de vous commencer à générer des chaînes de caractères à rechercher. Le binaire de recherche pour buffer dans le tableau trié. C'est facile, car les deux fonctions dont vous avez besoin sont la norme - qsort et bsearch.

    Une recherche binaire dans un tableau trié seulement besoin de faire sur les journaux2(filelines) les comparaisons de chaînes, au lieu de la filelines. Si dans votre cas, c'est 20-quelque chose de comparaisons de chaînes par appel à generate_string au lieu de quelques millions de dollars. Les chiffres que vous avez donnés, je pense que vous pouvez raisonnablement attendre d'elle pour aller de 20 à 25 fois plus rapide, bien que je promets rien.

    La fonction qsort() pourrait être un quicksort comme son nom l'indique, qui est O(N*N) le pire des cas, la performance. À moins que j'ai été certain que la façon dont qsort() se comporte sur la plate-forme cible, j'irais avec le ralentissement de la moyenne, mais beaucoup plus rapide sur le pire des cas hepasort ou smoothsort.
    Si vous le préférez. Comme je l'ai dit, l'avantage de qsort est que c'est la norme. Si je dois faire le travail moi-même alors je serais probablement plutôt écrire une table de hachage qu'un heapsort, pour être honnête 🙂 de toute façon, ce n'est pas tout à fait clair si le temps de démarrage de l'importance à tous, en comparaison avec le nombre de chaînes de caractères générées par seconde une fois que nous sommes en place. Si le temps de démarrage n'a pas vraiment d'importance, qsort mis en œuvre comme une bulle de tri serait absolument parfait!
    Avéré de l'algorithme de tri est probablement plus difficile à vis de celle d'une fonction de hachage, et une mauvaise fonction de hachage vous met dos au pire des cas en O(N) le temps de recherche.
    djbhash est assez bon pour moi, mais c'est vrai que les tables de hachage ont aussi catastrophique pour le pire des cas la performance. Une analyse est en ordre, si la liste des chaînes dans lines peut être malicieusement construit comme un quicksort - et/ou de hachage-killer. Si vous êtes inquiet à propos de ce genre de chose, alors vous avez à décider d'écrire vos propres algorithmes, ou juste pour ramasser une bibliothèque standard dont qsort est résistant.

    OriginalL'auteur Steve Jessop

  6. 0

    Je ne sais pas qu'il y a un moyen plus rapide que d'appeler strcmp de faire des comparaisons de chaînes, mais vous pouvez peut-être éviter appel strcmp tellement. Utiliser une table de hachage pour stocker vos chaînes et vous pouvez ensuite vérifier si la chaîne en buffer est dans la table de hachage. Si l'indice d'un coup, est important quand vous "faire quelque chose", la table la carte des chaînes à l'index.

    OriginalL'auteur Ted Hopp

  7. 0

    Vous pouvez essayer quelque chose de "pas cher", comme le dépistage basé sur le premier char. Si les premiers caractères ne correspondent pas, les chaînes ne peuvent pas être égaux. Si elles correspondent, puis d'appeler strcmp pour comparer l'ensemble de la chaîne. Vous pouvez envisager un meilleur algorithme, si c'est approprié pour votre situation; les exemples seraient trier le fichier/lignes et de faire une recherche binaire, en utilisant une table de hachage, ou similaire table de chaîne techniques.

    OriginalL'auteur Art Swri

  8. 0

    vous pourriez être en mesure de s'en sortir avec une comparaison binaire dans ce cas, parce que votre programme n'a pas fait sorte, mais compare pour l'égalité.

    vous pouvez également améliorer la comparaison des vitesses d'ici par la détermination de la longueur à l'avance (à condition bien sûr qu'ils varient assez). lorsque la longueur ne correspond pas ici, do something ne se fera pas.

    bien sûr, le hachage ici serait une autre considération en fonction du nombre de fois que vous lisez la valeur de hachage.

    OriginalL'auteur justin