11

2つの大きなアレイに対する1Dコンボリューションが必要です。このコードを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で知っていますか？

4

4 に答える 4

6

プロパティ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;
}

外側のループをさらに分割すると、いくつかの繰り返し条件を取り除くことができます。filterLength(これは 0 < ≤ 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;
}
于 2011-08-30T05:23:15.247 に答える
0

マイナーなスピードアップをもたらす可能性のある2つの可能性がありますが、確認するためにテストする必要があります。

  1. いくつかのテストを削除するには、内側のループを展開します。フィルターの長さがNの場合は常に倍になることがわかっている場合、これは簡単になります。
  2. ループの順序を逆にします。filter.length配列全体を通過します。これにより、内部ループでの間接参照が少なくなりますが、キャッシュ動作が悪化する可能性があります。
于 2011-08-30T02:02:27.817 に答える
0

特別な IIR フィルターを使用できます。次に、次のように処理します。

y(n)= a1*y(n-1)+b1*y(n-2)...+a2*x(n-1)+b2*x(n-2)......

速いと思います。

于 2013-08-14T14:12:45.050 に答える