Запрос на улучшение производительности Python для Winkler
-
02-10-2019 - |
Вопрос
Я 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
Решение
Я больше сосредоточил на оптимизации, чтобы получить больше из 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.
Удачи!
Другие советы
Предлагаю, что вы можете сделать еще лучше, если вы использовали модуль 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)
.