加速距离计算，滑动窗口

Question

我有两个时间序列A和B。A的长度为mB，B的长度为n。m << n。两者都有尺寸d。

我通过在B上滑动A来计算A与B中所有子序列之间的距离。在python中，代码如下所示。

def sliding_dist(A,B)
    n = len(B)
    dist = np.zeros(n)
    for i in range(n-m):
        subrange = B[i:i+m,:]
        distance = np.linalg.norm(A-subrange)
        dist[i] = distance
    return dist

现在，这段代码需要花费很多时间来执行，并且我有很多计算要做。我需要加快计算速度。我的猜测是，我可以使用卷积和频域乘法（FFT）来做到这一点。但是，我无法实现它。

有任何想法吗？：） 谢谢

Answer 1

norm(A - subrange) 本身不是卷积，但是可以表示为：

sqrt(dot(A, A) + dot(subrange, subrange) - 2 * dot(A, subrange))

如何快速计算每个术语：

• dot(A, A) -这只是一个常数。

• dot(subrange, subrange) -可以使用递归方法在O（1）（每个位置）中进行计算。

• dot(A, subrange)- 在这种情况下，这是一个卷积。因此，可以通过卷积定理在频域中进行计算。^1个

但是请注意，如果子范围大小仅为10，您不太可能看到性能提高。

_{1. AKA 快速卷积。}