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

Question

Considere la clase siguiente:

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. Básicamente creo una instancia de esa clase para cada dimensión del vector que usa esta medida de distancia (hay dimensiones que usan otras medidas de distancia). La creación de perfiles revela que la función __call__ de esta clase representa el 90% del tiempo de ejecución de mi implementación knn (¿quién lo hubiera pensado?). No creo que exista una forma pura de Python para acelerar esto, pero ¿tal vez si lo implemento en C?

Si ejecuto un programa simple de C que simplemente calcula distancias para valores aleatorios usando la fórmula anterior, es órdenes de magnitud más rápido que Python. Así que traté de usar ctypes y llamar a una función C que hace el cálculo, pero aparentemente la conversión de los parámetros y los valores de retorno es muy cara, porque el código resultante es mucho más lento.

Podría, por supuesto, implementar todo el knn en C y simplemente llamarlo, pero el problema es que, como he descrito, utilizo diferentes funciones de distancia para algunas dimensiones de los vectores, y traducirlas a C sería demasiado trabajo.

¿Cuáles son mis alternativas? ¿Escribir la función C usando el Python C-API eliminará la sobrecarga? ¿Hay alguna otra forma de acelerar este cálculo?

Answer 1

El siguiente código Cython (me di cuenta 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 indiqué __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 por medio de una sencilla setup.py (justo the example from the docs con el nombre del archivo alterado), se realiza casi 20 veces mejor que el python puro equivalente en un simple valor de referencia timeit. Tenga en cuenta que los únicos cambios fueron cdef s para el campo _norm y los parámetros __call__. Considero esto bastante impresionante.

Answer 2

Esto probablemente no ayudará 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