Processo optimizado para o cálculo da distância de co-seno em Python

Question

Eu escrevi um método para calcular a distância cosseno entre duas matrizes:

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

Running pode ser muito lento em uma grande variedade. Existe uma versão otimizada desse método que iria correr mais rápido?

Update: Eu tentei todas as sugestões, até à data, incluindo scipy. Aqui está a versão de bater, incorporando sugestões de Mike e 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

Se você pode usar SciPy, você pode usar cosine de spatial.distance:

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

Se você não pode usar SciPy, você poderia tentar obter um pequeno aumento de velocidade por reescrever o seu Python (EDIT: mas não funcionou como eu pensei que seria, veja abaixo).

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

É melhor para levantar uma excepção, quando os comprimentos de a e b são incompatíveis.

Ao usar o gerador de expressões dentro de chamadas para sum() você pode calcular os seus valores com a maior parte do trabalho que está sendo feito pelo interior código C do Python. Este deve ser mais rápido do que usando um loop for.

Eu não cronometrado isso, então eu não posso adivinhar o quanto mais rápido que poderia ser. Mas o código SciPy é quase certamente escritos em C ou C ++ e deve ser quase tão rápido quanto você pode começar.

Se você está fazendo bioinformática em Python, você realmente deve estar usando SciPy de qualquer maneira.

EDIT: Darius Bacon cronometrado meu código e encontrou-lo mais lento. Então, eu cronometrado meu código e ... sim, é mais lento. A lição para todos:. Quando você está tentando acelerar as coisas, não acho, medida

Eu estou sem entender por que minha tentativa de colocar mais trabalho sobre os internos C do Python é mais lento. Eu tentei-o para listas de comprimento 1000 e ainda mais lento era.

Eu não posso passar mais tempo na tentativa de cortar o Python inteligentemente. Se precisar de mais velocidade, eu sugiro que você tente SciPy.

EDIT: eu só testado com a mão, sem timeit. Acho que para breve a e b, o código antigo é mais rápido; por um longo e b, o novo código é mais rápido; em ambos os casos, a diferença não é grande. (Agora estou perguntando se posso confiar timeit no meu computador com Windows;. Eu quero tentar este teste novamente em Linux) Eu não mudaria o código de trabalho para tentar obtê-lo mais rápido. E mais uma vez peço-lhe para tentar SciPy. : -)

Answer 2

(eu pensava) você não está indo para acelerá-lo muito sem sair de C (como numpy ou scipy) ou mudar o que você calcular. Mas aqui está como eu ia tentar que, de qualquer maneira:

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))))

É mais ou menos duas vezes mais rápido em Python 2.6 com matrizes 500k elemento. (Depois de alterar mapa para imap, seguindo Jarret Hardie.)

Aqui está uma versão beliscada de código revisto do cartaz original:

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)

É feio, mas ele vem mais rápido. . .

Editar: E tente Psyco ! Ele acelera a versão final por outro fator de 4. Como eu poderia esquecer?

Answer 3

Não há necessidade de tomar abs() de a[i] e b[i] se você está em quadratura com ele.

a[i] loja e b[i] em variáveis ??temporárias, para evitar fazer a indexação mais de uma vez. Talvez o compilador pode otimizar isso, mas talvez não.

Verifique para o operador **2. É simplificando-o em uma multiplicação, ou está usando uma função de potência geral (log - multiplique por 2 - antilog).

Não faça sqrt duas vezes (embora o custo do que é pequeno). Fazer sqrt(denoma * denomb).

Answer 4

Semelhante a resposta de Darius Bacon, eu fui brincar com o operador e itertools para produzir uma resposta mais rápida. A seguir parece ser 1/3 mais rápido em uma matriz de 500 item de acordo com timeit:

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

Isto é mais rápido para arrays de cerca de 1000 elementos.

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

Usando o interior código C de SciPy ganha grande para matrizes de entrada de comprimento. Usando simples e vitórias Python diretos para matrizes de entrada curtas; código baseado em izip() de Darius Bacon aferido a melhor. Assim, a solução final é o de decidir qual utilizar em tempo de execução, com base no comprimento dos arranjos de entrada:

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)

Eu fiz um equipamento de teste que testou as funções com entradas diferentes de comprimento, e descobriram que o comprimento de cerca de 200 a função SciPy começou a ganhar. Quanto maior as matrizes de entrada, maior ele ganha. Para matrizes de comprimento muito curto, digamos comprimento 3, as vitórias código mais simples. Essa função adiciona uma pequena quantidade de sobrecarga para decidir qual o caminho a fazê-lo, então não é o melhor caminho.

No caso de você estiver interessado, aqui é o equipamento de teste:

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

A sua solução atualizada ainda tem duas raízes quadradas. Você pode reduzir esse número para um substituindo a linha sqrt com:

resultado = 1 - numerador / (Sqrt (denoma * denomb))

A é multiplicar tipicamente um pouco mais rápido do que um sqrt. Pode não parecer muito, pois só é chamado uma vez na função, mas parece que você está calculando um monte de distâncias cosseno, então a melhoria irá somar.

Seus olhares código como ele deve ser maduro para otimizações vetor. Então, se o suporte cross-platofrm não é um problema e você quer acelerá-lo ainda mais, você pode codificar o código de cosseno distância em C e verifique se o compilador está agressivamente vectorizing o código resultante (mesmo Pentium II é capaz de alguns vectorização de ponto flutuante )