Sugerencias sobre la manera de aumentar la velocidad de cálculo de la distancia

Question

Considere la siguiente clase:

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

lo uso para calcular la distancia entre dos elementos de un vector. Yo, básicamente, crear una instancia de esa clase para cada dimensión del vector que utiliza esta medida de distancia (hay dimensiones que utilizan otras medidas de distancia). Perfilado revela que la función __call__ de esta clase representa el 90% del tiempo de funcionamiento de mi knn-aplicación (¿quién habría pensado). No creo que hay alguna forma pura-Python para acelerar este proceso, pero tal vez si puedo implementar en C?

Si me quedo un sencillo programa C que sólo calcula distancias y valores aleatorios utilizando la fórmula anterior, que es varios órdenes de magnitud más rápido que Python. Así que he intentado usar ctypes y llamar a una función de C que hace el cálculo, pero al parecer la conversión de los parámetros y valores de retorno está lejos de caro, ya que el código resultante es mucho más lento.

I de podría implementar supuesto toda la knn en C y simplemente llame que, pero el problema es que, como he descrito, utilizo diferentes funciones de distancia por alguna dimensión de los vectores, y la traducción de estos para C sería demasiado trabajo .

¿Cuáles son mis alternativas? Va a escribir el C-función con la Python API C deshacerse de la cabeza? ¿Hay otras maneras de acelerar este cálculo para arriba?

Answer 1

El siguiente código Cython (realizo la primera línea de __init__ es diferente, lo sustituyó con cosas al azar porque no sé var y porque no importa de todos modos - que declaró __call__ es el cuello de botella):

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

Compilado través de un simple setup.py (justo el ejemplo de los documentos con el nombre del archivo alterado), se realiza casi 20 veces mejor que la pitón puro equivalente en un simple punto de referencia timeit contrieved. Tenga en cuenta que el único cambió eran cdefs para el campo _norm y los parámetros __call__. Considero que esto es bastante impresionante.

Answer 2

Esto probablemente no ayuda mucho, pero se puede volver a escribir usando funciones anidadas:

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