Запрос на улучшение производительности Python для Winkler

Question

Я Python N00B, и я хотел бы, чтобы некоторые предложения о том, как улучшить алгоритм для повышения производительности этого метода для вычисления расстояния Джоу-Винклера двух имен.

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). Поскольку вы, кажется, используете Python 2.x, измените все диапазон () для xrange (). Диапазон () генерирует полный список чисел до итерации над ними, когда 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 () рядом с началом функции, поэтому делают то же самое с тем. Замена мин () и MAX () действительно помогла сократить время. Это удобные функции, но более дорогое, чем метод, с которым я их заменил.

(3). Используйте Common1 вместо Len (ass1). Вы отслеживаете отслеживание длины Ass1 в Common1, поэтому давайте использовать его, а не вызывать дорогостоящую функцию, чтобы найти его снова.

(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, я обнаружил, что я получаю снижение во времени около 20% или около того с первыми 4 изменениями. Однако, когда я добавляю Psyco наряду с этими изменениями, код примерно в 3 раза до 4x быстрее, чем оригинал.

Если вы хотите больше скорости

Справедливое количество оставшегося времени находится в методе 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, он скоро ускоряет его. С этим окончательным изменением код примерно в 8x до 9X быстрее, чем оригинал.

Если это не достаточно быстро

Тогда вы, вероятно, должны обратиться к созданию модуля C.

Удачи!

Answer 2

Предлагаю, что вы можете сделать еще лучше, если вы использовали модуль 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

Answer 3

Помимо всего, что говорит Джастин, объединяющие строки дороги - 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).