طلب تحسين أداء Python لـ Winkler
-
02-10-2019 - |
سؤال
أنا بيثون N00B وأود بعض الاقتراحات حول كيفية تحسين الخوارزمية لتحسين أداء هذه الطريقة لحساب مسافة 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 ، قم بتغيير جميع 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
في الحلقة الأولى وتشابهها للحلقة الثانية. هناك أيضًا دقيقة أخرى () أبعد وأسفل و Max () بالقرب من بداية الوظيفة ، لذا تفعل الشيء نفسه مع هؤلاء. ساعد استبدال MIN () و MAX () حقًا في تقليل الوقت. هذه وظائف مريحة ، ولكن أكثر تكلفة من الطريقة التي استبدلتها بها.
(3). استخدم Common1 بدلاً من LEN (ASS1). لقد تابعت طول ASS1 بشكل مشترك 1 ، لذلك دعونا نستخدمه بدلاً من استدعاء وظيفة مكلفة للعثور عليها مرة أخرى.
(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 ٪ أو نحو ذلك مع التغييرات الأربعة الأولى. ومع ذلك ، عندما أضيف PSYCO مع هذه التغييرات ، يكون الرمز حوالي 3x إلى 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)
.