algorithm - 确定发生最具建设性干扰的偏移量

Question

我有两个数据数组:

我想将这些相似的图形对齐在一起(通过向任一数组添加偏移量):

基本上我想要的是最具建设性的干涉，如图所示，当两个波一起产生相同的波但振幅更大时:

这也和寻找破坏力最大的干扰一样，但是其中一个数组必须倒置，如图所示:

请注意，第二波是反转的(波峰变为波谷/反之亦然)。

实际数据将不仅包括一个主要的和一个次要的波峰和波谷，而且包括许多，并且可能没有任何明显的尖峰。我已使图表中的数据更简单，以显示我希望如何对齐数据。

我在想几个循环，比如:

biggest = 0
loop from -10 to 10 as offset
    count = 0
    loop through array1 as ar1
        loop through array2 as ar2
            count += array1[ar1] + array2[ar2 - offset]
    replace biggest with count if count/sizeof(array1) > biggest

但是，这需要遍历偏移量并遍历两个数组。我的实际数组定义非常大，这会花费很长时间。

我将如何确定将 data1 与 data2 匹配所需的偏移量？

JSFiddle (请注意，这是与语言无关的，我想比实际代码更了解算法)

Answer 1

看Convolution和 Cross-correlation它的计算使用 Fast Fourier Transformation .这就是它在现实生活应用程序中的完成方式。