J'essaie d'exécuter une simulation pour tester la moyenne distance de Levenshtein entre aléatoire Cordes binaires.
Mon programme est en Python mais j'utilise ce C Extension . La fonction qui est pertinente et prend la majeure partie du temps calcule la distance de Levenshtein entre deux chaînes et est-ce. P> peut-il être accéléré? P> Je vais exécuter le code dans 32 bits Ubuntu sur un processeur AMD FX (TM) -8350 Huit-Core. P> Voici le code Python qui l'appelle. P> from Levenshtein import distance
import random
for i in xrange(16):
sum = 0
for j in xrange(1000):
str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
sum += distance(str1,str2)
print i,sum/(1000*2**i)
4 Réponses :
Ce que vous pourriez faire est de commencer par apprendre certains concepts et directives OpenMP à partir de ce site: un apprêt d'un débutant pour OpenMP
Vous avez besoin d'un compilateur qui est compatible OpenMP. Voici une liste de compilateurs que travail . Vous voudrez utiliser l'option J'ai ajouté uniquement la directive compiler -fopenmp code> lors de la compilation de votre code. P> #pragma oomp parallèle pour code> à votre code pour indiquer au compilateur que les blocs de code suivants peuvent être exécutés en parallèle. Vous pouvez voir des gains d'addition en performances en changeant vos boucles pendant les boucles pour les boucles ou en appliquant le motif OpenMP tout au long de cette fonction. Vous pouvez régler les performances en ajustant le nombre de threads utilisés pour exécuter les boucles pour les boucles à l'aide de la fonction omp_set_num_threads () code> avant ces blocs. Un bon numéro pour vous de commencer est 8 car vous allez courir sur un processeur à 8 cœurs. P> int main()
{
int i = 0,
j = 0,
sum = 0;
char str1[30]; // Change size to fit your specifications
char str2[30];
#pragma omp parallel for
for(i=0;i<16;i++)
{
sum = 0;
// Could do a reduction on sum across all threads
for(j=0;j<1000;j++)
{
// Calls will have to be changed
// I don't know much Python so I'll leave that to the experts
str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
sum += distance(str1,str2)
}
printf("%d %d",i,(sum/(1000*2*i)));
}
}
Merci pour cela. Je vais exécuter le code dans 32 bits Ubuntu sur un processeur AMD FX (TM) -8350 Huit-Core. Le compilateur est la version 4.7.2 GCC.
J'aurais dû dire que le code Python définit simplement STR1 et STR2 pour être des chaînes binaires aléatoires de longueur 2 ** i.
Qu'est-ce que je ferais:
1) Très petite optimisation: allouer une fois et pour tous les 2) Vous essayez de calculer une moyenne. Faire le calcul moyen en C aussi. Cela devrait sauver quelque chose dans les appels. Encore une fois, petit changement, mais cela vient pas cher. P> 3) puisque vous n'êtes pas intéressé par les calculs réels, mais uniquement dans les résultats, dites que vous avez trois pc et chacun d'entre eux est un quad- Machine de noyau. Ensuite, courez sur chacun d'eux quatre em> les instances du programme, la boucle étant douze em> fois plus courte. Vous obtiendrez douze résultats dans un douzième du temps: Moyenne de ceux-ci et Bob est votre oncle. P> L'option n ° 3 ne nécessite aucune modification, à l'exception du cycle, et vous voudrez peut-être en faire une ligne de commande. paramètre, de sorte que vous puissiez déployer le programme sur un nombre variable d'ordinateurs. En réalité, vous voudrez peut-être produire à la fois le résultat et son "poids", afin de minimiser les chances d'erreurs lorsque vous résumez les résultats ensemble. P> rangées code> pour éviter la gestion de la mémoire. Ou vous pouvez essayer realloc () code>, ou vous pouvez garder une trace de la taille de la ligne code> de la ligne code> dans une variable statique (et avez-vous rangée code> statique aussi ). Cela sauve très peu, même si cela coûte peu de mettre en place. P> for j in xrange(N):
str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i)
sum += distance(str1,str2)
print N,i,sum/(N*2**i)
Merci. Je ne suis intéressé que par les chaînes binaires pour le moment.
Vous pouvez exécuter ce parallèle peut-être. Générez une liste géante de Randoms au début, puis dans votre boucle, des fils de ponte (8 threads) à la fois pour chaque processus de la liste et ajoutez son résultat final à la variable de somme. Ou générer une liste de 8 à la fois et faire 8 à la fois.
Le problème de la suggestion OpenMP est "Cet algorithme parallèglise mal, en raison d'un grand nombre de dépendances de données" - Wikipedia P> Plus tard ... P> for t in threads :
t.join()
Merci. J'entends le multitraitement est le module recommandé de nos jours pour le traitement parallèle python. Le threading a-t-il des avantages?
Le multiprocession utilise des processus au lieu de threads. Beaucoup de gens préfèrent le multitraitement en raison de la serrure de l'interpréteur mondial de Pythons dans le code fileté. Vous pouvez essayer les deux et les comparer, ils ont une syntaxe similaire à l'aide de la classe "Process". MultiProcessing peut en fait avoir un léger avantage ici << a href = "http://docs.python.org/2/library/multiprorocessing.html" rel = "nofollow noreferrer"> docs.python.org/2/library/multiprecessing .html >
Quelqu'un d'autre a eu beaucoup de recherches il y a une année il y a un an et deux a fait des tests de temps d'exécution.
Il est venu avec Ceci et utilisé un arbre de solution pour accélérer les choses up.
Avez-vous profilé votre programme complet et cette fonction pour déterminer où sont dépensés les cycles de la CPU? Sinon, vous devinez juste.
@sizzzzlerz J'ai profilé tout le programme pour trouver qu'il dépense la plupart de son temps dans cette fonction. Je ne sais pas comment profiler la fonction elle-même à tout niveau de détail plus fin.
@Sizzzzlerz Je viens de rérir le profilage. Sur une courte course, cela prend environ 17 secondes dans cette fonction et la fonction la plus chère suivante prend 0,055 seconde.
str1 = bin (aléatoire.getrandbits (2 ** i)) [2:]. zfill (2 ** i) <- qui crée une chaîne de2 ** i 1s et 0s, non? Le calcul de la distance estO (len1 * len2) , pouri = 15 qui prend un certain temps.@Danielelfischer Oui. Si le calcul de la distance pourrait être accéléré par CLEVER C optimisations / utilisation de SSE, etc., ce serait vraiment merveilleux.
Pourquoi avez-vous besoin de le faire sur une corde aussi longtemps que 2 ** 15 caractères? On dirait que la réponse est d'utiliser des chaînes plus courtes. En outre, je suis curieux de savoir pourquoi vous voudriez 1. connaître la réponse à cela, et 2. Pourquoi vous le simuleriez plutôt que de le calculer.
@Agf De bonnes questions! J'essaie d'estimer la distance moyenne de Levenshtein comme la longueur des chaînes va à l'infini. Il n'y a pas de formule connue pour cela, je n'ai donc pas d'autre choix que d'échantillonner au hasard et de prendre la moyenne de ceux-ci. Pour obtenir de bonnes réponses, j'ai besoin de pouvoir échantillonner le plus rapidement possible.
@Marshall OK, mais pour le binaire n'est pas une distance de Levenshtein équivalente au nombre de 1 bits dans une distance excusive-ou b, aka halming distance, qui est O (n)?
@AgF Malheureusement non. Essayez 010 et 101. La distance de Levenshtein est deux.
@Marshall - Je ne sais pas si ceci est une option puisque vous appelez le code C à l'aide de Python, mais vous pouvez essayer de paralleralliser le code plutôt que d'essayer d'optimiser le code de série. Vous pourriez essayer OpenMP pour vos boucles 'pour'.
@ MatTwolfe16 Je ne suis pas contre cela et on peut s'inquiéter de la façon de l'appeler de Python plus tard. Mais .. Je n'ai aucune idée de savoir comment travailler malheureusement.
@ Packersfan16, je doute vraiment que le
pour est un goulot d'étranglement. Il n'est exécuté que 16 000 fois, ce qui est probablement un calcul plus petit que le calcul de la distance d'édition unique dans lei = 15 itération.@AgF "pour binaire n'est pas la distance de la distance de Levenshtein ... Hamming Distance" Si cela était vrai, le projet de Marshall serait nettement plus facile, car le calcul de la distance de halogerie moyenne doit être assez simple.
Le deuxième exemple sur Wikipedia semble être conçu pour une opération plus rapide (préfère remplacer sur Insert / Suppr) et est agréable et succinct. Il est généralement plus rapide de remplacer quelque chose dans une matrice que d'insertion / de suppression et il est plus rapide de faire plusieurs insertions / suppressions à la fois que séquentiellement. De plus, depuis que vous connaissez le nombre de cœurs pouvant être utilisés, vous pouvez dérouler manuellement les boucles pour la parallélisation si votre compilateur ne sera pas (CGC récent avec OpenMP préféré?) ... Mais pour les chaînes binaires, tout le concept est corrigé parce que vous pouvez Do Goops <<, >>, |, &, ^ ... et devrait être retravaillé.
@technosaurus a l'air intéressant. Je suis flexible sur quel compilateur que j'utilise. Je suis actuellement sur GCC 4.7.2.
Si vous vouliez vraiment que vous souhaitiez une vitesse, vous pouvez utiliser une opération longue et utilisez une seule opération XOR («^») sur une autre longue longue en tant qu'observation à cycle unique (sur la plupart des ordinateurs modernes) pour obtenir 64 bits par cycle ... s'ils sont "Cordes" juste un coussinet avec une limite '\ 0' à 8 octets et jeté à long long * afin que vous puissiez itérer de longues chaînes (vous pouvez utiliser int si vous ciblez principalement 32 bits ... pour 32bits par cycle)
Et si vous deviez dérouler les morts pour 16 threads (8 noyaux avec 2 threads chacun) qui seraient 1024 bits par cycle ou 128 caractères. Si vous avez besoin d'exemples, reportez-vous à la section Strings de tout noyau LIBC ou de noyau ... Bien que le noyau Linux utilise l'assemblage sur la plupart des architectures, le code est écrit pour être incorporable en C
Il y a un algorithme plus intelligent pour la distance de Levenshtein en raison de UKKonen . Je ne sais pas pourquoi toujours à personne ne l'utilise toujours, même s'il a été inventé il y a près de 30 ans.
@larsmans Y a-t-il des implémentations rapides que vous connaissez?
@Marshall: Nope, désolé. Je voulais faire une mise en œuvre moi-même mais je ne suis jamais arrondi.