Python Leistungsverbesserung Anfrage für winkler
-
02-10-2019 - |
Frage
Ich bin ein n00b Python und ich würde einige Vorschläge, wie, wie der Algorithmus zur Verbesserung der Leistungsfähigkeit dieser Methode zur Verbesserung des Jaro-Winkler Abstand von zwei Namen zu berechnen.
def winklerCompareP(str1, str2):
"""Return approximate string comparator measure (between 0.0 and 1.0)
USAGE:
score = winkler(str1, str2)
ARGUMENTS:
str1 The first string
str2 The second string
DESCRIPTION:
As described in 'An Application of the Fellegi-Sunter Model of
Record Linkage to the 1990 U.S. Decennial Census' by William E. Winkler
and Yves Thibaudeau.
Based on the 'jaro' string comparator, but modifies it according to whether
the first few characters are the same or not.
"""
# Quick check if the strings are the same - - - - - - - - - - - - - - - - - -
#
jaro_winkler_marker_char = chr(1)
if (str1 == str2):
return 1.0
len1 = len(str1)
len2 = len(str2)
halflen = max(len1,len2) / 2 - 1
ass1 = '' # Characters assigned in str1
ass2 = '' # Characters assigned in str2
#ass1 = ''
#ass2 = ''
workstr1 = str1
workstr2 = str2
common1 = 0 # Number of common characters
common2 = 0
#print "'len1', str1[i], start, end, index, ass1, workstr2, common1"
# Analyse the first string - - - - - - - - - - - - - - - - - - - - - - - - -
#
for i in range(len1):
start = max(0,i-halflen)
end = min(i+halflen+1,len2)
index = workstr2.find(str1[i],start,end)
#print 'len1', str1[i], start, end, index, ass1, workstr2, common1
if (index > -1): # Found common character
common1 += 1
#ass1 += str1[i]
ass1 = ass1 + str1[i]
workstr2 = workstr2[:index]+jaro_winkler_marker_char+workstr2[index+1:]
#print "str1 analyse result", ass1, common1
#print "str1 analyse result", ass1, common1
# Analyse the second string - - - - - - - - - - - - - - - - - - - - - - - - -
#
for i in range(len2):
start = max(0,i-halflen)
end = min(i+halflen+1,len1)
index = workstr1.find(str2[i],start,end)
#print 'len2', str2[i], start, end, index, ass1, workstr1, common2
if (index > -1): # Found common character
common2 += 1
#ass2 += str2[i]
ass2 = ass2 + str2[i]
workstr1 = workstr1[:index]+jaro_winkler_marker_char+workstr1[index+1:]
if (common1 != common2):
print('Winkler: Wrong common values for strings "%s" and "%s"' % \
(str1, str2) + ', common1: %i, common2: %i' % (common1, common2) + \
', common should be the same.')
common1 = float(common1+common2) / 2.0 ##### This is just a fix #####
if (common1 == 0):
return 0.0
# Compute number of transpositions - - - - - - - - - - - - - - - - - - - - -
#
transposition = 0
for i in range(len(ass1)):
if (ass1[i] != ass2[i]):
transposition += 1
transposition = transposition / 2.0
# Now compute how many characters are common at beginning - - - - - - - - - -
#
minlen = min(len1,len2)
for same in range(minlen+1):
if (str1[:same] != str2[:same]):
break
same -= 1
if (same > 4):
same = 4
common1 = float(common1)
w = 1./3.*(common1 / float(len1) + common1 / float(len2) + (common1-transposition) / common1)
wn = w + same*0.1 * (1.0 - w)
return wn
Beispiel Ausgabe
ZIMMERMANN ARMIENTO 0.814583333
ZIMMERMANN ZIMMERMANN 1
ZIMMERMANN CANNONS 0.766666667
CANNONS AKKER 0.8
CANNONS ALDERSON 0.845833333
CANNONS ALLANBY 0.833333333
Lösung
Ich konzentrierte mich mehr auf die Optimierung mehr aus Python zu bekommen, als auf den Algorithmus zu optimieren, weil ich glaube nicht, dass es viel von einer algorithmischen Verbesserung ist hier werden musste. Hier sind einige Python-Optimierungen, dass ich kam mit.
(1). Da Sie werden mit Python 2.x angezeigt wird, ändern alle Bereich () 's zu xrange ()' s. range () erzeugt die vollständige Liste der Zahlen, bevor über sie iterieren während xrange sie erzeugt je nach Bedarf.
(2). Nehmen Sie die folgenden Substitutionen für max und min:
start = max(0,i-halflen)
mit
start = i - halflen if i > halflen else 0
und
end = min(i+halflen+1,len2)
mit
end = i+halflen+1 if i+halflen+1 < len2 else len2
in der ersten Schleife und ähnlichen für die zweite Schleife. Es gibt auch eine andere min () weiter nach unten und ein max () am Anfang der Funktion tut das gleiche mit denen. Ersetzen des min () ‚s und max ()‘ s half wirklich die Zeit zu reduzieren. Dies sind praktische Funktionen, aber teurer als die Methode, die ich ersetzt habe sie mit.
(3). Verwenden COMMON1 statt len ??(ASS1). Sie haben den Überblick über die Länge von ASS1 in gewurzelt1 gehalten, so machen wir es verwenden, anstatt eine teure Funktion aufrufen wieder zu finden ist.
(4). Ersetzen Sie den folgenden Code ein:
minlen = min(len1,len2)
for same in xrange(minlen+1):
if (str1[:same] != str2[:same]):
break
same -= 1
mit
for same in xrange(minlen):
if str1[same] != str2[same]:
break
Der Grund dafür ist vor allem, dass str1 [: samt] jedes Mal durch die Schleife eine neue Zeichenfolge erstellt und Sie werden Teile werden überprüfen, ob Sie bereits überprüft haben. Auch gibt es keine Notwendigkeit, zu überprüfen, ob '' != ''
und Abnahme same
danach, wenn wir nicht haben.
(5). Verwenden Sie psyco , eine Just-in-Time-Compiler der Arten. Sobald Sie es heruntergeladen haben und es installiert ist, fügen Sie einfach die Zeilen
import psyco
psyco.full()
am Anfang der Datei, es zu benutzen. Verwenden Sie keine psyco, wenn Sie die anderen Änderungen zu tun, dass ich erwähnt habe. Aus irgendeinem Grund, wenn ich es auf dem Original-Code lief es verlangsamt es tatsächlich nach unten.
Mit timeit, fand ich, dass ich eine Abnahme in der Zeit von etwa 20% oder so mit den ersten vier Änderungen zu bekommen. Allerdings, wenn ich psyco zusammen mit diesen Änderungen hinzufügen, ist der Code über 3x schneller als das Original 4x.
Wenn Sie mehr Geschwindigkeit wollen
Eine angemessene Menge der verbleibenden Zeit ist in der Entdeckung des String () -Methode. Ich beschloss, ersetzt dies mit meinem eigenen zu versuchen. Für die erste Schleife, ersetzt I
index = workstr2.find(str1[i],start,end)
mit
index = -1
for j in xrange(start,end):
if workstr2[j] == str1[i]:
index = j
break
und eine ähnliche Form für die zweite Schleife. Ohne psyco, dies verlangsamt den Code, aber mit psyco, beschleunigt es es auf eine ganze Menge. Mit dieser letzten Änderung ist der Code über 8x schneller 9x als das Original.
Wenn das nicht schnell genug
Dann sollten Sie wahrscheinlich wiederum ein C-Modul zu machen.
Viel Glück!
Andere Tipps
ich denke, Sie tun könnten noch besser, wenn Sie das PyLevenshtein Modul verwendet. Es ist C und recht schnell für die meisten Anwendungsfälle. Es enthält eine Jaro-winkler-Funktion, die die gleiche Leistung gibt, aber auf meinem Rechner ist es 63-mal schneller.
In [1]: import jw
In [2]: jw.winklerCompareP('ZIMMERMANN', 'CANNONS')
Out[2]: 0.41428571428571426
In [3]: timeit jw.winklerCompareP('ZIMMERMANN', 'CANNONS')
10000 loops, best of 3: 28.2 us per loop
In [4]: import Levenshtein
In [5]: Levenshtein.jaro_winkler('ZIMMERMANN', 'CANNONS')
Out[5]: 0.41428571428571431
In [6]: timeit Levenshtein.jaro_winkler('ZIMMERMANN', 'CANNONS')
1000000 loops, best of 3: 442 ns per loop
Zusätzlich zu allem, dass Justin sagt, Strings verketten ist teuer -. Python hat Speicher für die neue Zeichenfolge zuweisen kopieren Sie dann beide Strings in es
Das ist also schlecht:
ass1 = ''
for i in range(len1):
...
if (index > -1): # Found common character
...
ass1 = ass1 + str1[i]
Es wird wahrscheinlich schneller zu ASS1 und ass2 Listen von Zeichen und Verwendung ass1.append(str1[i])
zu machen. Soweit ich mit ASS1 und ass2 Sie tun danach das einzige, was von meiner schnellen Lesen des Codes sehen kann, ist, durchlaufen sie Zeichen für Zeichen, so dass sie Strings nicht sein müssen. Wenn Sie Bedarf haben sie als Zeichenketten zu verwenden, später dann können Sie sie mit ''.join(ass1)
konvertieren.