Оптимизирован метод вычисления косинуса расстояния в 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. Вот версия бить, включая предложения от Mike и 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

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

EDIT: Darius Bacon приурочил мой код и нашел его медленнее. Поэтому я приурочил свой код и ... да, он медленнее. Урок для всех: когда вы пытаетесь ускорить процесс, не угадывайте, не измеряйте.

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

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

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

Answer 2

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

(я думал), вы не собираетесь его ускорить много, не вспыхивают на 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, после Jarret Hardie.)

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

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

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

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

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

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

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

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

Answer 6

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 7

Использование кода C внутри SciPy выигрывает большой для длинных входных массивов. Использование простых и прямых выигрышей Python для коротких входных массивов; Darius Bacon's 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 8

Обновленное решение по-прежнему имеет два квадратных корня. Вы можете уменьшить это путем замены на SQRT линию:

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

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

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