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

Question

Я написал метод для вычисления косинусного расстояния между двумя массивами:

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

Запуск может быть очень медленным на большом массиве. Есть ли оптимизированная версия этого метода, которая будет работать быстрее?

Обновление: я попробовал все предложения на сегодняшний день, включая scipy. Вот лучшая версия, включающая предложения Майка и Стива:

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

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

Это некрасиво, но выходит быстрее. , .

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

Answer 2

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

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

Если вы не можете использовать SciPy, вы можете попытаться получить небольшое ускорение, переписав свой Python (РЕДАКТИРОВАТЬ: но это не сработало так, как я думал, см. Ниже).

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

Answer 3

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

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

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

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

Answer 4

Использование кода 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)

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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