在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获得一个小的加速(编辑:但它没有像我想象的那样工作,见下文).

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()您可以计算您的值,其中大部分工作由Python内部的C代码完成.这应该比使用for循环更快.

我还没有计时,所以我无法猜测它会有多快.但是SciPy代码几乎肯定是用C或C++编写的,它应该尽可能快地得到.

如果您正在使用Python进行生物信息学,那么您真的应该使用SciPy.

编辑:Darius培根计时我的代码,发现它更慢.所以我计算了我的代码......是的,它更慢了.适合所有人的教训:当你试图加快速度时,不要猜测,测量.

令我感到困惑的是,为什么我在Python的C内部进行更多工作的尝试速度较慢.我尝试了1000长度的列表,它仍然较慢.

我不能再花时间试图巧妙地破解Python了.如果你需要更快的速度,我建议你试试SciPy.

编辑:我只是手工测试,没有时间.我发现,对于简短的a和b,旧代码更快; 对于长a和b,新代码更快; 在这两种情况下,差异并不大.(我现在想知道我是否可以信任我的Windows计算机上的timeit;我想在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中的速度大约是500k元素阵列的两倍.(在将地图改为imap之后,继Jarret Hardie之后.)

这是原始海报修订代码的调整版本:

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倍.我怎能忘记？