Оптимизированный метод для вычисления расстояния косинуса в Python

(изначально я думал) вы не собираетесь сильно его ускорять, не переходя на C (например, numpy или scipy) или изменяя то, что вы вычисляете. Но вот как я бы все равно это попробовал:

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

Это примерно в два раза быстрее в Python 2.6 с массивами из 500 тыс. Элементов. (После изменения карты на imap, вслед за Джарретом Харди.)

Вот измененная версия измененного кода исходного плаката:

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)

Это уродливо, но выходит быстрее. . .

Изменить: И попробуйте Psyco ! Это ускоряет окончательную версию еще в 4 раза. Как я мог забыть?

Подобно ответу Дариуса Бэкона, я играл с оператором и itertools, чтобы получить более быстрый ответ. Следующее выглядит на 1/3 быстрее в массиве из 500 элементов согласно 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)

Нет необходимости брать abs () из a [i] и b [i] , если вы возводите его в квадрат.

Сохраните a [i] и b [i] в временные переменные, чтобы не выполнять индексацию более одного раза. Может быть, компилятор сможет это оптимизировать, а может и нет.

Проверьте оператор ** 2 . Это упрощает его до умножения или используется общая степенная функция (log - умножить на 2 - antilog).

Не выполняйте sqrt дважды (хотя стоимость этого небольшая). Сделайте sqrt (denoma * denomb) .

Это быстрее для массивов размером около 1000 + элементы.

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

Использование кода C внутри SciPy дает большие преимущества для длинных входных массивов. Использование простого и прямого Python дает преимущество для коротких входных массивов; Код Дариуса Бэкона izip () показал себя лучше всех. Таким образом, окончательное решение состоит в том, чтобы решить, какой из них использовать во время выполнения, на основе длины входных массивов:

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)

Я сделал тестовую программу, которая тестировала функции с входами разной длины, и обнаружила, что около длины 200 функция SciPy начала работать выиграть. Чем больше входные массивы, тем больше выигрыш. Для массивов очень короткой длины, скажем, 3, более простой код выигрывает. Эта функция добавляет крошечные накладные расходы, чтобы решить, каким способом это сделать, а затем делает это наилучшим образом.

Если вам интересно, вот тестовая программа:

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)

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