Оптимизированный метод расчета косинусного расстояния в 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

Если вы можете использовать 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.

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 5

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

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

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

  

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

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

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