winkler的Python性能改进请求

我是一个 python n00b，我想要一些关于如何改进算法的建议，以提高计算两个名字的 Jaro-Winkler 距离的方法的性能。

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

输出示例

ZIMMERMANN  ARMIENTO    0.814583333
ZIMMERMANN  ZIMMERMANN  1
ZIMMERMANN  CANNONS         0.766666667
CANNONS AKKER           0.8
CANNONS ALDERSON    0.845833333
CANNONS ALLANBY         0.833333333

我更注重优化以从 Python 中获得更多好处，而不是优化算法，因为我认为这里不需要进行太多算法改进。以下是我提出的一些 Python 优化。

(1).由于您似乎使用的是 Python 2.x，因此将所有 range() 更改为 xrange()。 range() 在迭代之前生成完整的数字列表，而 xrange 根据需要生成它们。

（2）。对 max 和 min 进行以下替换：

start = max(0,i-halflen)

with

start = i - halflen if i > halflen else 0

and

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

with

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

在第一个循环中，在第二个循环中类似。在函数开头附近还有一个 min() 和一个 max() ，因此对它们执行相同的操作。替换 min() 和 max() 确实有助于减少时间。这些都是方便的功能，但比我替换它们的方法成本更高。

（3）。使用 common1 而不是 len(ass1)。您已经跟踪了 common1 中 ass1 的长度，因此让我们使用它，而不是调用昂贵的函数来再次查找它。

（4）。替换以下代码：

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

with

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

其原因主要是 str1[:same] 每次通过循环都会创建一个新字符串，并且您将检查已经检查过的部分。另外，无需检查是否'' != ''并减少same之后如果我们不需要的话。

（5）。使用psyco http://psyco.sourceforge.net/，一种即时编译器。下载并安装后，只需添加以下行

import psyco
psyco.full()

位于文件顶部以使用它。除非您进行了我提到的其他更改，否则不要使用 psyco。由于某种原因，当我在原始代码上运行它时，它实际上减慢了速度。

使用 timeit，我发现前 4 次更改的时间减少了约 20% 左右。然而，当我添加 psyco 以及这些更改时，代码比原始代码快大约 3 到 4 倍。

如果你想要更快的速度

相当多的剩余时间都在字符串的 find() 方法中。我决定尝试用我自己的替换它。对于第一个循环，我替换了

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

with

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

第二个循环也有类似的形式。如果没有 psyco，这会减慢代码速度，但是有了 psyco，它会大大加快速度。经过最后的更改，代码比原始代码快大约 8 到 9 倍。

如果这还不够快

那么您可能应该转向制作 C 模块。

祝你好运！