Wie kann ich diesen Python-Code optimieren, um alle Wörter mit Wortabstand 1 zu generieren?
https://stackoverflow.com/questions/788084
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Die Profilerstellung zeigt, dass dies der langsamste Abschnitt meines Codes für ein kleines Wortspiel ist, das ich geschrieben habe:
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 ]
Anmerkungen:
distance()wird über 5 Millionen Mal aufgerufen, die meisten davon von getchildren, das alle Wörter in der Wortliste abrufen soll, die sich von unterscheidenwordum genau 1 Buchstaben.- Die Wortliste ist vorgefiltert und enthält nur Wörter mit der gleichen Anzahl an Buchstaben wie
worddas ist also garantiertword1Undword2haben die gleiche Anzahl von Zeichen. - Ich bin ziemlich neu in Python (habe vor 3 Tagen angefangen, es zu lernen), daher bin ich auch über Kommentare zu Namenskonventionen oder anderen Stilaspekten dankbar.
- Für die Wortliste nehmen Sie die 12dict-Wortliste mit der Datei „2+2lemma.txt“.
Ergebnisse:
Vielen Dank an alle, mit Kombinationen verschiedener Vorschläge habe ich das Programm jetzt doppelt so schnell laufen lassen (zusätzlich zu den Optimierungen, die ich vor meiner Anfrage selbst durchgeführt habe, also etwa eine vierfache Geschwindigkeitssteigerung gegenüber meiner ursprünglichen Implementierung).
Ich habe mit zwei Eingangssätzen getestet, die ich A und B nennen werde
Optimierung1:Iteriere über die Indizes von Wort1,2 ...aus
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
Zu Iterieren Sie Buchstabenpaare mit zip(word1, word2)
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
Ausführungszeit von 11,92 auf 9,18 für Eingabe A und 79,30 auf 74,59 für Eingabe B
Optimierung2:Zusätzlich zur Distanzmethode (die ich noch an anderer Stelle für die A*-Heuristik benötigte) wurde eine separate Methode für „Differenzen um eins“ hinzugefügt.
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
Die Ausführungszeit wurde für Eingabe A von 9,18 auf 8,83 und für Eingabe B von 74,59 auf 70,14 erhöht
Optimierung3:Der große Gewinner war hier die Verwendung izip anstatt zip
Ausführungszeit von 8,83 auf 5,02 für Eingabe A und 70,14 auf 41,69 für Eingabe B
Ich könnte es wahrscheinlich besser in einer niedrigeren Sprache schreiben, aber im Moment bin ich damit zufrieden.Vielen Dank an alle!
Nochmal bearbeiten:Weitere Ergebnisse unter Verwendung der Mark -Methode, um den Fall zu überprüfen, in dem der erste Buchstabe nicht übereinstimmt, hat ihn von 5.02 -> 3,59 und 41.69 -> 29.82 abgebaut
Darauf aufbauend und einbeziehen izip anstatt range, am Ende habe ich Folgendes herausgefunden:
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
Was noch etwas enger wurde und die Zeiten von 3,59 -> 3,38 auf 29,82 -> 27,88 senkte
Noch mehr Ergebnisse!
Ich versuche Sumudus Vorschlag, dass ich Erstellen Sie eine Liste aller Zeichenfolgen, die 1 Buchstaben von „Wort“ entfernt sind, und prüfen Sie dann, welche Zeichenfolgen in der Wortliste enthalten sind, anstelle der Funktion is_neighbor habe ich Folgendes erhalten:
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 )
Was letztendlich langsamer war (3,38 -> 3,74 und 27,88 -> 34,40), aber es schien vielversprechend.Zuerst dachte ich, der Teil, den ich optimieren müsste, sei „one_letter_off_strings“, aber die Profilerstellung zeigte etwas anderes und dass der langsame Teil tatsächlich so war
( w for w in oneoff if w in wordlist )
Ich dachte, ob es einen Unterschied gäbe, wenn ich „oneoff“ und „wordlist“ vertausche und den Vergleich andersherum durchführe, als mir klar wurde, dass ich nach der Schnittmenge der beiden Listen suchte.Ich ersetze das durch Set-Schnittpunkt auf den Buchstaben:
return set(oneoff) & set(wordlist)
Bumm!3,74 -> 0,23 und 34,40 -> 2,25
Das ist wirklich erstaunlich, der Gesamtgeschwindigkeitsunterschied zu meiner ursprünglichen naiven Implementierung:23,79 -> 0,23 und 180,07 -> 2,25, also etwa 80 bis 100 Mal schneller als die ursprüngliche Implementierung.
Falls es jemanden interessiert, ich habe einen Blogbeitrag verfasst Beschreibung des Programms Und Beschreibung der Optimierungen erstellt, einschließlich eines, das hier nicht erwähnt wird (weil es sich in einem anderen Abschnitt des Codes befindet).
Die große Debatte:
Ok, ich und Unknown führen eine große Debatte, die Sie in den Kommentaren von lesen können seine Antwort.Er behauptet, dass es mit der ursprünglichen Methode (mit is_neighbor statt mit den Sets) schneller wäre, wenn sie nach C portiert würde.Ich habe 2 Stunden lang versucht, ein C-Modul, das ich geschrieben habe, zu erstellen und verknüpfbar zu machen, ohne großen Erfolg, nachdem ich versucht hatte, es zu befolgen Das Und Das Beispiel, und es sieht so aus, als ob der Prozess unter Windows etwas anders ist?Ich weiß es nicht, aber ich habe es aufgegeben.Wie auch immer, hier ist der vollständige Code des Programms und die Textdatei stammt von 12dict-Wortliste mit der Datei „2+2lemma.txt“.Tut mir leid, wenn der Code etwas chaotisch ist, das habe ich nur zusammengehackt.Außerdem habe ich vergessen, Kommas aus der Wortliste zu entfernen, sodass es sich tatsächlich um einen Fehler handelt, den Sie für den gleichen Vergleich belassen oder durch Hinzufügen eines Kommas zur Liste der Zeichen in Cleanentries beheben können.
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")
Ich habe die Methode is_neighbors belassen, obwohl sie nicht verwendet wird.Dies ist die Methode, deren Portierung auf C vorgeschlagen wird.Um es zu verwenden, ersetzen Sie einfach getchildren durch Folgendes:
def getchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w))
Um es als C-Modul zum Laufen zu bringen, bin ich nicht so weit gekommen, aber das hier ist, was ich mir ausgedacht habe:
#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);
}
Ich habe dies profiliert mit:
python -m cProfile „Wordgame.py“
Und die aufgezeichnete Zeit war die Gesamtzeit des AStar-Methodenaufrufs.Der schnelle Eingabesatz war „Versdichter“ und der lange Eingabesatz war „Dichterverse“.Die Zeiten variieren offensichtlich zwischen verschiedenen Maschinen. Wenn also jemand dies versucht, vergleichen Sie die Ergebnisse mit dem Programm in seiner jetzigen Form und mit dem C-Modul.
Lösung
Wenn Ihre WordList sehr lang ist, ist es möglicherweise effizienter, alle möglichen 1-Buchstaben-Differenzen aus 'Wort' zu generieren, dann prüfen Sie, welche sich in der Liste befinden? Ich kenne keine Python, aber es sollte eine geeignete Datenstruktur für die WordList geben, die Suchzeit für Protokollzeit ermöglicht.
Ich schlage dies vor, denn wenn Ihre Wörter vernünftige Längen sind (~ 10 Buchstaben), suchen Sie nur nach 250 potenziellen Wörtern, was wahrscheinlich schneller ist, wenn Ihre WordList größer als ein paar hundert Wörter ist.
Andere Tipps
Ihre Funktion distance Berechnet die Gesamtentfernung, wenn Sie sich wirklich nur um die Entfernung = 1 kümmern. In den meisten Fällen werden Sie wissen, dass es in wenigen Zeichen> 1 ist, sodass Sie früh zurückkehren und viel Zeit sparen können.
Darüber hinaus könnte es einen besseren Algorithmus geben, aber ich kann mir nicht vorstellen.
Bearbeiten: Eine andere Idee.
Sie können 2 Fälle vornehmen, je nachdem, ob der erste Charakter übereinstimmt. Wenn es nicht übereinstimmt, muss der Rest des Wortes genau übereinstimmen, und Sie können das in einem Schuss testen. Ansonsten tun Sie es ähnlich wie das, was Sie getan haben. Sie könnten es sogar rekursiv tun, aber ich denke nicht, dass das schneller wäre.
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
Bearbeiten 2: Ich habe den Scheck gelöscht, um festzustellen, ob die Saiten gleich lang sind, da Sie sagen, dass sie überflüssig ist. Betrieb Ryans Tests in meinem eigenen Code und auf der Funktion is_Neighbors bereitgestellt von Mizardx, Ich bekomme Folgendes:
- Originalentfernung (): 3,7 Sekunden
- Mein Unterschied (): 1,1 Sekunden
- Mizardx is_Neighbors (): 3,7 Sekunden
Bearbeiten 3: (Wahrscheinlich in das Gemeinschafts -Wiki -Territorium hier, aber ...)
Versuchen Sie Ihre endgültige Definition von is_Neighbors () mit Izip anstelle von Reißverschluss: 2,9 Sekunden.
Hier ist meine neueste Version, die immer noch mit 1,1 Sekunden zählt:
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
Oder vielleicht die auskleiden izip Code:
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
Und ein neu geschriebenes getchildren:
def iterchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w) )
Die Leute machen dies hauptsächlich, indem sie versuchen, eine schnellere Funktion zu schreiben, aber es könnte einen anderen Weg geben.
"Entfernung" wird über 5 Millionen Mal bezeichnet
Warum ist das? Vielleicht ist es eine bessere Möglichkeit, zu optimieren distance, anstatt Millisekunden von zu rasieren distance's Ausführungszeit. Es ist unmöglich zu erkennen, ohne das vollständige Skript zu sehen, aber es ist im Allgemeinen unnötig, eine bestimmte Funktion zu optimieren.
Wenn das unmöglich ist, könnten Sie es vielleicht als C -Modul schreiben?
Wie oft wird die Entfernungsfunktion mit den gleichen Argumenten aufgerufen? Eine einfache implementierende Optimierung wäre zu verwenden Memoisierung.
Sie könnten wahrscheinlich auch eine Art Wörterbuch mit Frozensets von Buchstaben und Wörtern erstellen, die sich um eins unterscheiden und die Werte darin nachsehen. Diese Datenstruktur kann entweder gespeichert und durch Gurke geladen oder beim Start von Grund auf generiert werden.
Kurzschluss Die Bewertung ergibt nur Gewinne, wenn die von Ihnen verwendeten Wörter sehr lang sind, da der von Ihnen verwendete Hamming -Entfernungsalgorithmus im Grunde genommen o (n) ist, wobei n die Wortlänge ist.
Ich habe einige Experimente mit zeitlich für einige alternative Ansätze durchgeführt, die möglicherweise veranschaulichend sein.
Timeit -Ergebnisse
Ihre Lösung
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
Einzeiler
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
Verknüpfungsbewertung
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
Nun, Sie können damit beginnen, dass Ihre Schleife unterbrochen wird, wenn die Differenz 2 oder mehr beträgt.
Sie können auch ändern
for i in range(len(word1)):
Zu
for i in xrange(len(word1)):
Weil xrange bei Bedarf Sequenzen generiert, anstatt den gesamten Zahlenbereich auf einmal zu generieren.
Sie können auch versuchen, die Wortlängen zu vergleichen, was schneller geht.Beachten Sie außerdem, dass Ihr Code nicht funktioniert, wenn Wort1 größer als Wort2 ist
Danach können Sie algorithmisch nicht mehr viel tun, was bedeutet, dass Sie durch die Portierung dieses Abschnitts nach C wahrscheinlich eine größere Beschleunigung erzielen werden.
Bearbeiten 2
Ich versuche, meine Analyse des Sumudu-Algorithmus im Vergleich zur Überprüfung von Unterschieden Zeichen für Zeichen zu erklären.
Wenn Sie ein Wort der Länge L haben, beträgt die Anzahl der „Unterschiede um eins“-Wörter, die Sie generieren, 25L.Aus Implementierungen von Mengen auf modernen Computern wissen wir, dass die Suchgeschwindigkeit ungefähr beträgt log(n) Basis 2, wobei n die Anzahl der zu suchenden Elemente ist.
Da die meisten der 5 Millionen Wörter, die Sie testen, dies sind nicht Im Set durchqueren Sie die meiste Zeit das gesamte Set, was bedeutet, dass es wirklich wird Protokoll (25L) statt nur log(25L)/2.(und dies setzt im besten Fall ein Szenario für Sätze voraus, bei dem der Vergleich von Zeichenfolge für Zeichenfolge gleichbedeutend mit dem Vergleich von Zeichen für Zeichen ist.)
Nun werfen wir einen Blick auf die zeitliche Komplexität zur Bestimmung einer „Unterscheidet sich um eins“.Wenn wir davon ausgehen, dass Sie das gesamte Wort überprüfen müssen, beträgt die Anzahl der Operationen pro Wort L.Wir wissen, dass sich die meisten Wörter sehr schnell um 2 unterscheiden.Und da wir wissen, dass die meisten Präfixe nur einen kleinen Teil des Wortes einnehmen, können wir logischerweise davon ausgehen, dass Sie die meiste Zeit durchbrechen werden L/2, oder die Hälfte des Wortes (und dies ist eine konservative Schätzung).
Nun zeichnen wir die zeitliche Komplexität der beiden Suchvorgänge L/2 und log(25L) auf und berücksichtigen dies Dabei wird sogar berücksichtigt, dass der String-Matching die gleiche Geschwindigkeit hat wie der Char-Matching (sehr zugunsten von Sets).Sie haben die Gleichung log(25*L) > L/2, die vereinfacht werden kann zu log(25) > L/2 - log(L).Wie Sie der Grafik entnehmen können, sollte es schneller gehen, den char-Matching-Algorithmus zu verwenden, bis Sie erreicht sind sehr große Anzahl von L.
Außerdem weiß ich nicht, ob Sie bei Ihrer Optimierung mit einem Bruch bei einer Differenz von 2 oder mehr rechnen, aber aus Marks Antwort geht hervor, dass ich bereits bei einem Unterschied von 2 oder mehr breche, und tatsächlich, wenn der Unterschied im ersten Buchstaben liegt, ist er es Pausen nach dem ersten Buchstaben, und selbst trotz all dieser Optimierungen hat die Umstellung auf die Verwendung von Sets sie einfach umgehauen.Ich bin jedoch daran interessiert, Ihre Idee auszuprobieren
Ich war der Erste, der in dieser Frage vorgeschlagen hat, bei einer Differenz von 2 oder mehr zu brechen.Die Sache ist, dass Marks Idee des String-Slicings (wenn Wort1[0] != Wort2[0]:return word1[1:] == word2[1:]) bedeutet einfach, das, was wir tun, in C zu übertragen.Wie denkst du Wort1[1:] == Wort2[1:] ist berechnet?Genauso wie wir es tun.
Ich habe Ihre Erklärung ein paar Mal gelesen, bin ihr aber nicht ganz gefolgt. Würde es Ihnen etwas ausmachen, sie etwas ausführlicher zu erklären?Außerdem kenne ich mich nicht besonders gut mit C aus und arbeite seit ein paar Jahren mit Hochsprachen (am ehesten habe ich vor 6 Jahren in der High School C++ gelernt).
Was die Erstellung des C-Codes betrifft, bin ich etwas beschäftigt.Ich bin mir sicher, dass Sie es schaffen werden, da Sie zuvor in C geschrieben haben.Sie könnten auch C# ausprobieren, das wahrscheinlich ähnliche Leistungsmerkmale aufweist.
Weitere Erklärung
Hier ist eine ausführlichere Erklärung zu Davy8
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
Ihre one_letter_off_strings-Funktion erstellt einen Satz von 25L-Strings (wobei L die Anzahl der Buchstaben ist).
Wenn Sie einen Satz aus der Wortliste erstellen, wird ein Satz von D-Zeichenfolgen erstellt (wobei D die Länge Ihres Wörterbuchs ist).Indem Sie daraus einen Schnittpunkt erstellen, können Sie MUSS iteriere über jedes einmalig und sehen Sie, ob es in existiert Wortliste.
Die zeitliche Komplexität für diesen Vorgang ist oben detailliert beschrieben.Dieser Vorgang ist weniger effizient als der Vergleich Wort Sie wollen mit jedem Wort in Wortliste.Sumudus Methode ist eine Optimierung in C und nicht in einem Algorithmus.
Weitere Erklärung 2
Insgesamt gibt es nur 4500 Wörter (da die Wortliste vor der Übergabe an den Algorithmus nach Wörtern mit fünf Buchstaben vorgefiltert wird), die sich mit 125 Wörtern mit einem Buchstaben überschneiden.Anscheinend sagten Sie, der Schnittpunkt sei log(kleiner) oder mit anderen Worten log(125, 2).Vergleichen Sie dies erneut mit der Annahme, was Sie gesagt haben: Wenn ein Wort beim Vergleich in L/2 Buchstaben umgebrochen wird, runde ich dies auf 2 ab, obwohl es bei einem Wort mit 5 Buchstaben wahrscheinlicher ist, dass es 3 ist.Dieser Vergleich wird 4500 Mal durchgeführt, also 9000.log(125,2) beträgt etwa 6,9 und log(4500,2) etwa 12.Lassen Sie mich wissen, ob ich Ihre Zahlen falsch interpretiert habe.
Um die Schnittmenge von 125 Ein-Buchstaben-Wörtern mit einem Wörterbuch von 4500 zu erstellen, müssen Sie 125 * 4500 Vergleiche durchführen.Dies ist nicht log(125,2).Unter der Annahme, dass das Wörterbuch vorsortiert ist, beträgt es bestenfalls 125 * log(4500, 2). Es gibt keine magische Abkürzung für Sets. Sie führen hier auch einen Zeichenfolge-für-Zeichen-Vergleich anstelle eines Zeichen-für-Zeichen-Vergleichs durch.
Für eine so einfache Funktion, die eine so große Leistung implikation hat, würde ich wahrscheinlich eine C -Bibliothek erstellen und sie verwenden Ctypes. Einer der Gründer von Reddit behauptet, sie hätten die Website 2x mit dieser Technik genauso schnell gemacht.
Sie können auch verwenden Psyco Bei dieser Funktion, aber achten Sie darauf, dass es viel Speicher auf sichern kann.
Ich weiß nicht, ob es Ihre Geschwindigkeit erheblich beeinflusst, aber Sie könnten zunächst das Listenverständnis in einen Generatorausdruck umwandeln. Es ist immer noch iterbar, also sollte es im Gebrauch nicht viel anders sein:
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
zu
def getchildren(word, wordlist):
return ( w for w in wordlist if distance(word, w) == 1 )
Das Hauptproblem wäre, dass ein Listenverständnis sich selbst im Speicher konstruieren und einiges an Platz in Anspruch nehmen würde, während der Generator Ihre Liste in der Hand erstellt, sodass das Ganze nicht gespeichert werden muss.
Nach der Antwort von Unbekannt kann dies auch eine "pythonischere" Art des Schreibens der Entfernung () sein:
def distance(word1, word2):
difference = 0
for x,y in zip (word1, word2):
if x == y:
difference += 1
return difference
Aber es ist verwirrend, was beabsichtigt ist, wenn Len (Word1)! (Was sich als Optimierung herausstellen könnte ...)
Versuche dies:
def distance(word1, word2):
return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])
Haben Sie auch einen Link zu Ihrem Spiel? Ich mag es, durch Wortspiele zerstört zu werden
Das erste, was mir einfällt:
from operator import ne
def distance(word1, word2):
return sum(map(ne, word1, word2))
Das hat eine anständige Chance, schneller zu werden als andere Funktionen, die Menschen veröffentlicht haben, weil es keine interpretierten Schleifen hat, nur auf Python -Primitive aufgerufen. Und es ist kurz genug, dass Sie es vernünftigerweise in den Anrufer einbeziehen könnten.
Für Ihr höheres Problem würde ich die Datenstrukturen untersuchen, die für die Ähnlichkeitssuche in metrischen Räumen entwickelt wurden, z. B. dieses Papier oder dieses Buch, Ich habe mich nicht gelesen (sie sind auf der Suche nach einem Papier aufgetaucht, das ich gelesen habe, aber nicht erinnern kann).
Für diesen Ausschnitt:
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
Ich würde diesen verwenden:
return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])
Das gleiche Muster würde rund um den bereitgestellten Code folgen ...
Alle anderen konzentrierten sich nur auf explizite Entfernungskalkulation, ohne etwas gegen die Konstruktion der Kandidaten der Distanz-1 zu tun. Sie können sich verbessern, indem Sie eine bekannte Datenstruktur namens a verwenden Trie Um das zusammenzuführen implizite Entfernungskalkulation mit der Aufgabe von Erzeugen Sie alle Distanz-1-Nachbarwörter. Ein Trie ist eine verknüpfte List, bei der jeder Knoten für einen Buchstaben steht, und das "nächste" Feld "Nächste" ist ein DIKT mit bis zu 26 Einträgen, der auf den nächsten Knoten zeigt.
Hier ist der Pseudocode: Gehen Sie den trie iterativ für Ihr gegebenes Wort; Fügen Sie bei jedem Knoten den gesamten Abstand-0- und Abstand-1-Nachbarn zu den Ergebnissen hinzu; Halten Sie einen Zähler der Entfernung und verringern Sie ihn. Sie benötigen keine Rekursion, nur eine Suchfunktion, die ein zusätzliches Distanz -Argument für ganzzahlige Integer erfordert.
Ein geringfügiger Kompromiss mit zusätzlicher Geschwindigkeit für O (N) -Paltrate erhöht sich, indem separate Versuche für Länge 3, Länge, 4, Länge-5 usw. erstellt werden.
