Python Leistungsverbesserung Anfrage für winkler

Question

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

Answer 1

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!

Answer 2

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

Answer 3

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.