Comme l'une des missions du cours CS50 de Harvard, les étudiants sont chargés de créer un programme de vérification orthographique. La poussée principale de la mission est une vitesse pure - et je me suis senti au point où je bat la mise en œuvre du personnel, mais je sens que je peux faire mieux et je cherche une poussée dans la bonne direction. Voici mon pseudocode: P>
Unique Misspellings: 6960 Total Misspellings: 17845 Words in dictionary: 143091 Words in input text: 1150970 Total Time: 0.56 seconds Unique Misspellings: 8348 Total Misspellings: 45691 Words in dictionary: 143091 Words in input text: 904612 Total Time: 0.83 seconds
3 Réponses :
C'est un problème assez résolu. ;-) Vous devriez examiner une structure de données appelée Trie . Une trie est un arbre construit de caractères individuels, de sorte que le chemin représente les informations. Chaque nœud est composé de lettres que vous pouvez légitimement ajouter au préfixe actuel. Lorsqu'une lettre est un mot valide, qui est également enregistré. pour quatre mots: Cela représenterait "Aardvark", "Aardvarks", "Abaci", "Abaci", et "Abacus". Les nœuds sont contiguës verticalement, donc 2ème lettre [AB] est un nœud, et la 5ème lettre [i * u] est un nœud. traverser le caractère trempoté par caractère et vérifiez un mot valide lorsque vous Hit de l'espace. Si vous ne pouvez pas traverser le personnage que vous avez, alors c'est un mauvais mot. Si vous ne trouvez pas valide lorsque vous touchez de l'espace, c'est un mauvais mot. Ceci est O (n) à traiter (n = longueur de mot) et c'est très très rapide. Construire la trie va consommer un bouquet de RAM, mais vous ne vous souciez pas de cela, je pense.
Merci pour la note, Austin. J'avais considéré une trie au lieu d'une table de hachage, mais je ne suis pas convaincu que cela fournirait une amélioration de la vitesse. Je suis proche de O (1), et je me déplace dans une trie serait une étape dans la mauvaise direction, à moins que je ne manque quelque chose de fondamental sur votre suggestion. Je vais aller de l'avant et mettre en œuvre une trie de toute façon et poster les résultats dans un peu. J'espère éviter les essais et les erreurs, mais depuis que j'apprends, ce sont les pauses. :-)
Hachage un mot est o (len) sur le mot. Trie Traverse est également O (Len). C'est un scénario de pommes / pommes.
@Drew: O (1) peut être rapide ou peut être horriblement lent. Ce qui compte est le facteur constant. (Modifiez votre instructeur à ce sujet - je suis surpris de voir combien de kiddes sortent d'école pensant qu'ils peuvent neiger les gens avec Big-o.) J'ai tendance à être d'accord avec Austin's Trie, car s'il n'y a que 50 000 mots dans le dictionnaire, la trie ne devient pas très profond. De plus, vous pouvez l'utiliser pour Correction d'orthographe . En outre, je parie qu'il y a une autre astuce qu'ils ne vous disent pas - vous pouvez précompiler le dictionnaire dans le code. Cela vous donnera une vitesse massive.
@Mikedunlavey merci pour votre réponse. Le défi de chacun des points que vous faites (et qu'ils sont valides) est que je n'ai absolument aucune idée à l'avance sur quel dictionnaire ils me jetteront. Donc, ils peuvent me donner un dictionnaire avec 10 mots ou 500 000 entre les courses. Sinon, vous prenez certainement les 30 à 40 secondes pour pré-traiter et persister une table de hachage parfaite. Ce serait génial! Mais ils sont sur ce tour. ;-)
Dans vos deux essais, ce qui est notable, c'est que la majorité des mots sont correctement orthographiés. Par conséquent, vous devriez vous concentrer sur l'optimisation de la recherche de mots qui sont dans le dictionnaire.
Dans votre premier essai, par exemple, seulement 1,5% de tous les mots sont mal orthographiés. Supposons que cela prend deux fois plus longtemps en moyenne pour rechercher un mot qui n'est pas dans le dictionnaire (car chaque mot dans le seau doit être vérifié). Même si vous avez réduit cela à 0 (le minimum théorique :)), vous accéléreriez votre programme de moins de 3%.
Une optimisation de la hache commune consiste à déplacer la clé que vous trouvez au début de la chaîne du godet, si ce n'est pas déjà là. Cela aura tendance à réduire le nombre d'entrées de hachage vérifiées pour des mots couramment utilisés. Ce n'est pas une énorme accélération, mais dans les cas où certaines touches sont levées beaucoup plus souvent que d'autres, il peut certainement être remarqué.
Réduire la longueur de la chaîne en diminuant l'occupation de la hache peut aider davantage, au coût de la mémoire plus.
Une autre possibilité, puisque vous n'allez pas modifier le dictionnaire une fois qu'il est construit, est de stocker chaque chaîne de godet dans la mémoire contiguë, sans pointeur. Non seulement cela réduira la consommation de mémoire, il améliorera les performances du cache car, car la plupart des mots sont courts, la plupart des godets s'intégreront dans une seule ligne de cache.
Et puisque les mots ont tendance à être assez courts, vous pourrez peut-être pouvoir trouver un moyen d'optimiser la comparaison. Cela ne veut pas dire que les hashtables sont nécessairement la source de données optimale pour ce problème. Mais rappelez-vous que plus vous pouvez faire dans une seule ligne de cache, le programme plus rapide sera exécuté. Les données de données à forte intensité liées peuvent se révéler sous-optimal même si elles ont l'air bien sur papier.
Après avoir réfléchi à ce problème pendant quelques jours et écrire en réalité un code, je suis arrivé à la conclusion que l'optimisation de la vitesse de recherche de hashtable réussie n'est probablement pas correcte pour un Volworld Spellchecker . Il est vrai que la plupart des mots dans le texte recherché sont généralement correctement orthographiés - bien que cela dépend de l'utilisateur de la vérification orthographique - mais l'algorithme qui tente de suggérer des orthographes corrects, est susceptible de faire beaucoup de recherches infructueuses lors de la cycles d'armes orthographiques possibles. . Je sais que c'est probablement hors de portée de ce problème, mais cela fait une différence d'optimisation, car vous vous retrouvez avec deux stratégies très différentes.
Si vous essayez de rejeter rapidement, vous avez besoin de beaucoup de chaînes de seau vides, ou d'un filtre de floraison ou de son équivalent moral, vous pouvez donc rejeter la plupart des erreurs sur la première sonde.
Par exemple, si vous avez un bon algorithme de hachage qui donne plus de bits que vous en avez besoin - et vous le faites presque certainement, car les dictionnaires de vérification orthographique ne sont pas si gros - alors vous pouvez simplement utiliser des bits sinon inutilisés dans le hachage pour un hachage secondaire. Sans même aller avoir la peine de mettre en œuvre l'ensemble du filtre de floraison, vous pouvez simplement ajouter, dire, un masque 32 bits à chaque en-tête de godet représentant les valeurs possibles de cinq bits de hachage secondaires dans les valeurs stockées dans ce compartiment. Combiné à une table rare - J'ai utilisé 30% d'occupation pour l'expérience, ce qui n'est pas si rare - vous devriez être capable de rejeter 80-90% des défaillances de recherche sans aller au-delà de l'en-tête de seau.
D'autre part, si vous essayez d'optimiser le succès, il peut arriver que les seaux largish sont meilleurs, car il diminue sur le nombre d'en-têtes de seau et qui améliore l'utilisation du cache. Tant que l'ensemble du godet s'inscrit dans une ligne de cache, la vitesse de plusieurs comparaisons est si élevée que vous ne remarquerez pas la différence. (Et puisque les mots ont tendance à être courts, il est raisonnable de s'attendre à cinq ou six pour s'intégrer dans une coque de 64 octets.)
Quoi qu'il en soit, sans aller trop travailler, j'ai réussi à faire un million de recherches dans 70 millisecondes de CPU. Le multiprocession pourrait accélérer un temps écoulé un peu plus particulièrement car aucun verrouillage n'est requis étant donné que la table de hachage est immuable.
La morale que je veux dessiner à partir de ceci:
Afin d'optimiser:
Vous devez comprendre vos données
Vous devez comprendre votre modèle d'utilisation prévu
Vous devez adapter vos algorithmes en fonction de ce qui précède
Vous devez faire beaucoup d'expérimentation.
STRCMP () est bien optimisé mais il est généralement optimisé pour les cordes plus vastes. Si vous êtes autorisé à l'utiliser, l'opcode SSE4.2 PCMpetri est incroyablement puissant (mais déterminer ce qu'il fait et comment l'utiliser pour résoudre votre problème peut être un vast-shoot énorme). Plus simplement, vous devriez pouvoir comparer simultanément quatre préfixes de huit octets simultanément avec des opérations de comparaison de 256 bits (et vous pourriez même disposer d'opérations de 512 bits à votre disposition), donc avec une disposition de données intelligente, vous pourrez peut-être bien faire un Comparaison complète de godet en parallèle.
Merci pour votre réponse, Rici. J'aime l'idée de déplacer le lien "le plus courant" vers le front de la liste, même s'il ne fait que quelques itérations. L'occupation est moins problématique car j'utilise une très grande table avec moins de 2 000 collisions internes pour le dictionnaire de mots de 150 000 mots, même si je n'ai pas encore analysé chaque godet pour déterminer la manière dont les collisions sont réparties. (J'ai une table entière secondaire qui stocke des index de la table de hachage pour un nettoyage facile.) Je vais certainement regarder PCMpetri et j'apprécie la suggestion.
PCMpetri est en réalité plus facile à mettre en œuvre dans l'ASM que dans C. C'est une première pour moi.
@ Greatw: Il y a des intrinsèques :) Si vous n'avez pas de collisions, il n'est probablement pas utile que plusieurs seaux se compare (mais vous éliminer les listes liées est toujours une bonne optimisation pour les dictionnaires). PCMpetri est également utile pour la mise en œuvre de choses semblables à Strtok. Mais c'est pas pain tranché. Profil et voir si cela aide vraiment.
Il est intéressant de noter que votre deuxième expérience prend beaucoup plus longtemps avec moins de recherches de mots. Les mots sont-ils plus longs? Ou, contrairement à ce que je suggère dans ma réponse, y a-t-il quelque chose qui ralentit énormément les recherches échouées?
Re: Temps de recherche plus long - Ceci est hébergé sur une IDE Nuage9 Ubuntu, de sorte que les courses de mi-journée sont douteuses. Je l'ai retourné à nouveau sur le même ensemble de données, et le résultat était: orthographe unique: 8348 mots orthographiés: 45691 mots dans le Dictionnaire: 143091 mots dans le texte: 904612 Temps en charge: 0.05 Temps de chèque: 0.45 Temps de taille: 0.00 Temps en déchargement: 0.03 Time au total: 0.53
La variation de ces horaires rend cette technique d'analyse comparative inutilisable. Il est possible que la majeure partie du temps soit la lecture du disque; Les techniques de référence standard permettraient d'obtenir des valeurs plus cohérentes (bien que pas nécessairement plus significatif). Faire l'expérience K fois (dans une boucle); rejeter les valeurs aberrantes et signaler la moyenne. De cette façon, vous aurez probablement le fichier d'entrée mis en cache dans les tampons de noyau après les premières itérations et les autres ne devront pas attendre des broches.
@Drew: Alors, comment ça s'est passé pour vous à la fin? Pour mon petit hack, j'ai utilisé un dictionnaire Ubuntu de 99,171 mots et un vieux corpus de newsfeed, j'ai eu des coups de pied. Je triche probablement en ne faisant pas une seconde recherche sur des mots avec des caractères majuscules, mais le résultat est de détecter beaucoup plus de défaillances. Quoi qu'il en soit, l'entrée est un peu plus de 6 Mo; Il a 968234 mots, dont 199845 ne figurant pas dans le dictionnaire; La construction du dictionnaire prend environ 25 millisecondes et la recherche du texte prend environ 70 millisecondes. (Ordinateur portable I5, 2,5 GHz, exécutable à fil unique.)
Hey @icii, merci de demander et de prendre le temps de l'essayer vous-même. J'ai été détourné sur le prochain projet (écrire un serveur Web semblable à Apache) que j'ai terminé cet après-midi. Maintenant, je retourne pour mettre un timbre sur le vérificateur orthographique. Je ne vérifie pas non plus les bouchons. Je triche en prenant le mot entrant et le bitwise ou 32 pour me donner tous les minuscules. Je vais avoir une réponse pour vous demain.
Je travaillerai aujourd'hui si vous voulez jeter un coup d'œil ... github.com/ganellon/spell_check < / a> Main est en orthographe.C mais selon les règles de l'affectation, ce fichier source peut ne pas être modifié. Tout mon code est dans Dictionary.c
J'ai regardé votre code. Je ne sais pas si cela comptait dans votre environnement, mais si vous utilisez des pointeurs 64 bits, vous pourriez obtenir une vitesse maximale de 1,2 million simplement en les coupant jusqu'à 32 bits. Essayez de remplacer les pointeurs sur les mots de votre dictionnaire avec des valeurs 32 bits -Erez-les près des pointeurs ou des entiers 32 bits offset à partir de l'adresse de base mem_dict adresse de base. (Il s'agit principalement d'améliorer les performances de cache en réduisant la taille des données.)
En outre, ne vous libérez pas mem_dict . Il suffit de souscrire dessus. Allocation de chaînes individuelles est pire, car malloc () et des amis arrondi à une taille de bloc même.
Enfin, envisagez d'abandonner mem_dict et de jeter la mémoire au problème. Si vous traitez les 4 ou 8 premiers octets de la saisie de la chaîne en tant que type entier, vous pouvez utiliser zéro-remplir le tampon TEMP et votre bloc de chaîne et les comparer en tant qu'étabeurs. si (* (int32_t *) temp == * (int32_t *) (TRAV-> clé)) {... Je pense que vous allez faire assez bien avec 32 bits et la majeure partie du commun Les mots sont moins de 64 bits de long, de sorte que vous pouvez coder la logique (puisque vous savez lenny ) pour ignorer le MEMCMP entièrement.
Enfin, enfin (vraiment!), Envisagez de convertir à Pascal Strings (mettre une longueur de 8 bits dans le premier caractère). Vous faites déjà ce travail et cela déclenche le plus tôt possible l'échec possible des mots de différentes longueurs.
@Drew: est le code d'analyse comparative dans l'orthographe.C une partie de ce que vous avez donné? Ma réaction immédiate était que c'était "tout simplement faux", mais je me suis installé "inexact"; Il essaie de mesurer les événements dont le temps de fonctionnement attendu est (au pire) des centaines de nanosecondes avec une minuterie de résolution microseconde. Évidemment, c'est inexact mais il y a une raison de croire que ce n'est pas aussi inexacte car si vous avez beaucoup d'événements, la minuterie va rouler à la valeur suivante à l'intérieur d'un événement avec une probabilité à peu près égale à le temps réel pris par l'événement.
@AustinHastings Merci beaucoup de jeter un coup d'œil! Je ne libérez pas de Mem_Dict jusqu'à ce que la table de hachage soit remplie et que vous n'avez aucune autre utilisation pour MEM_DICT. Je pensais que je pouvais simplement l'utiliser sans créer une table de hachage, mais j'aurai vraiment une recherche linéaire glorifiée. Est-ce ce que tu veux dire?
@ici Oui, tout ce qui est en orthographe.C est comme il est arrivé dans le cadre de la distribution. Les modifications apportées à Speller.c ne sont pas autorisées - et je peux deviner pourquoi dans certains endroits où j'aurais apporté des modifications.
@AustinHastings vient d'avoir un moment AH-HH en ce qui concerne le maintien de Mem_Dict en le déplaçant dans l'espace mondial et en utilisant ces adresses. Cela économisera certainement un peu de temps, plutôt que de MALLOC pour chaque nouveau nœud. Je vais toujours avoir à Malloc pour les nœuds de collision, mais il y a beaucoup moins lourd. Merci pour ce conseil.
@Drew: Il est clair qu'ils essaient de ne pas contaminer le calendrier de votre fonction de recherche avec, par exemple, le moment de la synchronisation de l'analyseur Word ou avec l'impression des mots mal orthographiés, si le printf est décalé. Mais le résultat est de contaminer la référence avec le coût d'appel de GetRusage. Sur mon système, GetRusage prend environ 220 NSEC; Une recherche de hachage raisonnable ne devrait pas prendre même 100 NSEC. Au moins 2/3 du temps comptabilisé est composé de Calling Greüsage.
@ici - vous pouvez voir pourquoi j'ai commenté cette ligne de Speller.c; Avoir toutes ces mal orthographiques de déversement à l'écran est absurde. Je l'ai commenté parce que je n'étais intéressé que par le résumé, mais ce n'est pas la version "officielle" que je devrai utiliser dans le produit final.
@AustinMastings Changement de nœud de la touche [45] à * Touche et mettez à jour les fonctions CreateNode et Addnode Réduisez la durée de la fonction de charge de 0,06 à 0,04 secondes. Ce sera toujours un taux cohérent basé sur la taille du dictionnaire, mais c'est une énorme économie! Grande suggestion.
@ Drew: Je suppose qu'ils vident les orthographies à STDOUT afin de vérifier que les mauvaises orthographies sont identifiées. Cependant, combiner une référence et une validation n'est pas toujours une bonne idée. Dans ce cas, je penserais que les deux devraient être séparés, auquel cas pourriez-vous entourer la boucle de recherche entière avec une seule paire de gobusage. Bien sûr, cela aurait pour effet d'inclure le coût de l'analyse, qui est également non trivial par rapport au coût de la recherche ...
... la façon dont je ferais qu'il serait d'abord de lire la totalité de l'entrée en mémoire, de l'analyser en mots et de valider les orthographies. Ensuite, je me répare de la saisie, en gardant une trace de combien de temps qui a pris. Ensuite, je me répare à nouveau de la saisie, mais cette fois-ci, gardez à nouveau la trace de l'heure. La différence entre les deux serait le coût de la recherche. Valider d'abord réchaufferait le cache afin que les deux autres boucles soient (plus) comparables.
Laissez-nous Continuez cette discussion en chat .
Quelques perspectives / idées que vous pourriez explorer:
où les valeurs sont similaires de longueur - ou peu plus grandes que les pointeurs - le hachage fermé vous donnera une meilleure performance que toute hachage ouverte AKA APPROCHE SÉPARATION
La longueur des mots en cours de vérification est une solution bon marché (peut-être si vous le suivez quand même), vous pouvez diriger des validations aux méthodes les plus optimales pour cette longueur de mot
Pour obtenir plus de mots sur moins de pages de mémoire (et ainsi être plus sympa de cache), vous pouvez essayer d'avoir plusieurs tables de hachage, où les godets sont dimensionnés à la longueur de texte la plus longue de celui-ci
Les godets de 4 octets et de 8 octets permettent de manière appropriée des comparaisons d'une valeur mono-instructions et 64 bits, si vous cotez les chaînes avec les nuls (c'est-à-dire que vous pouvez faire une union de Votre choix de la fonction de hachage est important: essayez quelques bons
Votre choix de stratégie de manutention de collision est également important: profil avec linéaire, quadratique et peut-être une liste de nombres premiers (1, 3, 7, 11 ...).
Le nombre de godets est un acte d'équilibrage: trop peu et vous avez trop de collisions, trop de godets et vous avez plus de cache de mémoire, alors testez avec une gamme de valeurs pour trouver les paramètres optimaux
Vous pouvez profiler à l'aide d'un nombre maximum de godets de collision-orversion avec Beaucoup de l'interaction ci-dessus: par exemple. Si vous utilisez une fonction de hachage forte, vous avez moins de besoin d'un nombre premier de godets; Si vous avez moins de collisions, vous avez moins de besoin d'une commande de recherche post-collision élaborée à travers des godets alternatifs
La vérification orthographique est très facile à accabler avec des threads, car vous faites des recherches de table de hachage en lecture seule; L'insertion préalable du dictionnaire dans la ou les tableaux de hachage (s) - moins, bien que l'utilisation de plusieurs tables telles que ci-dessus offre une façon de paralliser
uint32_t et Char [4] ou uint64_t et Char [8] et comparez les valeurs d'entier).
%% Valeurs de hachage de pliage dans la plage d'index du godet contre une puissance de deux comptes de godets où vous pouvez utiliser plus vite < Code> & Bitmasking
Le problème avec l'idée de mise en cache: vous accélérerez le traitement des mots qui se produisent dans le cache, mais ralentissez le traitement des mots non dans le cache. Ainsi, par exemple, si les mots mal orthographiés sont mis dans un cache, vous ferez accélérer le traitement d'environ 5 000 mots, mais ralentirez le traitement d'environ 1,14 million de mots. C'est un mauvais compromis. Je vais donc sauter l'idée de la mise en cache et travailler à l'obtention de toutes les conviences de hachage de 8 cœurs.
Si vous ne trouvez pas ce que vous recherchez ici, essayez l'examen de code.
Avez-vous profilé votre code?
Étant donné que vous avez un nombre important d'orthographes répétées, avez-vous envisagé d'ajouter les orthographies au hasch? Si vous stockez le résultat vrai / faux de la recherche et insérez des mots mauvais au début des chaînes de hachage, vous pourriez obtenir des performances.
@Paulhankin - En quelque sorte, à l'aide de GetRusage et de struct de rusage entre les appels vers chaque fonction, où le chargement du dictionnaire dans la mémoire, la vérification des mots entrants contre la table de hachage et la libération du tas est chronométrée individuellement, ainsi que la valorisation globale afin de garantir que tout est nettoyé.
@AustinMastings Ajout des orthographes / les marquer "Bad 'au hasch nécessiterait une modification de la structure de liaison de chaîne et nécessite un chèque supplémentaire au-delà de la hausse -> Valeur -> Chèques de clé que je fais déjà. Je vais devoir penser Sur cela. Bonne suggestion cependant. Je vais l'essayer.
Vous pouvez ajouter un octet supplémentaire au mot et le stocker au-delà de la fuite '\ 0'.