python - Python中的串行向量减法或 "subtractive convolution"？

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 的文件生成)，我想知道是否没有更优雅的 pythonic 解决方案，使用更少的 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

您的版本:

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

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

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

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