J'ai voulu faire une fonction de recherche des anagrammes pour un mot donné en entrée. J'ai utilisé pour cela plusieurs méthodes afin de comparer les résultats. Mon but était de générer uniquement les anagrammes qui sont des mots du dictionnaire. J'ai pour cela récupérer un fichier texte contenant tous les mots de la langue française, quelques 336 531 lignes et donc autant de mots.
Je vous propose ici les résultats avec 6 méthodes différentes basées sur le même algorithme de départ. (vous pouvez en retrouver sur le site du zéro).
La première méthode consiste à rechercher tous les anagrammes d'un mot et de comparer les résultats avec le fichier dictionnaire.
Pour la deuxième méthode, j'ai découpé le fichier dictionnaire en 26 parties, chaque partie contenant les mots commençant par une lettre différente. Ainsi le nombre de fichier lu sera égal aux nombres de lettres distinctes dans le mot, ce qui réduit le nombre de mot à comparer.
J'ai ensuite repris ces deux méthodes en stockant les fichiers de dictionnaire en RAM(tmpfs).
Pour les deux dernières méthodes, j'ai voulu testé les performances avec une base NoSQL: mongodb.
La 5ème méthode c'est donc: une table mongodb avec tous les mots.
La 6ème méthode comporte 26 tables mongodb.
Voici les résultats qui sont assez surprenants:
Entrer le mot a anagrammer:lucie
Resultats pour:
Algo initial:['celui\r\n']
8.78637504578sec
Algo initial+optimisation: ['celui\r\n']
2.28806495667sec
Algo initial+fichier en ram:['celui\r\n']
8.73582601547sec
Algo initial+optimisation+fichier en ram: ['celui\r\n']
2.32720899582sec
Utilisation mongodb: [u'celui']
50.171544075sec
Utilisation mongodb+optimisation: [u'celui']
9.79022812843sec
J'ai donc voulu anagrammer le mot "lucie". Comme vous le voyez le stockage du fichier en ram n'apporte pas une réelle amélioration. Quand à mongodb, c'est plutôt décevant. La lecture en base est plus lente que la lecture d'un fichier texte. Il faudrait refaire le test en multi-threadé afin de pouvoir je pense obtenir de meilleurs résultats.
Les tests ont été réalisé sur Ubuntu 12.04 64bits en environnement virtualisé avec python 2.7 et pymongo 2.1.
Aucun commentaire:
Enregistrer un commentaire