اقتراحات حول كيفية تسريع حساب المسافة

Question

النظر في الفصل التالي:

class SquareErrorDistance(object):
    def __init__(self, dataSample):
        variance = var(list(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, u, v): # u and v are floats
        return (u - v) ** 2 * self._norm

أستخدمه لحساب المسافة بين عنصرين من المتجه. أقوم أساسًا بإنشاء مثيل واحد من تلك الفئة لكل بُعد للمتجه الذي يستخدم مقياس المسافة هذا (هناك أبعاد تستخدم مقاييس المسافة الأخرى). يكشف التنميط أن __call__ تمثل وظيفة هذه الفئة 90 ٪ من وقت تشغيل تنفيذ KNN (الذي كان يفكر). لا أعتقد أن هناك أي وسيلة نقية لتسريع هذا الأمر ، ولكن ربما إذا قمت بتطبيقه في ج؟

إذا قمت بتشغيل برنامج C بسيط يحسب مسافات للقيم العشوائية باستخدام الصيغة أعلاه ، فهو أوامر ذات حجم أسرع من Python. لذلك حاولت استخدام ctypes واتصل بوظيفة C التي تقوم بالحساب ، ولكن يبدو أن تحويل المعلمات وقيم الإرجاع باهظة الثمن ، لأن الكود الناتج أبطأ بكثير.

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

إذن ما هي بدائلي؟ سوف تكتب الوظيفة C باستخدام بيثون C-api تخلص من النفقات العامة؟ هل هناك أي طرق أخرى لتسريع هذا الحساب؟

Answer 1

رمز Cython التالي (أدرك السطر الأول من __init__ مختلف ، لقد استبدلته بأشياء عشوائية لأنني لا أعرف var ولأنه لا يهم على أي حال - ذكرت __call__ هو عنق الزجاجة):

cdef class SquareErrorDistance:
    cdef double _norm

    def __init__(self, dataSample):
        variance = round(sum(dataSample)/len(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, double u, double v): # u and v are floats
        return (u - v) ** 2 * self._norm

تم تجميعها عبر setup.py بسيط (فقط المثال من المستندات مع تغيير اسم الملف) ، فإنه يؤدي ما يقرب من 20 مرة من الثعبان النقي المكافئ في contrieved البسيطة timeit معيار. لاحظ أن التغير الوحيد كان cdefق ل _norm الحقل و __call__ المعلمات. أنا أعتبر هذا مثيرًا للإعجاب.

Answer 2

ربما لن يساعد هذا كثيرًا ، ولكن يمكنك إعادة كتابته باستخدام وظائف متداخلة:

def SquareErrorDistance(dataSample):
    variance = var(list(dataSample))
    if variance == 0:
        def f(u, v):
            x = u - v
            return x * x
    else:
        norm = 1.0 / (2 * variance)
        def f(u, v):
            x = u - v
            return x * x * norm
    return f