Vorschläge, wie eine Abstandsberechnung zu beschleunigen

Question

Betrachten Sie die folgende Klasse:

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

ich damit den Abstand zwischen zwei Elementen eines Vektors zu berechnen. Ich im Grunde eine Instanz dieser Klasse für jede Dimension des Vektors erstellen, die diese Abstandsmessung verwendet (es sind Dimensionen, die andere Abstandsmaße verwenden). Profilierungs zeigt, dass die __call__ Funktion dieser Klasse für 90% der Laufzeit meiner knn-Implementierung macht (wer hätte das gedacht). Ich glaube nicht, es gibt jeden reinen Python Weg, um diese zu beschleunigen, aber vielleicht, wenn ich es in C implementieren?

Wenn ich ein einfaches C-Programm ausführen, dass nur berechnet Entfernungen für Zufallswerte der obigen Formel verwendet, ist es um Größenordnungen schneller als Python. Also habe ich versucht, mit ctypes und eine C-Funktion aufrufen, die die Berechnung der Fall ist, aber anscheinend die Umwandlung die Parameter und Rückgabewerte ist viel zu teuer, da der resultierende Code sehr viel langsamer ist.

Ich könnte natürlich die gesamte knn in C implementieren und rufen Sie nur das, aber das Problem ist, dass, wie ich beschrieben, verwende ich unterschiedliche Abstandsfunktionen für einige Dimension der Vektoren, und diese C übersetzen wäre zu viel Arbeit .

Also, was sind meine Alternativen? Wird das Schreiben der C-Funktion, um den Python C-API des Kopfes loswerden? Gibt es andere Möglichkeiten, um diese Berechnung zu beschleunigen?

Answer 1

Der folgende cython Code (Ich weiß, die erste Zeile des __init__ ist anders, ich habe es mit random stuff ersetzt, weil ich var nicht wissen, und weil es keine Rolle, trotzdem tut - Sie erklären __call__ den Engpass ist):

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

Zusammengestellt über einen einfachen setup.py (nur das Beispiel aus die Dokumentation mit dem Dateinamen verändert), führt er fast 20-mal besser als der äquivalent reine Python in einfach contrieved timeit Benchmark. Beachten Sie, dass die einzige geändert wurden cdefs für das _norm Feld und die __call__ Parameter. Ich halte das für ziemlich beeindruckend.

Answer 2

Dies wird wahrscheinlich nicht viel helfen, aber Sie können es neu schreiben verschachtelte Funktionen:

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