Suggerimenti su come accelerare un calcolo della distanza

Question

Si consideri la seguente classe:

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

Io lo uso per calcolare la distanza tra due elementi di un vettore. Io fondamentalmente creare un'istanza di tale classe per ogni dimensione del vettore che utilizza la misura della distanza (ci sono dimensioni che utilizzano altri misure di distanza). Profiling rivela che la funzione __call__ di questa classe rappresenta il 90% del rodaggio tempo del mio knn attuazione (chi avrebbe mai pensato). Io non credo che ci sia alcun modo puro Python per accelerare questo, ma forse se implementarlo in C?

Se corro un semplice programma C che solo calcola le distanze per i valori casuali utilizzando la formula di cui sopra, è ordini di grandezza più veloce di Python. Così ho provato ad utilizzare ctypes e chiamare una funzione C che fa il calcolo, ma a quanto pare la conversione dei parametri e valori di ritorno è molto costoso, perché il codice risultante è molto più lento.

I potrebbe naturalmente implementare l'intero knn in C e basta chiamare, ma il problema è che, come ho descritto, io uso diverse funzioni di distanza per una dimensione dei vettori, e traducendo questi per C sarebbe troppo lavoro .

Quindi quali sono le mie alternative? Sarà la scrittura del C-funzione utilizzando il Python C-API sbarazzarsi della testa? Ci sono altri modi per accelerare questo calcolo su?

Answer 1

Il seguente codice Cython (mi rendo conto la prima linea di __init__ è diverso, ho sostituito con roba a caso, perché io non so var e perché non importa in ogni caso - si afferma __call__ è il collo di bottiglia):

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

Compilato tramite un semplice setup.py (basta l'esempio la documentazione con il nome di file modificato), si effettua quasi 20 volte meglio del pitone puro equivalente in un semplice riferimento timeit contrieved. Si noti che l'unica cambiato erano cdefs per il campo _norm ei parametri __call__. Considero questo abbastanza impressionante.

Answer 2

Questo probabilmente non aiuterà molto, ma si può riscrivere usando funzioni annidate:

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