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

Если вы можете использовать SciPy, вы можете использовать cosine из spatial.distance:

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

Если вы не можете использовать SciPy, вы можете попытаться получить небольшое ускорение, переписав свой Python (EDIT: но это не сработало, как я думал, см. Ниже).

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

Лучше создать исключение, когда длины a и b не совпадают.

Используя выражения генератора внутри вызовов sum(), вы можете вычислить свои значения, при этом большая часть работы выполняется кодом C внутри Python. Это должно быть быстрее, чем использование цикла for.

Я не засекал это, поэтому я не могу предположить, насколько быстрее это может быть. Но код SciPy почти наверняка написан на C или C++, и он должен быть максимально быстрым.

Если вы занимаетесь биоинформатикой на Python, вам все равно следует использовать SciPy.

РЕДАКТИРОВАТЬ: Дариус Бэкон рассчитал время моего кода и обнаружил, что он медленнее. Поэтому я рассчитал свой код и... да, он стал медленнее. Урок для всех: когда вы пытаетесь ускорить процесс, не гадайте, а измеряйте.

Я сбит с толку тем, почему моя попытка поработать над внутренностями C Python работает медленнее. Я попробовал это для списков длиной 1000, и это было еще медленнее.

Я больше не могу тратить время на то, чтобы ловко взломать Python. Если вам нужно больше скорости, я предлагаю вам попробовать SciPy.

РЕДАКТИРОВАТЬ: я только что проверил вручную, без времени. Я считаю, что для коротких a и b старый код работает быстрее; для длинных a и b новый код работает быстрее; в обоих случаях разница невелика. (Теперь мне интересно, могу ли я доверять timeit на моем компьютере с Windows; я хочу снова попробовать этот тест на Linux.) Я бы не стал менять рабочий код, чтобы попытаться сделать его быстрее. И еще раз призываю вас попробовать SciPy. :-)

(Сначала я думал), что вы не сможете сильно ускорить его, не переходя на 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 раза. Как я мог забыть?

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

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

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

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

Подобно ответу Дариуса Бэкона, я играл с оператором и 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)

Это быстрее для массивов из более чем 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)

Ваше обновленное решение по-прежнему имеет два квадратных корня. Вы можете уменьшить это значение до единицы, заменив строку sqrt на:

результат = 1 - числитель / (sqrt(denoma*denomb))

Умножение обычно немного быстрее, чем sqrt. Может показаться, что это не так уж много, так как она вызывается в функции только один раз, но похоже, что вы вычисляете много косинусных расстояний, поэтому улучшение будет складываться.

Ваш код выглядит так, как будто он созрел для векторной оптимизации. Поэтому, если кросс-платформенная поддержка не является проблемой, и вы хотите еще больше ускорить ее, вы можете написать код косинусного расстояния на C и убедиться, что ваш компилятор агрессивно векторизует результирующий код (даже Pentium II способен к некоторой векторизации с плавающей запятой). )