WinklerのPythonパフォーマンス改善要求

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

質問

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top