如何使用 Numpy 更快地最小化这个距离？ （找到两个信号彼此接近的移动索引）
How to minimize this distance faster with Numpy? (find shifting-index for which two signals are close to each other)
给定一个长度为 1000 的数组 x 和长度为 500k 的 y，我们可以计算 索引 k 其中 x 是最接近“y-偏移 k 指数”:
mindistance = np.inf # infinity
for k in range(len(y)-1000):
t = np.sum(np.power(x-y[k:k+1000],2))
if t < mindistance:
mindistance = t
index = k
print index
# x is close to y[index:index+N]
根据我的测试，这似乎在数值上是昂贵的。 有没有聪明的numpy方法来更快地计算它？
注：看来如果我把x的长度从1000换成100，计算时间并没有太大变化。缓慢似乎主要来自 for k in range(...) 循环。如何加快速度？
这可以用 np.correlate 来完成，它计算的不是相关系数（正如人们可能猜到的那样），而是简单地计算乘积之和，例如 x[n]*y[m]（这里 m 是 n 加上一些偏移） .自
(x[n] - y[m])**2 = x[n]**2 - 2*x[n]*y[m] + y[m]**2
我们可以得到差的平方和，通过将x和y的一部分的平方和相加。 （实际上，x[n]**2 的总和不依赖于移位，因为我们总是得到 np.sum(x**2)，但我还是将它包括在内。）[= 的一部分的总和16=] 也可以通过这种方式找到，通过将 x 替换为相同大小的全一数组，将 y 替换为 y**2。
这是一个例子。
import numpy as np
x = np.array([3.1, 1.2, 4.2])
y = np.array([8, 5, 3, -2, 3, 1, 4, 5, 7])
diff_sq = np.sum(x**2) - 2*np.correlate(y, x) + np.correlate(y**2, np.ones_like(x))
print(diff_sq)
这会打印 [39.89 45.29 11.69 39.49 0.09 12.89 23.09]，这确实是从 x 到 y 的各个部分所需的距离。选择最小的 argmin.
除了user6655984的精彩回答之外的一个小基准：
import numpy as np
import time
x = np.random.rand(1000) # random array of size 1k
y = np.random.rand(100*1000) # random array of size 100k
print "Naive method"
start = time.time()
mindistance = np.inf
for k in range(len(y)-1000):
t = np.sum(np.power(x-y[k:k+1000],2))
if t < mindistance:
mindistance = t
index = k
print index, mindistance
print "%.2f seconds\n" % (time.time() - start)
print "Correlation method"
start = time.time()
diff_sq = np.sum(x**2) - 2*np.correlate(y, x) + np.correlate(y**2, np.ones_like(x))
i = np.argmin(diff_sq)
print i, diff_sq[i]
print "%.2f seconds\n" % (time.time() - start)
我们得到了 x 145 的速度改进因子:)
Naive method
60911 143.6153965841267
8.75 seconds
Correlation method
60911 143.6153965841267
0.06 seconds
SSD距离的最小值("sum of squared difference")是相关性的最大值。
众所周知，著名的 FFT 可以有效地计算相关性（时间为 N Log N 而不是 NM）。
在 N=1000 和 M=500000 的情况下，您可以获得加速。
给定一个长度为 1000 的数组 x 和长度为 500k 的 y，我们可以计算 索引 k 其中 x 是最接近“y-偏移 k 指数”:
mindistance = np.inf # infinity
for k in range(len(y)-1000):
t = np.sum(np.power(x-y[k:k+1000],2))
if t < mindistance:
mindistance = t
index = k
print index
# x is close to y[index:index+N]
根据我的测试，这似乎在数值上是昂贵的。 有没有聪明的numpy方法来更快地计算它？
注：看来如果我把x的长度从1000换成100，计算时间并没有太大变化。缓慢似乎主要来自 for k in range(...) 循环。如何加快速度？
这可以用 np.correlate 来完成，它计算的不是相关系数（正如人们可能猜到的那样），而是简单地计算乘积之和，例如 x[n]*y[m]（这里 m 是 n 加上一些偏移） .自
(x[n] - y[m])**2 = x[n]**2 - 2*x[n]*y[m] + y[m]**2
我们可以得到差的平方和，通过将x和y的一部分的平方和相加。 （实际上，x[n]**2 的总和不依赖于移位，因为我们总是得到 np.sum(x**2)，但我还是将它包括在内。）[= 的一部分的总和16=] 也可以通过这种方式找到，通过将 x 替换为相同大小的全一数组，将 y 替换为 y**2。
这是一个例子。
import numpy as np
x = np.array([3.1, 1.2, 4.2])
y = np.array([8, 5, 3, -2, 3, 1, 4, 5, 7])
diff_sq = np.sum(x**2) - 2*np.correlate(y, x) + np.correlate(y**2, np.ones_like(x))
print(diff_sq)
这会打印 [39.89 45.29 11.69 39.49 0.09 12.89 23.09]，这确实是从 x 到 y 的各个部分所需的距离。选择最小的 argmin.
除了user6655984的精彩回答之外的一个小基准：
import numpy as np
import time
x = np.random.rand(1000) # random array of size 1k
y = np.random.rand(100*1000) # random array of size 100k
print "Naive method"
start = time.time()
mindistance = np.inf
for k in range(len(y)-1000):
t = np.sum(np.power(x-y[k:k+1000],2))
if t < mindistance:
mindistance = t
index = k
print index, mindistance
print "%.2f seconds\n" % (time.time() - start)
print "Correlation method"
start = time.time()
diff_sq = np.sum(x**2) - 2*np.correlate(y, x) + np.correlate(y**2, np.ones_like(x))
i = np.argmin(diff_sq)
print i, diff_sq[i]
print "%.2f seconds\n" % (time.time() - start)
我们得到了 x 145 的速度改进因子:)
Naive method
60911 143.6153965841267
8.75 secondsCorrelation method
60911 143.6153965841267
0.06 seconds
SSD距离的最小值("sum of squared difference")是相关性的最大值。
众所周知，著名的 FFT 可以有效地计算相关性（时间为 N Log N 而不是 NM）。
在 N=1000 和 M=500000 的情况下，您可以获得加速。