Python中的串行矢量减法还是“减法卷积”？

Question

首先，我想为这个问题的标题不清楚而道歉：原因是我无法确定工作中的数学过程。在

简而言之，情况如下：

1. 我有两个向量，f1和f2，长度不同。在
2. 我想计算f1和f2之间的最小平方距离。在

下面是我如何继续

import numpy as np

def distLstSq(f1,f2):
    "Return the least square distance between f1 and f2 per unit element"
    return np.sum(np.square(np.subtract(f1,f2)))/len(f1)

f1 = np.arange(100)
f2 = np.random.random_integers(1,100,5)

nBuf = len(f2)
dist = np.empty(len(f1)-nBuf)
for i in range(len(f1)-nBuf):
    temp = f1[i:i+nBuf]
    dist[i] = distLstSq(temp,f2)

然而，由于向量f1（从4MB的文件中生成），我想知道是否还有更优雅的python解决方案，在更少的时间内使用更少的CPU资源。可能是一种“减法卷积”，f2在f1上滑动，每个步骤都有减法运算。在

非常感谢您的意见！在

贝特朗

Answer 1

首先，我想指出dist中的项数不是len(f1)-nBuf，而是len(f1)-nBuf+1。这就是短向量和长向量完全重叠的方式。在

忽略按len(f1)的除法，它只是按一个常数进行缩放，您将为f2的每个片计算以下内容：

所以我认为你可以通过一些预计算来减少运算量。我们也可以用np.convolve来求交叉项。在

f1_squared = f1**2
f2_squared_sum = np.sum(f2**2)
nBuf = len(f2)
cross_terms = -2*np.convolve(f1, f2[::-1], "valid")
# reverse f2 to get what we want. 
# "valid" returns  where vectors completely overlap
squared_distance = [f2_squared_sum + np.sum(f1_squared[i:i+nBuf]) + cross_terms[i] 
                    for i in xrange(len(cross_terms))]
mean_squared_distance = np.array(squared_distance)/nBuf

您的版本：

^{pr2}$

基于timeit.timeit，我的版本要快30-50%。在

通过优化np.sum(f1_squared[i:i+nBuf])可以进一步提高性能，因为这涉及到重复操作。应该有一些分而治之的方法来计算总和。在

我也认为scipy.signal.fftconvolve可以比np.convolve快，但这取决于更短的向量(see here)的长度