Python mejora del rendimiento solicitud de Winkler

Question

Soy un n00b pitón y me gustaría algunas sugerencias sobre cómo mejorar el algoritmo para mejorar el rendimiento de este método para calcular la distancia de Jaro-Winkler, de dos nombres.

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

Ejemplo de salida

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

Me he centrado más en la optimización para obtener más provecho de Python que en la optimización del algoritmo, porque no creo que no es mucho de una mejora algorítmica que había aquí. Aquí hay algunas optimizaciones Python que se me ocurrió.

(1). Ya que parecen estar utilizando Python 2.x, cambiar toda la gama () 's a xrange (s)'. range () genera la lista completa de los números antes de iterar sobre ellos, mientras que los genera xrange según sea necesario.

(2). Realiza las siguientes sustituciones de max y min:

start = max(0,i-halflen)

con

start = i - halflen if i > halflen else 0

y

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

con

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

en el primer bucle y otros similares para el segundo bucle. También hay otro min () más abajo y una max () cerca del comienzo de la función así hacer lo mismo con los. Sustitución de la min) 's y MAX ()' (es realmente ayudó a reducir el tiempo. Estas son funciones convenientes, pero más costosa que el método que les he sustituido con.

(3). Uso common1 en lugar de len (ASS1). Usted ha mantenido un seguimiento de la longitud de ASS1 en common1 así que vamos a utilizar en lugar de llamar a una función costosa para encontrarla de nuevo.

(4). Vuelva a colocar el siguiente código:

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 razón de esto se debe principalmente a que str1 [: igual] crea una nueva cadena cada vez que a través del bucle y se va a controlar partes que ya ha comprobado. Además, no hay necesidad de comprobar si '' != '' y same decremento después si nos no tienen que hacerlo.

(5). Uso psyco , un compilador justo a tiempo de clases. Una vez que haya descargado e instalado, sólo tiene que añadir las líneas

import psyco
psyco.full()

en la parte superior del archivo de usarlo. No utilice psyco menos que hacer los otros cambios que he mencionado. Por alguna razón, cuando me encontré con él en su código original que en realidad se desaceleró hacia abajo.

Uso timeit, he encontrado que estaba recibiendo una disminución en el tiempo de aproximadamente 20% o así con los primeros 4 cambios. Sin embargo, cuando agrego psyco junto con esos cambios, el código es de aproximadamente 3 veces a 4 veces más rápido que el original.

Si quieres más velocidad

Una buena cantidad de tiempo restante es en el método find () de la cadena. Decidí intentar reemplazar esto con mi propia. Para el primer bucle, Substituí

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

con

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

y una forma similar para el segundo bucle. Sin psyco, esto ralentiza el código, pero con psyco, que lo acelera mucho. Con este cambio final del código es de 8x a 9x más rápido que el original.

Si eso no es lo suficientemente rápido

A continuación, se debe, probablemente, a su vez hacer un módulo C.

Buena suerte!

Answer 2

Me imagino que podría hacer aún mejor si se ha utilizado el módulo PyLevenshtein. Es C y bastante rápido para la mayoría de los casos de uso. Incluye una función de Jaro-Winkler que da la misma salida, pero en mi máquina es 63 veces más rápido.

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

Además de todo lo que Justin dice, la concatenación de cadenas es caro -. Pitón tiene que asignar memoria para la nueva cadena a continuación, copiar las dos cadenas en ella

Así que esto es malo:

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

Probablemente será más rápido para hacer listas ASS1 y ASS2 de caracteres y el uso ass1.append(str1[i]). Por lo que puedo ver desde mi lectura rápida del código lo único que se hace con ASS1 y ASS2 después es para iterar a través de ellos carácter por carácter por lo que no tienen que ser cadenas. Si lo hizo necesidad de utilizarlos como cadenas, más adelante, entonces puede convertirlos con ''.join(ass1).