python的绩效改进请求Winkler

StackOverflow https://stackoverflow.com/questions/2741872

题

我是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，因此将所有范围（）的s更改为Xrange（）s。 range（）在Xrange根据需要生成它们的同时生成数字的完整列表。

（2）。进行以下最大和最小的替换：

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

在第一个循环中，第二个循环的类似循环。在功能开头附近还有另一个min（）距离，最大为（），因此与这些功能相同。替换Min（）和Max（）的s确实有助于减少时间。这些是方便的功能，但比我替换的方法更为昂贵。

（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，我发现在前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模块。

祝你好运！

其他提示

我想如果您使用了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必须为新字符串分配内存，然后将两个字符串复制到其中。

所以这很糟糕：

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).

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top