demande d'amélioration de la performance Python pour winkler

Question

Je suis un n00b python et je voudrais quelques suggestions sur la façon d'améliorer l'algorithme pour améliorer les performances de cette méthode pour calculer la distance Jaro-Winkler de deux noms.

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

sortie Exemple

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

Je me suis concentré plus sur l'optimisation pour obtenir plus de Python que sur l'optimisation de l'algorithme parce que je ne pense pas qu'il y ait beaucoup d'une amélioration algorithmiques à se trouver ici. Voici quelques optimisations Python que je suis venu avec.

(1). Puisque vous semblez utiliser Python 2.x, changer toute la gamme () est à xrange () 's. range () génère la liste complète des numéros avant itérer sur eux tandis que xrange les génère au besoin.

(2). Effectuez les substitutions suivantes pour max et min:

start = max(0,i-halflen)

avec

start = i - halflen if i > halflen else 0

et

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

avec

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

dans la première boucle et autres semblables pour la deuxième boucle. Il y a aussi une autre min () plus bas et un max () vers le début de la fonction donc faire la même chose avec ceux-ci. Remplacement du min () 's et max () est vraiment aidé à réduire le temps. Ce sont des fonctions pratiques, mais plus cher que la méthode que je les ai remplacés par.

(3). Utilisation common1 au lieu de len (ASS1). Vous avez gardé la trace de la longueur de ASS1 en common1 si nous allons l'utiliser plutôt que d'appeler une fonction coûteuse pour la retrouver.

(4). Remplacez le code suivant:

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

avec

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

La raison est principalement que str1 [: même] crée une nouvelle chaîne à chaque fois dans la boucle et vous serez vérifier les pièces que vous avez déjà vérifié. En outre, il n'y a pas besoin de vérifier si '' != '' et décrément same après si nous n'avons pas.

(5). Utilisez psyco , un compilateur juste à temps de toutes sortes. Une fois que vous avez téléchargé et installé, il suffit d'ajouter les lignes

import psyco
psyco.full()

en haut du fichier à utiliser. Ne pas utiliser psyco à moins que vous ne les autres changements que je l'ai mentionné. Pour une raison quelconque, quand je l'ai couru sur votre code d'origine, il a ralenti en fait vers le bas.

En utilisant timeit, je trouve que je devenais une diminution du temps d'environ 20%, ou avec les 4 premiers changements. Cependant, quand j'ajoute psyco avec ces changements, le code est environ 3 fois 4 fois plus rapide que l'original.

Si vous voulez plus de vitesse

Un montant juste du temps restant est dans la méthode de découverte () de la chaîne. J'ai décidé d'essayer de la remplacer par moi-même. Pour la première boucle, j'ai remplacé

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

avec

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

et une forme similaire à la deuxième boucle. Sans psyco, cela ralentit le code, mais avec psyco, il l'accélère pas mal. Avec ce dernier changement du code est de 8x 9x plus rapide que l'original.

Si cela ne suffit pas rapide

Ensuite, vous devriez probablement adapterons un module C.

Bonne chance!

Answer 2

Je suppose que vous pourriez faire encore mieux si vous utilisez le module PyLevenshtein. Il est C et assez rapide pour la plupart des cas d'utilisation. Il comprend une fonction de Jaro-winkler qui donne la même sortie, mais sur ma machine, il est 63 fois plus rapide.

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

En plus de tout ce que Justin dit, cordes est cher concaténer -. Python doit allouer de la mémoire pour la nouvelle chaîne puis copiez les deux chaînes dans ce

Alors cela est mauvais:

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

Il sera probablement plus rapide de faire des listes de ASS1 et ASS2 des personnages et de l'utilisation ass1.append(str1[i]). Pour autant que je peux voir de mon lecture rapide du code de la seule chose que vous faites avec ASS1 et ASS2 est ensuite à itérer par leur caractère par caractère afin qu'ils ne doivent pas nécessairement être des chaînes. Si vous avez besoin de les utiliser comme des chaînes plus tard, alors vous pouvez les convertir en ''.join(ass1).