Python richiesta miglioramento delle prestazioni per Winkler

Question

Sono un n00b pitone e vorrei qualche suggerimento su come migliorare l'algoritmo per migliorare le prestazioni di questo metodo per calcolare la distanza Jaro-Winkler di due nomi.

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

uscita Esempio

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

mi sono concentrato di più su come ottimizzare per ottenere di più da Python rispetto all'ottimizzazione dell'algoritmo, perché non credo che ci sia molto di un miglioramento algoritmico per essere avuto qui. Qui ci sono alcune ottimizzazioni Python che mi è venuta.

(1). Dal momento in cui sembra essere utilizzando Python 2.x, cambiare tutto range () 's per xrange) (' s. range () genera l'elenco completo dei numeri prima iterazione su di loro mentre xrange li genera in base alle esigenze.

(2). Effettuare le seguenti sostituzioni per max e min:

start = max(0,i-halflen)

con

start = i - halflen if i > halflen else 0

e

end = min(i+halflen+1,len2)

con

end = i+halflen+1 if i+halflen+1 < len2 else len2

nel primo ciclo e altre simili per il secondo ciclo. C'è anche un altro min () più in basso e un massimo (), vicino l'inizio della funzione in modo da fare lo stesso con quelli. Sostituzione del min) 's e max ()' (S davvero ha contribuito a ridurre il tempo. Si tratta di funzioni utili, ma più costoso rispetto al metodo li ho sostituiti con.

(3). Uso common1 invece di len (ASS1). Hai tenuto traccia della lunghezza di ASS1 in common1 quindi cerchiamo di usarlo, piuttosto che chiamare una funzione costosa per trovare di nuovo.

(4). Sostituire il seguente codice:

minlen = min(len1,len2)
for same in xrange(minlen+1):
    if (str1[:same] != str2[:same]):
        break
same -= 1

con

for same in xrange(minlen):
    if str1[same] != str2[same]:
        break

La ragione di questo è soprattutto che str1 [: stesso] crea una nuova stringa ogni volta attraverso il ciclo e sarai controllando le parti che hai già controllato. Inoltre, non c'è bisogno di controllare se '' != '' e decremento same seguito se non abbiamo a.

(5). Usa Psyco , un compilatore just-in-time di sorta. Una volta scaricato e installato, è sufficiente aggiungere le righe

import psyco
psyco.full()

nella parte superiore del file di usarlo. Non utilizzare Psyco a meno che non si fanno le altre modifiche che ho citato. Per qualche ragione, quando mi sono imbattuto sul vostro codice originale in realtà rallentato verso il basso.

Utilizzando timeit, ho scoperto che mi è stato sempre una diminuzione del tempo di circa il 20% o giù di lì con i primi 4 modifiche. Tuttavia, quando aggiungo psyco insieme a tali modifiche, il codice è di circa 3 volte a 4 volte più veloce di quella originale.

Se volete maggiori velocità

Una discreta quantità di tempo rimanente è nella scoperta della stringa () metodo. Ho deciso di provare a sostituire questo con la mia. Per il primo ciclo, ho sostituito

index = workstr2.find(str1[i],start,end)

con

index = -1
for j in xrange(start,end):
    if workstr2[j] == str1[i]:
        index = j
        break

e una forma simile per il secondo ciclo. Senza psyco, questo rallenta il codice, ma con Psyco, accelera in su un bel po '. Con questa modifica il codice finale è di circa 8x a 9x più veloce rispetto all'originale.

Se questo non è abbastanza veloce

allora probabilmente si dovrebbe girare a fare un modulo C.

In bocca al lupo!

Answer 2

immagino che si possa fare ancora meglio se si è utilizzato il modulo PyLevenshtein. E 'C e abbastanza veloce per la maggior parte dei casi d'uso. Esso include una funzione di Jaro-Winkler che dà la stessa uscita, ma sulla mia macchina è 63 volte più veloce.

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

In aggiunta a tutto ciò che Justin dice, concatenazione di stringhe è costoso -. Python deve allocare memoria per la nuova stringa quindi copiare entrambe le stringhe in esso

Quindi questo è un male:

ass1 = ''
for i in range(len1):
     ...
    if (index > -1):    # Found common character
        ...
        ass1 = ass1 + str1[i]

Sarà probabilmente più veloce per fare ASS1 e ASS2 elenchi di personaggi e uso ass1.append(str1[i]). Per quanto posso vedere dalla mia lettura veloce del codice l'unica cosa che si fa con ASS1 e ASS2 è poi a iterare attraverso di loro carattere per carattere in modo che non hanno bisogno di essere stringhe. Se avuto bisogno di usarli come stringhe più tardi poi si possono convertire con ''.join(ass1).