distance Levenshtein (ou Damerau-Levenshtein, si possible!) Est

J'ai un programme dans lequel j'ai besoin de calculer plusieurs fois la distance de Levenshtein entre les paires de mots (l'un d'entre eux est fixe), et plusieurs fois peuvent aller de 1000 à 120000 pour chaque mot fixe. Puisque je veux optimiser ce programme autant que possible, j'ai pensé à implémenter ces calculs dans l'assemblage. Le problème est que je ne sais rien à propos de l'assemblage, sauf pour la théorie et que cela peut représenter de grandes améliorations de la vitesse. Quelqu'un peut-il m'aider s'il vous plaît ou me fournir le code d'assemblage pour cette distance? Aussi, comment puis-je appeler l'assembly à partir d'un module C#?distance Levenshtein (ou Damerau-Levenshtein, si possible!) Est

Source

2010-11-07 Miguel

Un compilateur bonne C peut produire des performances proches de celle de l'assemblage. De plus, vous pouvez lui demander de produire le fichier d'assemblage intermédiaire pour inspecter et détecter les inefficacités grossières (généralement causées par la peur des alias du compilateur: vous pouvez ensuite les corriger au niveau C en copiant certaines variables globales dans des variables locales auxquelles il est clair il n'y a pas d'alias). –

Peut-être que vous devriez d'abord implémenter ceci en C# (ou utiliser une bibliothèque C#) avant d'apprendre le langage assembleur. Après tout, le code C# peut être assez rapide pour vos besoins. –

Etant donné que vous ne connaissez pas l'assemblage, ce n'est probablement pas le meilleur choix, car l'optimisation du code d'assemblage nécessite une bonne connaissance de l'assemblage et du matériel en question. –

Vous pouvez facilement utiliser un BK-tree pour créer un arbre de recherche si Levenshtein est suffisant. Damarau-Levenshtein can not be used with a metric tree.

Vous n'avez pas besoin d'écrire cette implémentation en assembleur ou C#, vous pouvez aller loin en utilisant du code et des pointeurs non sécurisés.

Lire et cache str.Length, ce sont des invocations de méthode (très probablement inline/optimisé)
Accédez à vos chaînes avec des pointeurs.
fixed(char* ptrX=strX, ptrY=strY) ...
Vous pouvez créer votre table/tableau/état en int [rows * cols] au lieu de int [rows] [cols] et utiliser des pointeurs pour lire/écrire.
int[] state = new int[rows*cols]
fixed(int* ptrState=state)
Vous avez vraiment pas besoin de plus de deux lignes dans votre table d'état, vous avez celui que vous lisez à partir, et celui que vous écrivez. Puis échangez les pointeurs et lisez ce que vous venez d'écrire.
Je crois que vous pouvez optimiser en supprimant des préfixes identiques/suffixes
L('catz', 'cats') == L('z', 's') == 1
L('rats', 'cats') == L('r', 'c') == 1

Source

2010-11-07 19:47:55 sisve

distance Levenshtein (ou Damerau-Levenshtein, si possible!) Est

Répondre

Questions connexes