WinklerのPythonパフォーマンス改善要求
-
02-10-2019 - |
質問
私はPython N00Bです。アルゴリズムを改善してこの方法のパフォーマンスを改善して、2つの名前の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を使用しているように見えるので、すべての範囲()を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
2番目のループの最初のループと同様のループで。また、関数の先頭近くにさらに下にあるMIN()とMAX()もありますので、それらで同じことをします。 min()とmax()を置き換えると、時間を短縮するのに役立ちました。これらは便利な機能ですが、私がそれらを置き換えた方法よりもコストがかかります。
(3)。 len(ass1)の代わりにcommon1を使用します。 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
その後、必要がない場合。
(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
2番目のループの同様のフォーム。 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)
.