我需要针对 2 个大阵列的一维卷积。我在 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];
}
}
那么，有人知道任何快速卷积算法widthout FFT吗？
您可以减少对 的索引访问次数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 < filterLength≤ inputLength≤ 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;
}
卷积在数值上与带有额外回绕步骤的多项式乘法相同。因此，所有的多项式和大整数乘法算法都可以用来进行卷积。
FFT 是获得快速 O(n log(n)) 运行时间的唯一方法。但是您仍然可以使用Karatsuba 算法等分而治之的方法获得亚二次运行时间。
一旦你了解了 Karatsuba 的算法是如何工作的，它就很容易实现。它在 O(n^1.585) 中运行，并且可能比尝试超级优化经典的 O(n^2) 方法更快。
这里有两种可能会稍微加快速度，但您需要进行测试才能确定。
filter.length遍历整个数组。这会减少内部循环中的取消引用，但可能会有更糟糕的缓存行为。 您可以使用特殊的 IIR 滤波器。然后像这样处理：
y(n)= a1*y(n-1)+b1*y(n-2)...+a2*x(n-1)+b2*x(n-2)......
我认为它更快。