طريقة الأمثل لحساب المسافة جيب التمام في بيثون

Question

وكتبت طريقة لحساب المسافة جيب التمام بين اثنين من صفائف:

def cosine_distance(a, b):
    if len(a) != len(b):
        return False
    numerator = 0
    denoma = 0
    denomb = 0
    for i in range(len(a)):
        numerator += a[i]*b[i]
        denoma += abs(a[i])**2
        denomb += abs(b[i])**2
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

ويمكن تشغيل ذلك تكون بطيئة جدا على مجموعة كبيرة. هناك إصدار الأمثل لهذه الطريقة من شأنها أن تعمل بشكل أسرع؟

تحديث: لقد حاولت كل الاقتراحات حتى الآن، بما في ذلك scipy. وهنا نسخة للفوز، وتتضمن اقتراحات من مايك وستيف:

def cosine_distance(a, b):
    if len(a) != len(b):
        raise ValueError, "a and b must be same length" #Steve
    numerator = 0
    denoma = 0
    denomb = 0
    for i in range(len(a)):       #Mike's optimizations:
        ai = a[i]             #only calculate once
        bi = b[i]
        numerator += ai*bi    #faster than exponent (barely)
        denoma += ai*ai       #strip abs() since it's squaring
        denomb += bi*bi
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

Answer 1

إذا يمكنك استخدام SciPy، يمكنك استخدام cosine من spatial.distance:

<لأ href = "HTTP: // مستندات .scipy.org / وثيقة / scipy / إشارة / spatial.distance.html "يختلط =" noreferrer "> http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

إذا لا يمكنك استخدام SciPy، هل يمكن أن محاولة الحصول على تسريع صغيرة عن طريق إعادة كتابة بك بيثون (تحرير: ولكنه لم ينجح في مسعاه مثل اعتقدت انه سيكون، انظر أدناه).

from itertools import izip
from math import sqrt

def cosine_distance(a, b):
    if len(a) != len(b):
        raise ValueError, "a and b must be same length"
    numerator = sum(tup[0] * tup[1] for tup in izip(a,b))
    denoma = sum(avalue ** 2 for avalue in a)
    denomb = sum(bvalue ** 2 for bvalue in b)
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

ومن الأفضل أن رفع استثناء عند أطوال أ و ب متطابقة.

وباستخدام تعابير مولد داخل المكالمات إلى sum() يمكنك حساب القيم الخاصة بك مع معظم العمل الذي تقوم به رمز C داخل بيثون. هذا ينبغي أن يكون أسرع من استخدام حلقة for.

وأنا لم توقيت هذا ما لا أستطيع أن أخمن كيف أسرع بكثير قد يكون. لكن رمز SciPy ويكاد يكون من المؤكد مكتوب في C أو C ++ وينبغي أن يكون حول بأسرع ما يمكن الحصول عليه.

إذا كنت تفعل المعلوماتية الحيوية في بيثون، هل حقا يجب أن تستخدم SciPy على أي حال.

وتحرير: داريوس بيكون توقيت قانون بلدي وجدت أنه أبطأ. لذلك أنا توقيت قانون بلدي و... نعم، فمن أبطأ. الدرس للجميع: عندما كنت في محاولة لتسريع الامور، لا تخمين وقياس

وأنا في حيرة لماذا محاولة مني لوضع المزيد من العمل على الأجزاء الداخلية من C بيثون أبطأ. حاولت للقوائم طول 1000 وكان لا يزال أبطأ.

وأنا لا يمكن أن تنفق المزيد من الوقت على محاولة الإختراق بيثون بذكاء. اذا كنت بحاجة الى مزيد من السرعة، أقترح عليك محاولة SciPy.

وتحرير: أنا مجرد اختبار من جهة، دون timeit. أجد أن لمسافة قصيرة وب، رمز القديم هو أسرع. لفترة طويلة وب، والقانون الجديد هو أسرع. في كلتا الحالتين الفرق ليس كبيرا. (أنا أتساءل الآن ما اذا كان يمكنني الوثوق timeit على جهاز الكمبيوتر ويندوز لي؛ فأنا أريد أن أجرب هذا الاختبار مرة أخرى على لينكس) وأود أن لا تغيير قانون العمل لمحاولة الحصول عليها بشكل أسرع. واحد مزيد من الوقت وأحثكم على محاولة SciPy. : -)

Answer 2

و(اعتقدت في البداية) كنت لن تسريع العملية الكثير دون الخروج إلى C (مثل نمباي أو scipy) أو تغيير ما كنت احسب. ولكن هنا كيف كنت تحاول ذلك، على أي حال:

from itertools import imap
from math import sqrt
from operator import mul

def cosine_distance(a, b):
    assert len(a) == len(b)
    return 1 - (sum(imap(mul, a, b))
                / sqrt(sum(imap(mul, a, a))
                       * sum(imap(mul, b, b))))

وانها تقريبا ضعف سرعة في بيثون 2.6 مع صفائف 500K عنصر. (بعد تغيير الخريطة لIMAP، بعد جارت هاردي).

وهنا نسخة أنب من القانون المعدل الملصق الأصلي:

from itertools import izip

def cosine_distance(a, b):
    assert len(a) == len(b)
    ab_sum, a_sum, b_sum = 0, 0, 0
    for ai, bi in izip(a, b):
        ab_sum += ai * bi
        a_sum += ai * ai
        b_sum += bi * bi
    return 1 - ab_sum / sqrt(a_sum * b_sum)

وانها قبيحة، لكنها لا تأتي بشكل أسرع. . .

تعديل: و محاولة Psyco ! فإنه يسرع النسخة النهائية من قبل عامل آخر من 4. كيف يمكن أن أنسى؟

Answer 3

لا حاجة لاتخاذ abs() من a[i] وb[i] إذا كنت تربع عليه.

ومخزن a[i] وb[i] في المتغيرات المؤقتة، لتجنب القيام فهرسة أكثر من مرة. ربما المترجم يمكن تحسين هذا، ولكن ربما لا.

وتحقق في مشغل **2. هو تبسيط قبل أن تتحول إلى ضرب، أو باستخدام وظيفة السلطة العامة (تسجيل - ضرب من قبل 2 - antilog).

لا تفعل الجذر التربيعي مرتين (على الرغم من أن تكلفة هذا صغيرة). هل sqrt(denoma * denomb).

Answer 4

وعلى غرار الجواب داريوس بيكون، لقد تم اللعب مع المشغل وitertools لإنتاج إجابة أسرع. وفيما يلي يبدو أن 1/3 أسرع على 500 البند وفقا لمجموعة timeit:

from math import sqrt
from itertools import imap
from operator import mul

def op_cosine(a, b):
    dot_prod = sum(imap(mul, a, b))
    a_veclen = sqrt(sum(i ** 2 for i in a))
    b_veclen = sqrt(sum(i ** 2 for i in b))

    return 1 - dot_prod / (a_veclen * b_veclen)

Answer 5

وهذا هو أسرع لصفائف حول 1000+ العناصر.

from numpy import array
def cosine_distance(a, b):
    a=array(a)
    b=array(b)
    numerator=(a*b).sum()
    denoma=(a*a).sum()
    denomb=(b*b).sum()
    result = 1 - numerator / sqrt(denoma*denomb)
    return result

Answer 6

وباستخدام رمز C داخل يفوز SciPy كبير لصفائف إدخال طويلة. باستخدام بيثون بسيطة ومباشرة يفوز للصفائف مدخلات قصيرة. إجراء مقارنة معيارية كود القائم على izip() داريوس بيكون من أفضل. وهكذا، فإن الحل النهائي هو قرار واحد للاستخدام في وقت التشغيل، استنادا إلى طول صفائف المدخلات:

from scipy.spatial.distance import cosine as scipy_cos_dist

from itertools import izip
from math import sqrt

def cosine_distance(a, b):
    len_a = len(a)
    assert len_a == len(b)
    if len_a > 200:  # 200 is a magic value found by benchmark
        return scipy_cos_dist(a, b)
    # function below is basically just Darius Bacon's code
    ab_sum = a_sum = b_sum = 0
    for ai, bi in izip(a, b):
        ab_sum += ai * bi
        a_sum += ai * ai
        b_sum += bi * bi
    return 1 - ab_sum / sqrt(a_sum * b_sum)

ولقد تقدمت تسخير اختبار اختبار وظائف مع مختلف المدخلات طول، وجدت أن ما يقرب من طول 200 بدأت وظيفة SciPy للفوز. وأكبر صفائف المدخلات، وأكبر فوزها. للصفائف طول قصيرة جدا، ويقول طول 3، يفوز رمز أبسط. هذه الوظيفة يضيف كمية ضئيلة من النفقات العامة أن تقرر أي طريقة للقيام بذلك، ثم يفعل ذلك أفضل وسيلة.

في حال كنت مهتما، وهنا هو تسخير اختبار:

from darius2 import cosine_distance as fn_darius2
fn_darius2.__name__ = "fn_darius2"

from ult import cosine_distance as fn_ult
fn_ult.__name__ = "fn_ult"

from scipy.spatial.distance import cosine as fn_scipy
fn_scipy.__name__ = "fn_scipy"

import random
import time

lst_fn = [fn_darius2, fn_scipy, fn_ult]

def run_test(fn, lst0, lst1, test_len):
    start = time.time()
    for _ in xrange(test_len):
        fn(lst0, lst1)
    end = time.time()
    return end - start

for data_len in range(50, 500, 10):
    a = [random.random() for _ in xrange(data_len)]
    b = [random.random() for _ in xrange(data_len)]
    print "len(a) ==", len(a)
    test_len = 10**3
    for fn in lst_fn:
        n = fn.__name__
        r = fn(a, b)
        t = run_test(fn, a, b, test_len)
        print "%s:\t%f seconds, result %f" % (n, t, r)

Answer 7

def cd(a,b):
    if(len(a)!=len(b)):
        raise ValueError, "a and b must be the same length"
    rn = range(len(a))
    adb = sum([a[k]*b[k] for k in rn])
    nma = sqrt(sum([a[k]*a[k] for k in rn]))
    nmb = sqrt(sum([b[k]*b[k] for k in rn]))

    result = 1 - adb / (nma*nmb)
    return result

Answer 8

والحل النسخة المحدثة من لا يزال لديه اثنين من الجذور التربيعية. يمكنك تقليل هذا واحد عن طريق استبدال خط الجذر التربيعي مع:

<اقتباس فقرة>   

ونتيجة = 1 - البسط /   (الجذر التربيعي (denoma * denomb))

ووتتكاثر عادة أسرع قليلا جدا من الجذر التربيعي. قد لا يبدو كثيرا كما يطلق عليه مرة واحدة فقط في وظيفة، ولكن يبدو وكأنك حساب الكثير من المسافات جيب التمام، وبالتالي فإن تحسين تضيف ما يصل.

والتعليمات البرمجية يبدو أنه يجب أن يكون قد حان لأمثل النواقل. إذا كان الأمر كذلك الدعم عبر platofrm ليست قضية وتريد تسريع أبعد من ذلك، هل يمكن أن رمز رمز المسافة جيب التمام في C والتأكد من المترجم الخاص بك هو كمية موجهة بقوة رمز الناتج (حتى بنتيوم II قادر على بعض العائمة vectorisation نقطة )