طلب تحسين أداء Python لـ Winkler

Question

أنا بيثون 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

Answer 1

لقد ركزت أكثر على التحسين للحصول على أكثر من 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.

حظا طيبا وفقك الله!

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