加快距离计算，滑动窗口

Question

我有两个时间序列A和B. A长度qazxsw poi和B长度qazxsw poi。 qazxsw poi。两者都有尺寸m。

我通过在A上滑动A来计算A和B中所有子序列之间的距离。在python中，代码看起来像这样。

n

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

有任何想法吗？ ：） 谢谢

Answer 1

使用矩阵运算实现，就像我在评论中提到的那样。想法是逐步评估规范。在你的情况下，我的价值是：

m << n

前三行计算平方和，最后一行计算sqrt（）。

加速大约是60倍。

d

更新

这是在矩阵运算中需要的“重新实现”规范。如果你想要一些

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

提供的其他规范，它就不灵活了。由于norm（）接收参数轴，因此可以使用不同的方法来创建B滑动窗口的矩阵并在整个数组上制定规范。以下是该方法的实现，但加速速度约为40x，比以前慢。

d[i] = sqrt((A[0] - B[i])^2 + (A[1] - B[+1])^2 + ... + (A[m-1] - B[i+m-1])^2)

Answer 2

import numpy
import time

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

def sd_2(A, B):
    m = len(A)
    dist = numpy.square(A[0] - B[:-m])
    for i in range(1, m):
        dist += numpy.square(A[i] - B[i:-m+i])
    return numpy.sqrt(dist, out=dist)

A = numpy.random.rand(10)
B = numpy.random.rand(500)
x = 1000
t = time.time()
for _ in range(x):
    d1 = sliding_dist(A, B)
t1 = time.time()
for _ in range(x):
    d2 = sd_2(A, B)
t2 = time.time()

print numpy.allclose(d1, d2)
print 'Orig %0.3f ms, second approach %0.3f ms' % ((t1 - t) * 1000., (t2 - t1) * 1000.)
print 'Speedup ', (t1 - t) / (t2 - t1)

本身不是卷积，但它可以表达为：

numpy

如何快速计算每个术语：

• def sd_3(A, B):
      m = len(A)
      n = len(B)
      bb = numpy.empty((len(B) - m, m))
      for i in range(m):
          bb[:, i] = B[i:-m+i]
      return numpy.linalg.norm(A - bb, axis=1)

  - 这只是一个常数。
• norm(A - subrange) - 这可以使用递归方法在O（1）（每个位置）中计算。
• sqrt(dot(A, A) + dot(subrange, subrange) - 2 * dot(A, subrange)) - 在这种背景下这是一个卷积。所以这可以通过dot(A, A).1在​​频域中计算出来

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

---

1. AKA dot(subrange, subrange)。