Python性能提升请求win

Question

我是python00b，我想要一些关于如何改进算法的建议，以提高这种方法计算两个名称的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

输出示例

^{pr2}$

Answer 1

我更关注于优化Python，而不是优化算法，因为我不认为这里有多少算法上的改进。下面是我提出的一些Python优化。在

（一）。由于您似乎使用的是python2.x，所以将all range（）更改为xrange（）。range（）在迭代之前生成完整的数字列表，而xrange根据需要生成数字。在

（二）。对“最大”和“最小”进行以下替换：

start = max(0,i-halflen)

与

^{2}$

以及

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

与

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

第一个循环中的第二个和第二个相似的循环。下面还有一个min（），函数开头附近有一个max（），所以对这些函数也要做同样的处理。替换min（）和max（）确实有助于减少时间。这些都是方便的函数，但是比我替换它们的方法更昂贵。在

（三）。使用common1代替len（ass1）。您已经在common1中跟踪了ass1的长度，所以让我们使用它，而不是调用一个昂贵的函数来再次找到它。在

（四）。替换以下代码：

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]每次通过循环都会创建一个新字符串，您将检查已经检查过的部分。另外，如果我们不需要检查'' != ''和递减{}，那么就不必再检查了。在

（五）。使用psyco，一个实时编译器。一旦您下载并安装了它，只需添加行

import psyco
psyco.full()

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

使用timeit，我发现在前4个更改中，我得到了大约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模块。在

祝你好运！在

Answer 2

除了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)来转换它们。在

Answer 3

我想如果你用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