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

Я - питон 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
Источник

3 ответа

Решение

Я сосредоточился больше на оптимизации, чтобы получить больше от 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). Вы отследили длину 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] каждый раз создает новую строку в цикле, и вы будете проверять уже проверенные детали. Кроме того, нет необходимости проверять, '' != '' и декремент same потом, если мы не должны.

(5). Используйте psyco, компилятор как раз вовремя. Как только вы загрузили и установили его, просто добавьте строки

import psyco
psyco.full()

в верхней части файла, чтобы использовать его. Не используйте psyco, если вы не сделаете другие изменения, которые я упомянул. По какой-то причине, когда я запустил его на вашем исходном коде, это на самом деле замедлило его.

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

Удачи!

Источник

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

Источник
Другие вопросы по тегам