suggestions sur la façon d'accélérer un calcul de la distance

Question

Considérez la classe suivante:

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 

Je l'utilise pour calculer la distance entre deux éléments d'un vecteur. Je crée fondamentalement une instance de cette classe pour chaque dimension du vecteur qui utilise cette mesure de distance (il existe des dimensions qui utilisent d'autres mesures de distance). Le profilage révèle que la fonction __call__ de cette classe représente 90% du temps d'exécution de mon knn-implémentation (qui aurait pensé). Je ne pense pas qu'il existe un moyen pur-Python pour accélérer cela, mais peut-être si je l'implémente en C?

Si j'exécute un simple programme C qui calcule simplement les distances pour des valeurs aléatoires en utilisant la formule ci-dessus, il est plus rapide que Python. J'ai donc essayé d'utiliser ctypes et d'appeler une fonction C qui fait le calcul, mais apparemment la conversion des paramètres et des valeurs de retour est loin d'être chère, car le code résultant est beaucoup plus lent. Je pourrais bien sûr implémenter le knn entier en C et juste l'appeler, mais le problème est que, comme je l'ai décrit, j'utilise différentes fonctions de distance pour une certaine dimension des vecteurs, et les traduire en C serait trop travail.

Alors, quelles sont mes alternatives? Est-ce que l'écriture de la fonction C en utilisant le Python C-API se débarrasser de la surcharge? Existe-t-il d'autres moyens d'accélérer ce calcul?

Answer 1

Le code cython suivant (je réalise la première ligne de __init__ est différent, je l'ai remplacé avec des trucs au hasard parce que Je ne sais pas var et parce qu'il n'a pas d'importance de toute façon - vous avez dit __call__ est le goulot d'étranglement):

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 

Compilé par un simple setup.py (juste the example from the docs avec le nom de fichier modifié), il effectue près de 20 fois mieux que le python pur équivalent dans un benchmark timeit simple et respecté. Notez que les seuls changements ont été cdef s pour le champ _norm et les paramètres __call__. Je considère que c'est assez impressionnant.

Answer 2

Ce ne sera probablement pas beaucoup d'aide, mais vous pouvez le réécrire en utilisant les fonctions imbriquées:

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