Comment puis-je optimiser ce code Python pour générer tous les mots avec mot distance 1?
https://stackoverflow.com/questions/788084
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Le profilage montre c'est le plus lent segment mon code pour un petit jeu de mots que j'ai écrit:
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
Notes:
-
distance()est appelé plus de 5 millions de fois, dont la majorité est de GetChildren, qui est censé obtenir tous les mots dans la liste de mots qui diffèrent dewordexactement 1 lettre. - est wordlist préfiltré pour avoir seulement des mots contenant le même nombre de lettres que
wordil est garanti queword1etword2ont le même nombre de caractères. - Je suis assez nouveau pour Python (commencé à apprendre il y a 3 jours) si des commentaires sur les conventions de nommage ou d'autres choses de style ont également apprécié.
- pour wordlist prendre la liste de mots 12dict en utilisant le « 2+ 2lemma.txt » fichier
Résultats:
Merci tout le monde, avec des combinaisons de différentes suggestions que je reçu le programme en cours d'exécution deux fois plus vite maintenant (au-dessus des optimisations que j'ai fait moi-même avant de demander, donc 4 fois la vitesse augmente environ de ma mise en œuvre initiale)
Je l'ai testé avec 2 séries d'entrées que je vais appeler A et B
optimisation1: itérer sur indices de word1,2 ... à partir de
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
itérer sur les paires de lettres en utilisant zip(word1, word2)
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
eu le temps d'exécution de 11,92 à 9,18 pour l'entrée A, et 79,30 à 74,59 pour l'entrée B
Optimization2: Ajout d'un procédé distinct pour diffère par un, en plus de la distance (procédé qui je encore nécessaires ailleurs pour les heuristiques A *)
def is_neighbors(word1,word2):
different = False
for c1,c2 in zip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
eu le temps d'exécution de 9,18 à 8,83 pour l'entrée A, et 74,59 à 70,14 pour l'entrée B
Optimization3:
Grand gagnant ici était d'utiliser izip au lieu de zip
eu le temps d'exécution de 8,83 à 5,02 pour l'entrée A, et 70,14 à 41,69 pour l'entrée B
Je pourrais probablement faire mieux l'écrire dans une langue de niveau inférieur, mais je suis heureux avec ce pour l'instant. Merci à tous!
Modifier à nouveau: Plus de résultats En utilisant la méthode de Mark de vérifier le cas où la première lettre ne correspond pas à se vers le bas de 5,02 -> 3,59 et 41,69 -> 29,82
Miser sur cela et incorporant izip au lieu de range , j'ai fini avec ceci:
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
Ce qui serra un peu plus, ce qui porte le temps vers le bas de 3,59 -> 3,38 et 29,82 -> 27,88
résultats encore plus!
Essayer la suggestion de Sumudu que je générer une liste de toutes les chaînes qui sont 1 lettre au large de « mot », puis vérifier pour voir ceux qui étaient dans la liste des mots , au lieu de la fonction is_neighbor J'ai fini avec ceci:
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return ( w for w in oneoff if w in wordlist )
Ce qui a fini par être plus lente (3,38 -> 3,74 et 27,88 -> 34,40) mais il semblait prometteur. Au début, je pensais que la partie que je avais besoin d'optimiser était « one_letter_off_strings », mais le profilage montré autrement et que la partie lente était en fait
( w for w in oneoff if w in wordlist )
Je pensais que s'il n'y aurait aucune différence si je suis passé « OneOff » et « liste de mots » et fait la comparaison de l'autre quand il m'a frappé que je cherchais l'intersection des 2 listes. Je remplacerai que set intersection sur les lettres :
return set(oneoff) & set(wordlist)
Bam! 3,74 -> 0,23 et 34,40 -> 2,25
Ceci est vraiment incroyable, la différence de vitesse totale de ma mise en œuvre naïve originale: 23,79 -> 0,23 et 180,07 -.> 2,25, donc environ 80 à 100 fois plus rapide que la mise en œuvre originale
Si quelqu'un est intéressé, j'ai fait de blog décrivant le programme et sa réponse . Il prétend que ce serait plus rapide en utilisant la méthode originale (à l'aide is_neighbor au lieu d'utiliser les jeux) si elle a été porté à C. J'ai essayé pendant 2 heures pour obtenir un module C je l'ai écrit pour construire et être liable sans beaucoup de succès après avoir essayé de suivez cette et ce exemple, et il semble que le processus est un peu différent dans Windows? Je ne sais pas, mais j'ai renoncé à cela. Quoi qu'il en soit, voici le code complet du programme, et le fichier texte proviennent de la 12dict liste de mots en utilisant le fichier "2 + 2lemma.txt". Désolé si le code est, c'était un peu en désordre juste quelque chose que je piraté ensemble. Aussi j'oublié de dépouiller des virgules de la liste de mots de sorte que est en fait un bug que vous pouvez laisser dans pour le bien de la même comparaison ou le corriger en ajoutant une virgule à la liste des caractères dans cleanentries.
from itertools import izip
def unique(seq):
seen = {}
result = []
for item in seq:
if item in seen:
continue
seen[item] = 1
result.append(item)
return result
def cleanentries(li):
pass
return unique( [w.strip('[]') for w in li if w != "->"] )
def distance(word1, word2):
difference = 0
for x,y in izip (word1, word2):
if x != y:
difference += 1
return difference
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
import Queue
closedset = []
openset = [start]
pqueue = Queue.PriorityQueue(0)
g_score = {start:0} #Distance from start along optimal path.
h_score = {start:distance(start, goal)}
f_score = {start:h_score[start]}
pqueue.put((f_score[start], start))
parent_dict = {}
while len(openset) > 0:
x = pqueue.get(False)[1]
if x == goal:
return reconstruct_path(parent_dict,goal)
openset.remove(x)
closedset.append(x)
sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
sortedOpen.sort()
for y in getchildren(x, wordlist):
if y in closedset:
continue
temp_g_score = g_score[x] + 1
temp_is_better = False
appended = False
if (not y in openset):
openset.append(y)
appended = True
h_score[y] = distance(y, goal)
temp_is_better = True
elif temp_g_score < g_score[y] :
temp_is_better = True
else :
pass
if temp_is_better:
parent_dict[y] = x
g_score[y] = temp_g_score
f_score[y] = g_score[y] + h_score[y]
if appended :
pqueue.put((f_score[y], y))
return None
def reconstruct_path(parent_dict,node):
if node in parent_dict.keys():
p = reconstruct_path(parent_dict,parent_dict[node])
p.append(node)
return p
else:
return []
wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
userentry = raw_input("Hello, enter the 2 words to play with separated by a space:\n ")
words = [w.lower() for w in userentry.split()]
if(len(words) == 2 and len(words[0]) == len(words[1])):
break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
print "Minimum number of steps is %s" % (len(answer))
reply = raw_input("Would you like the answer(y/n)? ")
if(reply.lower() == "y"):
answer.insert(0, words[0])
print "\n".join(answer)
else:
print "Good luck!"
else:
print "Sorry, there's no answer to yours"
reply = raw_input("Press enter to exit")
J'ai quitté la méthode is_neighbors, même si ce n'est pas utilisé. Ceci est la méthode qui est proposée à être porté à C. Pour l'utiliser, il suffit de remplacer GetChildren avec ceci:
def getchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w))
Quant à le faire fonctionner en tant que module C Je n'ai pas jusque-là, mais ce que je suis venu avec:
#include "Python.h"
static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
int length;
const char *word1, *word2;
if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
return NULL;
int i;
int different = 0;
for (i =0; i < length; i++)
{
if (*(word1 + i) != *(word2 + i))
{
if (different)
{
return Py_BuildValue("i", different);
}
different = 1;
}
}
return Py_BuildValue("i", different);
}
PyMethodDef methods[] = {
{"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
{NULL, NULL, 0, NULL}
};
PyMODINIT_FUNC
initIsNeighbor(void)
{
Py_InitModule("isneighbor", methods);
}
Je PROFILES cela en utilisant:
python -m cprofile "Wordgame.py"
Et le temps enregistré était le temps total de l'appel de méthode AStar. L'ensemble d'entrée rapide était « poètes de vers » et l'ensemble d'entrée était longue « vers » poètes. Timings varie évidemment entre les machines différentes, donc si quelqu'un ne finissent par essayer cette comparaison des résultats donnent du programme tel qu'il est, ainsi qu'avec le module C.
La solution
Si votre liste de mots est très longue, pourrait-il être plus efficace pour générer toutes les 1-lettre-différences de « mot » possibles, puis vérifiez ceux qui sont dans la liste? Je ne sais pas Python, mais il devrait y avoir une structure de données appropriée pour la liste de mots permettant lookups log-temps.
Je suggère cela parce que si vos mots sont des longueurs raisonnables (~ 10 lettres), alors vous ne serez cherchez 250 mots potentiels, ce qui est probablement plus rapide si votre liste de mots est plus grand que quelques centaines de mots.
Autres conseils
Votre fonction distance calcule la distance totale, lorsque vous vraiment ne vous préoccupez distance = 1. La majorité des cas, vous saurez qu'il est> 1 en quelques caractères, vous pouvez donc revenir tôt et économiser beaucoup de temps.
Au-delà, il pourrait y avoir un meilleur algorithme, mais je ne peux pas y penser.
Modifier. Une autre idée
Vous pouvez faire 2 cas, selon que le premier caractère correspond. Si elle ne correspond pas, le reste du mot doit correspondre exactement, et vous pouvez tester pour cela d'un seul coup. Dans le cas contraire, faites-le de façon similaire à ce que vous faisiez. Vous pouvez même le faire récursive, mais je ne pense pas que ce serait plus rapide.
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
same = True
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if same:
same = False
else:
return False
return not same
Edit 2: J'ai supprimé le contrôle pour voir si les chaînes sont de la même longueur, puisque vous dites qu'il est redondant. Exécution tests de Ryan sur mon propre code et sur la fonction is_neighbors fourni par MizardX , je reçois le texte suivant :
- distance d'origine (): 3,7 secondes
- Mon DifferentByOne (): 1,1 secondes
- is_neighbors de MizardX (): 3,7 secondes
Modifier 3: (probablement entrer dans le territoire wiki communautaire, mais ...)
Essayer votre définition finale de is_neighbors () avec IZIP au lieu de zip. 2.9 secondes
Voici ma dernière version, qui encore temps à 1.1 secondes:
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if different:
return False
different = True
return different
from itertools import izip
def is_neighbors(word1,word2):
different = False
for c1,c2 in izip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
Ou peut-être en alignant le code izip:
def is_neighbors(word1,word2):
different = False
next1 = iter(word1).next
next2 = iter(word2).next
try:
while 1:
if next1() != next2():
if different:
return False
different = True
except StopIteration:
pass
return different
Et getchildren réécrite:
def iterchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w) )
Les gens vont principalement à ce sujet en essayant d'écrire une fonction plus rapide, mais il pourrait y avoir une autre façon ..
"distance" est appelé plus de 5 millions de fois
Pourquoi est-ce? Peut-être une meilleure façon d'optimiser est d'essayer de réduire le nombre d'appels à distance, plutôt que de se raser millisecondes de temps d'exécution de distance's. Il est impossible de dire sans voir le script complet, mais l'optimisation d'une fonction spécifique est généralement inutile.
Si cela est impossible, vous pourriez peut-être écrire comme un module C?
Comment est souvent la fonction de distance appelée avec les mêmes arguments? Un simple à mettre en œuvre l'optimisation serait d'utiliser memoization .
Vous pouvez probablement aussi créer une sorte de dictionnaire avec frozensets de lettres et des listes de mots qui diffèrent par un et rechercher des valeurs dans ce. Cette structure de données pourrait soit être stocké et chargé par cornichon ou généré à partir de zéro au démarrage.
Le court-circuitage l'évaluation ne vous donnera des gains si les mots que vous utilisez sont très longues, puisque l'algorithme de distance de Hamming que vous utilisez est essentiellement O (n) où n est la longueur de mot.
Je l'ai fait quelques expériences avec timeit pour certaines approches alternatives qui peuvent être illustrative.
Résultats TimeIt
Votre solution
d = """\
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
"""
t1 = timeit.Timer('distance("hello", "belko")', d)
print t1.timeit() # prints 6.502113536776391
One Liner
d = """\
from itertools import izip
def hamdist(s1, s2):
return sum(ch1 != ch2 for ch1, ch2 in izip(s1,s2))
"""
t2 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 10.985101179
Raccourci évaluation
d = """\
def distance_is_one(word1, word2):
diff = 0
for i in xrange(len(word1)):
if word1[i] != word2[i]:
diff += 1
if diff > 1:
return False
return diff == 1
"""
t3 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 6.63337
Eh bien, vous pouvez commencer par avoir votre rupture de boucle si la différence est 2 ou plus.
Vous pouvez également modifier
for i in range(len(word1)):
à
for i in xrange(len(word1)):
Parce que xrange génère des séquences sur la demande au lieu de générer l'ensemble des nombres à la fois.
Vous pouvez également essayer de comparer les longueurs de mots qui serait plus rapide. Notez également que votre code ne fonctionne pas si mot1 est supérieure à word2
Il n'y a pas beaucoup d'autres choses que vous pouvez faire algorithmiquement après cela, ce qui est de dire que vous aurez probablement plus d'un portage que par speedup section C.
Edit 2
Tenter d'expliquer mon analyse de l'algorithme de Sumudu par rapport aux différences de vérification CHAR par char.
Lorsque vous avez un mot de longueur L, le nombre de mots « diffère par un » vous générerez sera 25L. Nous savons que des mises en œuvre de jeux sur les ordinateurs modernes, que la vitesse de recherche est d'environ log (n) base 2 , où n est le nombre d'éléments à rechercher.
Après avoir constaté que la plupart des 5 millions de mots que vous testez contre est pas dans l'ensemble, la plupart du temps, vous serez en traversant l'ensemble, ce qui signifie qu'il devient vraiment journal (25L) au lieu de seulement log (25L) / 2. (Et ceci suppose le meilleur des cas pour les jeux que la comparaison par chaîne chaîne est équivalente à comparer par char omble chevalier)
Maintenant, nous jeter un oeil à la complexité de temps pour déterminer un « diffère par un ». Si nous supposons que vous devez vérifier le mot entier, le nombre d'opérations par mot devient L . Nous savons que la plupart des mots diffèrent par 2 très rapidement. Et sachant que la plupart des préfixes prennent une petite partie du mot, on peut logiquement supposer que vous casserez la plupart du temps par L / 2 , soit la moitié du mot (ce qui est une estimation prudente) .
Alors maintenant, nous traçons les complexités de temps des deux recherches, L / 2 et log (25L), et en gardant à l'esprit que cela même chaîne envisage correspondant à la même vitesse que correspondant char (très en faveur des ensembles). Vous avez le journal de l'équation (25 * L)> L / 2, qui peut être simplifiée jusqu'à log (25)> L / 2 - log (L). Comme vous pouvez le voir sur le graphique, il devrait être plus rapide d'utiliser l'algorithme de correspondance char jusqu'à très un grand nombre de L.
En outre, je ne sais pas si vous comptez briser la différence de 2 ou plus dans votre optimisation, mais de la réponse de Mark I déjà pause sur une différence de 2 ou plus, et en fait, si la différence de la première lettre, il se casse après la première lettre, et même en dépit de toutes ces optimisations, le passage à l'aide d'ensembles juste les sauter hors de l'eau. Je suis intéressé à essayer votre idée si
Je suis la première personne dans cette question de proposer la rupture sur une différence de 2 ou plus. La chose est, que l'idée de marque de découpage en tranches de chaîne (si word1 [0] = word2 [0]: retour word1 [1:] == word2 [1:]) est en train de mettre tout simplement ce que nous faisons en C. Comment avez-vous penser word1 [1:] == word2 [1:] est calculée? De la même façon que nous faisons.
Je lis votre explication quelques fois, mais je ne suis pas tout à fait cela, voulez-vous nous expliquer un peu plus en profondeur? Aussi je ne suis pas terriblement familier avec le C et je travaille dans les langues de haut niveau au cours des dernières années (le plus proche a été l'apprentissage C ++ dans le lycée il y a 6 ans
En ce qui concerne la production du code C, je suis un peu occupé. Je suis sûr que vous serez en mesure de le faire depuis que vous avez écrit en C avant. Vous pouvez également essayer C #, ce qui a probablement des caractéristiques de performance similaires.
Plus Explication
Voici une explication plus approfondie à Davy8
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
Votre fonction one_letter_off_strings va créer un ensemble de chaînes 25L (où L est le nombre de lettres).
CreAting un ensemble de la liste de mots va créer un ensemble de chaînes D (où D est la longueur de votre dictionnaire). En créant une intersection de cela, vous DOIT itérer sur chaque OneOff et voir si elle existe dans wordlist .
La complexité de temps pour cette opération est détaillée ci-dessus. Cette opération est moins efficace que la comparaison du mot que vous voulez avec chaque mot wordlist . La méthode de sumudu est une optimisation en C plutôt que dans l'algorithme.
Plus Explication 2
Il y a seulement 4500 mots au total (parce que la liste de mots est pré-filtré pour 5 mots de lettre avant même d'être passé à l'algorithme), étant entrecoupés de 125 mots-off d'une lettre. Il semble que vous disiez intersection est log (plus petit) ou dans le journal otherwords (125, 2). Comparez cela à nouveau en supposant que vous avez dit, où l'on compare une pause de mot dans L / 2 lettres, je vais arrondir cela à 2, même si un mot de 5 lettres, il est plus susceptible d'être 3. Cette comparaison se fait 4500 fois, si 9000. log (125,2) est d'environ 6,9, et le journal (4500,2) est d'environ 12. laissez-moi savoir si je mal interprété vos chiffres.
Pour créer l'intersection de 125 mots-off d'une lettre avec un dictionnaire de 4500, vous devez faire 125 * 4500 comparaisons. Ceci est journalise pas (125,2). Il est au mieux 125 * log (4500, 2) en supposant que le dictionnaire est prétrié. Il n'y a pas de raccourci magique pour les ensembles. Vous faites également une chaîne par chaîne au lieu de char par comparaison char ici.
Pour une telle fonction simple qui a une si grande implication de la performance, je serais probablement faire une bibliothèque C et l'appeler à l'aide ctypes . L'un des fondateurs de reddit réclamations qu'ils ont fait le site en utilisant 2x plus vite cette technique.
Vous pouvez également utiliser psyco sur cette fonction, mais méfiez-vous qu'il peut manger beaucoup de mémoire .
Je ne sais pas si cela va affecter de manière significative votre vitesse, mais vous pouvez commencer en tournant la compréhension de la liste dans une expression de générateur. Il est encore itérables donc il ne devrait pas être très différente dans l'usage:
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
à
def getchildren(word, wordlist):
return ( w for w in wordlist if distance(word, w) == 1 )
Le principal problème serait qu'une compréhension de la liste ne se construire en mémoire et prendre un peu d'espace, alors que le générateur va créer votre liste à la volée donc il n'y a pas besoin de stocker l'ensemble.
En outre, à la suite sur la réponse inconnue, cela peut être une manière plus « pythonique » de la distance d'écriture ():
def distance(word1, word2):
difference = 0
for x,y in zip (word1, word2):
if x == y:
difference += 1
return difference
Mais il est déroutant ce INTENTIONNELLE quand len (word1)! = Len (mot2), dans le cas de zip ne retournera autant de caractères que le mot le plus court. (Ce qui pourrait se révéler une optimisation ...)
Essayez ceci:
def distance(word1, word2):
return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])
En outre, avez-vous un lien vers votre jeu? J'aime être détruit par des jeux de mots
La première chose à se produire à moi:
from operator import ne
def distance(word1, word2):
return sum(map(ne, word1, word2))
qui a une bonne chance d'aller plus vite que d'autres fonctions de gens ont posté, car il n'a pas de boucles interprétées, appelle simplement à des primitives Python. Et il est assez court que vous pourriez inline raisonnablement dans l'appelant.
Pour votre problème de niveau supérieur, je regarde dans les structures de données mis au point pour la recherche de similarité dans les espaces métriques, par exemple ce papier ou
pour cet extrait: j'utiliser celui-ci: le même schéma suivrait tout autour du code fourni ... for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])
Tout le monde mis au point juste sur le calcul de la distance explicite sans rien faire construire les candidats à distance 1.
Vous pouvez améliorer en utilisant un bien connu des données structure appelée Trie pour fusionner les
Voici le pseudocode: marcher sur la Trie itérativement pour votre parole donnée; à chaque noeud ajouter toutes les distances et la distance 0-1 voisins les résultats; garder un compteur de distance et de décrémenter. Vous n'avez pas besoin récursion, juste une fonction de recherche qui prend un argument entier distance_so_far supplémentaire.
Un compromis mineure de vitesse supplémentaire pour l'augmentation de l'espace de O (N) peut être obtenu par la construction d'Essais séparés pour longueur 3, 4-longueur, la longueur des mots-5 etc..
