无FFT的1D快速卷积
我需要对2个大arrays进行一维卷积。 我在C＃中使用此代码，但运行时需要很长时间。
我知道我知道！ FFT卷积非常快。 但在这个项目中我不能使用它。 不使用FFT是项目的约束（请不要问为什么：/）。
这是我在C＃中的代码（从matlab移植，顺便说一下）：
var result = new double[input.Length + filter.Length - 1]; for (var i = 0; i < input.Length; i++) { for (var j = 0; j < filter.Length; j++) { result[i + j] += input[i] * filter[j]; } } 那么，有谁知道任何快速卷积算法宽度FFT？
卷积在数值上与具有额外环绕步骤的多项式乘法相同。 因此，所有多项式和大整数乘法算法都可用于执行卷积。
FFT是获得快速O（n log（n））运行时的唯一方法。 但是你仍然可以使用像Karatsuba算法这样的分而治之的方法来获得次二次运行时间。
一旦你了解它的工作原理，Karatsuba的算法就很容易实现。 它运行在O（n ^ 1.585），并且可能比尝试超级优化经典O（n ^ 2）方法更快。
您可以减少result的索引访问次数，以及Length属性：
int inputLength = filter.Length; int filterLength = filter.Length; var result = new double[inputLength + filterLength - 1]; for (int i = resultLength; i >= 0; i--) { double sum = 0; // max(i - input.Length + 1,0) int n1 = i < inputLength ? 0 : i - inputLength + 1; // min(i, filter.Length - 1) int n2 = i < filterLength ? i : filterLength - 1; for (int j = n1; j <= n2; j++) { sum += input[i - j] * filter[j]; } result[i] = sum; }
如果你进一步拆分外环，你可以摆脱一些重复的条件。 （假定为0 < resultLength ）
int inputLength = filter.Length; int filterLength = filter.Length; int resultLength = inputLength + filterLength - 1; var result = new double[resultLength]; for (int i = 0; i < filterLength; i++) { double sum = 0; for (int j = i; j >= 0; j--) { sum += input[i - j] * filter[j]; } result[i] = sum; } for (int i = filterLength; i < inputLength; i++) { double sum = 0; for (int j = filterLength - 1; j >= 0; j--) { sum += input[i - j] * filter[j]; } result[i] = sum; } for (int i = inputLength; i < resultLength; i++) { double sum = 0; for (int j = i - inputLength + 1; j < filterLength; j++) { sum += input[i - j] * filter[j]; } result[i] = sum; }
您可以使用特殊的IIR滤波器。 然后处理如下：
y(n)= a1*y(n-1)+b1*y(n-2)...+a2*x(n-1)+b2*x(n-2)......
我认为它更快。
这里有两种可能会带来轻微加速的可能性，但您需要进行测试才能确定。
- 展开内循环以删除一些测试。 如果您知道filter长度将始终为多个（如果有的话N），这将更容易。
- 颠倒循环的顺序。
filter.length是否filter.length整个数组。 这在内循环中的解除引用次数较少，但可能具有较差的缓存行为。