4

私はc＃で移動平均フィルターを実装するためのエレガントな方法を探しています。さて、それは簡単ですが、境界では、平均化ウィンドウが開始/終了をラップします。この種のコードは醜くて直感的ではなく、LINQなどを使用してこれを解決するためのよりスマートな方法があるかどうか疑問に思いました。

だから私が現在持っているのは：

// input is a List<double> y, output is List<double> yfiltered
int yLength = y.Count;
for (int i = 0; i < yLength; i++)
{
    double sum = 0.0;
    for (int k = i - halfWindowWidth; k <= i + halfWindowWidth; k++)
    {
        if (k < 0)
        {
            // k is negative, wrap around
            sum += y[yLength - 1 + k];
        }
        else if (k >= yLength)
        {
            // k exceeds y length, wrap around
            sum += y[k - yLength];
        }
        else
        {
            // k within y.Count
            sum += y[k];
        }
    }
    yfiltered[i] = sum / (2 * halfWindowWidth + 1);
}
4

3 に答える 3

5

これはまったく別の提案です -

読みやすくするのではなく、実際に改善しようとしていました。

現在のコードの問題は、実際には必要ないときに、何度も何度も多くの数値を合計することです。

実装コードの後で両方のアプローチを比較しています...

私は最初に束を合計してから、テールを差し引いてヘッドを追加することを何度も繰り返しています:

double sum = 0;

// sum = Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1)
//    .Select(k => y[(k + yLength) % yLength]).Sum();

for (var i = -halfWindowWidth; i <= halfWindowWidth; i++)
{
    sum += y[(i + yLength) % yLength];
}

yFiltered[0] = sum / (2 * halfWindowWidth + 1);

for (var i = 1; i < yLength; i++)
{
    sum = sum -
          y[(i - halfWindowWidth - 1 + yLength) % yLength] +
          y[(i + halfWindowWidth) % yLength];

    yFiltered[i] = sum / (2 * halfWindowWidth + 1);
}

そして、完全な再計算アプローチとこれを比較した速度テストは次のとおりです。

private static double[] Foo1(IList<double> y, int halfWindowWidth)
{
    var yfiltered = new double[y.Count];

    var yLength = y.Count;

    for (var i = 0; i < yLength; i++)
    {
        var sum = 0.0;

        for (var k = i - halfWindowWidth; k <= i + halfWindowWidth; k++)
        {
            sum += y[(k + yLength) % yLength];
        }

        yfiltered[i] = sum / (2 * halfWindowWidth + 1);
    }

    return yfiltered;
}

private static double[] Foo2(IList<double> y, int halfWindowWidth)
{
    var yFiltered = new double[y.Count];
    var windowSize = 2 * halfWindowWidth + 1;

    double sum = 0;

    for (var i = -halfWindowWidth; i <= halfWindowWidth; i++)
    {
        sum += y[(i + y.Count) % y.Count];
    }

    yFiltered[0] = sum / windowSize;

    for (var i = 1; i < y.Count; i++)
    {
        sum = sum -
              y[(i - halfWindowWidth - 1 + y.Count) % y.Count] +
              y[(i + halfWindowWidth) % y.Count];

        yFiltered[i] = sum / windowSize;
    }

    return yFiltered;
}

private static TimeSpan TestFunc(Func<IList<double>, int, double[]> func, IList<double> y, int halfWindowWidth, int iteration
{
    var sw = Stopwatch.StartNew();

    for (var i = 0; i < iterations; i++)
    {
        var yFiltered = func(y, halfWindowWidth);
    }

    sw.Stop();
    return sw.Elapsed;
}

private static void RunTests()
{
    var y = new List<double>();
    var rand = new Random();

    for (var i = 0; i < 1000; i++)
    {
        y.Add(rand.Next());
    }

    var foo1Res = Foo1(y, 100);
    var foo2Res = Foo2(y, 100);

    Debug.WriteLine("Results are equal: " + foo1Res.SequenceEqual(foo2Res));

    Debug.WriteLine("Foo1: " + TestFunc(Foo1, y, 100, 1000));
    Debug.WriteLine("Foo2: " + TestFunc(Foo2, y, 100, 1000));
}

時間の複雑さ:

マイウェイ: O(n + m)

他の方法: O(n * m)

Foo1 は O(n * m) で Foo2 は O(n + m) であるため、違いが非常に大きいことは驚くことではありません。

この非常にクレイジーではない大きなスケールでの結果は次のとおりです。

結果が等しい: True

Foo1: 5.52 秒

Foo2: 61.1 ミリ秒

さらに大きなスケールで (反復とカウントの両方で 1000 を 10000 に置き換えました):

Foo1: 10 分後に停止...

Foo2: 6.9 秒

于 2012-05-08T09:18:27.883 に答える
4

私のコメントを拡張すると、 mod ( %)演算子を使用して からkラップすることができます
0ylength - 1

    // input is a List<double> y, output is List<double> yfiltered
    int yLength = y.Count;
    for (int i = 0; i < yLength; i++)
    {
        double sum = 0.0;
        for (int k = i - halfWindowWidth; k <= i + halfWindowWidth; k++)
        {
            sum += y[(k + yLength) % yLength];
        }
        yfiltered[i] = sum / (2 * halfWindowWidth + 1);
    }
于 2012-05-08T09:02:24.040 に答える
3 
for (var i = 0; i < yLength; i++)
{
    var sum = Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1)
        .Select(k => y[(yLength + k) % yLength]).Sum();

    yFiltered[i] = sum / (2 * halfWindowWidth + 1);
}

あるいは：

var output = input.Select((val, i) =>
                 Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1)
                           .Select(k => input[(input.Count + k) % input.Count])
                 .Sum()).ToList();
于 2012-05-08T09:04:27.547 に答える