Méthode optimisée pour calculer la distance cosinus en Python

Question

J'ai écrit une méthode pour calculer la distance en cosinus entre deux tableaux:

def cosine_distance(a, b):
    if len(a) != len(b):
        return False
    numerator = 0
    denoma = 0
    denomb = 0
    for i in range(len(a)):
        numerator += a[i]*b[i]
        denoma += abs(a[i])**2
        denomb += abs(b[i])**2
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

L'exécuter peut être très lent sur un grand tableau. Existe-t-il une version optimisée de cette méthode qui serait plus rapide?

Mise à jour: j'ai déjà essayé toutes les suggestions, y compris scipy. Voici la version à battre, intégrant les suggestions de Mike et Steve:

def cosine_distance(a, b):
    if len(a) != len(b):
        raise ValueError, "a and b must be same length" #Steve
    numerator = 0
    denoma = 0
    denomb = 0
    for i in range(len(a)):       #Mike's optimizations:
        ai = a[i]             #only calculate once
        bi = b[i]
        numerator += ai*bi    #faster than exponent (barely)
        denoma += ai*ai       #strip abs() since it's squaring
        denomb += bi*bi
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

Answer 1

Si vous pouvez utiliser SciPy, vous pouvez utiliser cosinus à partir de spatial.distance :

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

Si vous ne pouvez pas utiliser SciPy, vous pouvez essayer d’obtenir une petite accélération en réécrivant votre Python (EDIT: mais cela n’a pas fonctionné comme je le pensais, voir ci-dessous).

from itertools import izip
from math import sqrt

def cosine_distance(a, b):
    if len(a) != len(b):
        raise ValueError, "a and b must be same length"
    numerator = sum(tup[0] * tup[1] for tup in izip(a,b))
    denoma = sum(avalue ** 2 for avalue in a)
    denomb = sum(bvalue ** 2 for bvalue in b)
    result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
    return result

Il est préférable de lever une exception lorsque les longueurs de a et b ne correspondent pas.

En utilisant des expressions de générateur dans les appels à sum () , vous pouvez calculer vos valeurs, la plupart du travail étant effectué par le code C à l'intérieur de Python. Cela devrait être plus rapide que d’utiliser une boucle pour .

Je n'ai pas chronométré cela, donc je ne peux pas deviner à quel point cela pourrait être plus rapide. Mais le code SciPy est presque certainement écrit en C ou C ++ et il devrait être aussi rapide que possible.

Si vous faites de la bioinformatique en Python, vous devriez de toute façon utiliser SciPy de toute façon.

EDIT: Darius Bacon a chronométré mon code et l’a trouvé plus lent. Alors j'ai chronométré mon code et ... oui, c'est plus lent. La leçon pour tous: lorsque vous essayez d'accélérer les choses, ne devinez pas, mesurez.

Je suis déconcerté par les raisons pour lesquelles ma tentative de mettre davantage de travail sur les composants C de Python est plus lente. Je l'ai essayé pour des listes de longueur 1000 et c'était encore plus lent.

Je ne peux plus passer de temps à essayer de pirater intelligemment le Python. Si vous avez besoin de plus de vitesse, je vous suggère d'essayer SciPy.

EDIT: Je viens de tester à la main, sans temps. Je trouve que pour a et b, l'ancien code est plus rapide; pendant longtemps a et b, le nouveau code est plus rapide; dans les deux cas, la différence n'est pas grande. (Je me demande maintenant si je peux faire confiance à timeit sur mon ordinateur Windows; je veux réessayer ce test sous Linux.) Je ne changerais pas le code qui fonctionne pour essayer de l'obtenir plus rapidement. Et une fois de plus, je vous exhorte à essayer SciPy. : -)

Answer 2

(Je pensais au départ) vous n'allez pas accélérer les choses sans passer à C (comme numpy ou scipy) ou changer votre calcul. Mais voici comment j'essaierais ça, quand même:

from itertools import imap
from math import sqrt
from operator import mul

def cosine_distance(a, b):
    assert len(a) == len(b)
    return 1 - (sum(imap(mul, a, b))
                / sqrt(sum(imap(mul, a, a))
                       * sum(imap(mul, b, b))))

Il est environ deux fois plus rapide en Python 2.6 avec des tableaux de 500 000 éléments. (Après avoir modifié la carte en imap, suivez Jarret Hardie.)

Voici une version modifiée du code révisé de l'affiche originale:

from itertools import izip

def cosine_distance(a, b):
    assert len(a) == len(b)
    ab_sum, a_sum, b_sum = 0, 0, 0
    for ai, bi in izip(a, b):
        ab_sum += ai * bi
        a_sum += ai * ai
        b_sum += bi * bi
    return 1 - ab_sum / sqrt(a_sum * b_sum)

C'est moche, mais ça sort plus vite. . .

Modifier: et essayez Psyco ! Cela accélère la version finale par un autre facteur de 4. Comment pourrais-je oublier?

Answer 3

Inutile de prendre abs () de a [i] et b [i] si vous le corrigez.

Stockez a [i] et b [i] dans des variables temporaires pour éviter de procéder à l'indexation plusieurs fois. Le compilateur peut peut-être optimiser cela, mais peut-être pas.

Consultez l'opérateur ** 2 . Simplifie-t-il la multiplication ou utilise-t-il une fonction de puissance générale (log - multiply by 2 - antilog)?

Ne le faites pas deux fois (même si le coût est peu élevé). Faites sqrt (denoma * denomb) .

Answer 4

Semblable à la réponse de Darius Bacon, je me suis mis à jouer avec l'opérateur et les outils informatiques pour produire une réponse plus rapide. Ce qui suit semble être 1/3 plus rapide sur un tableau de 500 éléments en fonction du temps:

from math import sqrt
from itertools import imap
from operator import mul

def op_cosine(a, b):
    dot_prod = sum(imap(mul, a, b))
    a_veclen = sqrt(sum(i ** 2 for i in a))
    b_veclen = sqrt(sum(i ** 2 for i in b))

    return 1 - dot_prod / (a_veclen * b_veclen)

Answer 5

Cela est plus rapide pour les tableaux d'environ 1000 éléments.

from numpy import array
def cosine_distance(a, b):
    a=array(a)
    b=array(b)
    numerator=(a*b).sum()
    denoma=(a*a).sum()
    denomb=(b*b).sum()
    result = 1 - numerator / sqrt(denoma*denomb)
    return result

Answer 6

L'utilisation du code C à l'intérieur de SciPy gagne gros pour les tableaux de données longs. L'utilisation simple et directe de Python gagne les tableaux d'entrée courts; Le code basé sur izip () de Darius Bacon a été comparé au mieux. Ainsi, la solution ultime consiste à décider lequel utiliser au moment de l’exécution, en fonction de la longueur des tableaux d’entrée:

from scipy.spatial.distance import cosine as scipy_cos_dist

from itertools import izip
from math import sqrt

def cosine_distance(a, b):
    len_a = len(a)
    assert len_a == len(b)
    if len_a > 200:  # 200 is a magic value found by benchmark
        return scipy_cos_dist(a, b)
    # function below is basically just Darius Bacon's code
    ab_sum = a_sum = b_sum = 0
    for ai, bi in izip(a, b):
        ab_sum += ai * bi
        a_sum += ai * ai
        b_sum += bi * bi
    return 1 - ab_sum / sqrt(a_sum * b_sum)

J'ai créé un test harnais qui testait les fonctions avec différentes entrées de longueur et a constaté que vers la longueur 200, la fonction SciPy commençait à gagner. Plus les matrices d'entrée sont grandes, plus elles gagnent. Pour des tableaux de très courte longueur, disons de longueur 3, le code le plus simple l'emporte. Cette fonction ajoute une petite quantité d’overhead pour décider de la meilleure façon de le faire, puis le fait de la meilleure façon.

Si cela vous intéresse, voici le harnais de test:

from darius2 import cosine_distance as fn_darius2
fn_darius2.__name__ = "fn_darius2"

from ult import cosine_distance as fn_ult
fn_ult.__name__ = "fn_ult"

from scipy.spatial.distance import cosine as fn_scipy
fn_scipy.__name__ = "fn_scipy"

import random
import time

lst_fn = [fn_darius2, fn_scipy, fn_ult]

def run_test(fn, lst0, lst1, test_len):
    start = time.time()
    for _ in xrange(test_len):
        fn(lst0, lst1)
    end = time.time()
    return end - start

for data_len in range(50, 500, 10):
    a = [random.random() for _ in xrange(data_len)]
    b = [random.random() for _ in xrange(data_len)]
    print "len(a) ==", len(a)
    test_len = 10**3
    for fn in lst_fn:
        n = fn.__name__
        r = fn(a, b)
        t = run_test(fn, a, b, test_len)
        print "%s:\t%f seconds, result %f" % (n, t, r)

Answer 7

def cd(a,b):
    if(len(a)!=len(b)):
        raise ValueError, "a and b must be the same length"
    rn = range(len(a))
    adb = sum([a[k]*b[k] for k in rn])
    nma = sqrt(sum([a[k]*a[k] for k in rn]))
    nmb = sqrt(sum([b[k]*b[k] for k in rn]))

    result = 1 - adb / (nma*nmb)
    return result

Answer 8

Votre solution mise à jour a toujours deux racines carrées. Vous pouvez le réduire à un en remplaçant la ligne sqrt par:

  

resultat = 1 - numérateur /   (sqrt (denoma * denomb))

Une multiplication est généralement un peu plus rapide qu'un carré. Cela pourrait ne pas sembler beaucoup car il n’appelle qu’une fois dans la fonction, mais il semblerait que vous calculiez beaucoup de distances de cosinus. L’amélioration s’améliorera donc.

Votre code semble devoir être optimisé pour les optimisations vectorielles. Donc, si le support cross-platofrm n’est pas un problème et que vous souhaitez l’accélérer davantage, vous pouvez coder le code de distance cosinus en C et vous assurer que votre compilateur vectorise de manière agressive le code résultant (même Pentium II est capable de vectorisation en virgule flottante). )