优化的方法，用于计算余弦的距离在蟒蛇

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

在运行，它可以非常缓慢，在一个大型阵列。是否有一个优化的版本的这种方法，将运行速度更快？

更新：我已经试过了所有建议，包括这.这里的版本打，合并建议从迈克和史蒂夫：

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

如果你可以使用这，你可以使用 cosine 从 spatial.distance:

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

如果你不能使用这，你可以尝试获得一个小的加速通过重写你的蟒蛇(编辑：但它没有像我想的那样，请参阅下文)。

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码内的蟒蛇。这应该可以更快的速度比使用 for 循环。

我还没定这个所以我不能猜测，如何更快的可能。但这代码几乎可以肯定是写在C或C++并应有关一样快，你可以得到的。

如果你正在做的生物信息学在蟒蛇，你真的应该是使用这无论如何。

编辑：Darius熏肉时我的代码，发现速度较慢。所以我计时我的代码和...是的，这是速度较慢。该课程：当你试图加快速度，不要猜测、测量。

我困惑为什么我试图把更多的工作C内部的蟒蛇是速度较慢。我尝试过对列出的长1000和它仍然速度较慢。

我不能花更多的时间试图破解Python巧妙。如果你需要更快的速度，我建议你可以试试这.

编辑：我只是测试一方面，没有斑马旅行记.我找到短a和b、老码是速度更快；长a和b、新代码是速度更快；在这两种情况差异不大。(我现在想知道如果我可以信任斑马旅行记在我的窗户计算机；我想要尝试这一试验又在Linux。) 我不会改变工作的代码，试图得到它更快。和一个更多的时间，我敦促你要试试这.:-)

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，以下贾勒特哈迪。）

下面是原来的海报的订正代码微调的版本：

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操作者。是它简化成乘法，或者是使用一般的幂函数它（对数 - 乘以2 - 反对数）。

不要做两次的sqrt（虽然那成本小）。做sqrt(denoma * denomb)。

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更快相当多。这可能似乎并不多，因为它是在函数只调用一次，但它听起来像你计算余弦很大距离的，所以改进加起来。

您的代码看起来它应该是成熟矢量优化。因此，如果跨platofrm支持不是一个问题，要进一步缩短它，你可以用C编写的余弦距离的代码，并确保你的编译器正积极矢量化产生的代码（甚至奔腾II能够进行某些浮点矢量化的）