winkler的Python性能改進請求

Question

我是一個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 

Answer 1

我更專注於優化，以獲得更多的Python比對算法的優化，因爲我不認爲有多大的改進算法在這裏了。以下是我提出的一些Python優化。 （1）

（1）。由於您似乎在使用Python 2.x，所以將所有range（）更改爲xrange（）。 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（），以及一個max（），所以這些都是一樣的。替換min（）和max（）確實有助於縮短時間。這些功能很方便，但比我用它替換的方法更昂貴。

（3）。使用common1而不是len（ass1）。您已經掌握了common1中ass1的長度，因此讓我們使用它，而不是調用昂貴的函數來再次找到它。

（4）。與

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

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

這樣做的原因主要在於STR1：將以下代碼[：同]通過循環創建一個新的字符串每次和你將被檢查的部分，你」已經檢查過了。另外，如果我們不需要，則不需要檢查'' != ''和減少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模塊。

祝你好運！

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