logo标签列表

Python性能改进请求：针对Winkler的建议

pythonoptimizationperformancejaro-winkler
4

我是一名 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
如果您能提供一些示例，例如一些名称对和正确的分数，那将非常有帮助。否则很难知道我们的编辑是否破坏了函数。 - JudoWill
感谢您编辑问题。我会获取那些例子。 - Martlark
我在我的示例案例中没有得到与您相同的输出（除非字符串完全相同），但我从Jaro-Winkler距离维基百科页面尝试的示例中，w是正确的。 - Justin Peel
我的输出有误，我会尽快修复。非常抱歉。 - Martlark
感谢所有的评论。最终我用C重写了它，速度快多了。 - Martlark
3个回答
4

我想如果你使用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
pypy 1.6可以使原始代码（实际上是从Febrl获取的：http://sf.net/projects/febrl）运行速度提高10倍。只需要再多给它一点时间 :) - sayap
我最终使用C语言制作了一个Python模块，速度快了很多，并且修复了一个逻辑错误。感谢您的建议。 - Martlark
4

我更加注重优化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

在第一个循环中以及类似于第二个循环的地方，有另一个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

使用

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 模块。

祝好运！

这些更改在没有使用pysco的情况下将我的测试脚本的性能提高了25％。谢谢！ - Martlark
xrange和range在使用Python 2.6.5时似乎没有太大区别。 - Martlark
是的，也许是这样。我还没有真正看过2.6.5中的更改。此外，我们并没有使用非常大的范围，因此不应该有太大的影响。使用xrange的原因是它在迭代之前不会在内存中形成整个列表。相反，它会根据需要生成每个元素。 - Justin Peel
0
除了Justin所说的一切，字符串拼接是很耗费资源的 - Python必须为新字符串分配内存，然后将两个字符串复制到其中。
所以这是不好的：
ass1 = ''
for i in range(len1):
     ...
    if (index > -1):    # Found common character
        ...
        ass1 = ass1 + str1[i]

将ass1和ass2作为字符列表，并使用ass1.append(str1[i])可能会更快。就我对代码的快速阅读所看到的，您之后所做的唯一事情是逐个字符地迭代访问它们，因此它们不需要是字符串。如果您之后确实需要将它们用作字符串，那么可以使用''.join(ass1)进行转换。

我尝试创建ass1和ass2列表，但它使程序变慢了，这让我感到惊讶。我还尝试创建workstr1和workstr2列表，但也使程序变慢了。我真的以为至少其中一个会有所帮助，但字符串连接可能非常快或其他原因导致程序变慢。 - Justin Peel
我在这样做时没有注意到任何加速。 - Martlark
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接