请求提升Winkler的Python性能
我刚开始学Python，想请教一下大家，有什么建议可以让这个计算两个名字之间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
3 个回答
除了Justin说的那些，连接字符串是比较耗费资源的——Python需要为新的字符串分配内存，然后把两个字符串都复制到这个新字符串里。
所以这样做不好：
ass1 = ''
for i in range(len1):
...
if (index > -1): # Found common character
...
ass1 = ass1 + str1[i]
更快的方法是把ass1和ass2做成字符列表，然后用ass1.append(str1[i])来添加字符。从我快速浏览代码的情况来看，之后你对ass1和ass2的操作只是逐个字符地遍历，所以它们不需要是字符串。如果你之后确实需要把它们当作字符串使用，可以用''.join(ass1)来转换。
我想如果你使用PyLevenshtein这个模块，效果会更好。这个模块是用C语言写的，速度很快，适合大多数情况。它里面有一个叫做jaro-winkler的函数，能给出相同的结果，但在我的电脑上，它的速度快了63倍。
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
我更关注如何让Python运行得更快，而不是优化算法，因为我觉得在算法上没有太多可以改进的地方。下面是我想到的一些Python优化方法。
(1). 由于你似乎在使用Python 2.x，把所有的range()改成xrange()。因为range()会在开始时生成一个完整的数字列表，而xrange()是根据需要一个一个生成的。
(2). 对于max和min，做以下替换：
start = max(0,i-halflen)
用
start = i - halflen if i > halflen else 0
和
end = min(i+halflen+1,len2)
用
end = i+halflen+1 if i+halflen+1 < len2 else len2
在第一个循环中，第二个循环也类似。函数的开头还有一个max()，后面还有一个min()，也要做同样的替换。替换这些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
用
for same in xrange(minlen):
if str1[same] != str2[same]:
break
这样做的主要原因是，str1[:same]在每次循环时都会创建一个新字符串，而你会检查已经检查过的部分。而且，如果我们不需要检查'' != ''，就没有必要在之后减少same的值。
(5). 使用psyco，这是一种即时编译器。下载并安装后，只需在文件顶部添加以下几行
import psyco
psyco.full()
就可以使用它。不要在没有做我提到的其他更改的情况下使用psyco。奇怪的是，当我在你的原始代码上运行它时，反而让代码变慢了。
使用timeit测试后，我发现前四个更改能让运行时间减少大约20%。但是，当我把psyco和这些更改一起使用时，代码的速度比原来的快了大约3到4倍。
如果你想要更快的速度
剩下的时间大部分花在字符串的find()方法上。我决定尝试用我自己的方法替换它。在第一个循环中，我把
index = workstr2.find(str1[i],start,end)
替换为
index = -1
for j in xrange(start,end):
if workstr2[j] == str1[i]:
index = j
break
第二个循环也用类似的方式。没有psyco时，这会让代码变慢，但有了psyco后，速度会快很多。经过这个最终的更改，代码的速度比原来的快了大约8到9倍。
如果这还不够快
那你可能需要考虑做一个C模块。
祝你好运！