c# - 効率的なローリング最大および最小ウィンドウ

Question

ローリング最大値と最小値を効率的に計算したい。ウィンドウが移動するたびに、使用中のすべての値から最大値/最小値を再計算するよりも良いことを意味します。

ここに同じことを尋ねる投稿があり、誰かがその評価に基づいて機能すると思われるある種のスタックアプローチを含むソリューションを投稿しました。しかし、私は一生それを再び見つけることはできません。

解決策や投稿を見つける際に、どんな助けもいただければ幸いです。皆さん、ありがとうございました！

score 7 · Accepted Answer

使用するアルゴリズムは、昇順の最小値 (C++ 実装)と呼ばれます。

C# でこれを行うには、ダブルエンドのキュークラスを取得する必要があります。NuGet にはNito.Dequeという名前で適切なクラスが存在します。

Nito.Deque を使用して簡単な C# 実装を作成しましたが、簡単に確認しただけで、頭から実行したため、間違っている可能性があります。

public static class AscendingMinima
{
    private struct MinimaValue
    {
        public int RemoveIndex { get; set; }
        public double Value { get; set; }
    }

    public static double[] GetMin(this double[] input, int window)
    {
        var queue = new Deque<MinimaValue>();
        var result = new double[input.Length];

        for (int i = 0; i < input.Length; i++)
        {
            var val = input[i];

            // Note: in Nito.Deque, queue[0] is the front
            while (queue.Count > 0 && i >= queue[0].RemoveIndex)
                queue.RemoveFromFront();

            while (queue.Count > 0 && queue[queue.Count - 1].Value >= val)
                queue.RemoveFromBack();

            queue.AddToBack(new MinimaValue{RemoveIndex = i + window, Value = val });

            result[i] = queue[0].Value;
        }

        return result;
    }
}

score 3 · Accepted Answer

これをより効率的に行う 1 つの方法を次に示します。ときどき値を計算する必要がありますが、特定の縮退データ (常に減少する値) を除いて、このソリューションでは最小化されています。

物事を単純化するために自分自身を最大限に制限しますが、最小限に拡張することも簡単です.

必要なものは次のとおりです。

ウィンドウ自体、最初は空です。
現在の最大値 ( max)、最初は任意の値。
現在の最大値 ( maxcount) のカウントで、最初は 0 です。

アイデアは、現在の最大値を保持するためのキャッシュとしてmaxandを使用することです。maxcountキャッシュが有効な場合は、キャッシュ内の値を返すだけでよく、非常に高速な一定時間の操作です。

最大値を要求したときにキャッシュが無効な場合は、キャッシュにデータを入力してからその値を返します。これは、前の段落の方法よりも遅くなりますが、キャッシュが再び有効になると、その後の最大値のリクエストでは、より高速な方法が使用されます。

ウィンドウと関連データを維持するために行うことは次のとおりです。

次の値を取得しますN。
ウィンドウがいっぱいの場合は、最も古いエントリを削除しMます。maxcount が 0 より大きく、Mに等しい場合max、デクリメントしますmaxcount。0に達すると、キャッシュは無効になりますが、ユーザーが最大値を要求maxcountするまでは心配する必要はありません(それまでキャッシュを再設定する意味はありません)。
Nローリングウィンドウに追加します。
ウィンドウサイズが現在 1 の場合 (これNが現在の唯一のエントリです)、および 1 に設定し、max手順1 に戻ります。Nmaxcount
maxcountが 0 よりも大きくよりも大きい場合はN、とを1 にmax設定maxし、ステップ 1 に戻ります。Nmaxcount
maxcountが 0 より大きくNに等しい場合、maxをインクリメントしますmaxcount。
ステップ 1 に戻ります。

ここで、そのウィンドウ管理が進行中の任意の時点で、最大値を要求できます。これは別の操作であり、ウィンドウ管理自体とは異なります。これは、次の規則を順番に使用して行うことができます。

ウィンドウが空の場合、最大値はありません。例外を発生させるか、適切なセンチネル値を返します。
maxcountが 0 より大きい場合、キャッシュは有効です。単純に return を返しますmax。
それ以外の場合は、キャッシュを再設定する必要があります。以下のコードスニペットに従って、リスト全体を設定し、設定しmaxます。maxcount

set max to window[0], maxcount to 0
for each x in window[]:
    if x > max:
        set max to x, maxcount to 1
    else:
        if x == max:
            increment maxcount

ほとんどの場合、最大値のキャッシュを維持し、必要な場合にのみ再計算するという事実は、エントリが追加されるたびに盲目的に再計算するよりもはるかに効率的なソリューションになります。

明確な統計を得るために、次の Python プログラムを作成しました。サイズ 25 のスライディングウィンドウを使用し、0 から 999 までの乱数を使用します (これらのプロパティを操作して、それらが結果にどのように影響するかを確認できます)。

最初にいくつかの初期化コード。変数に注意してください。statキャッシュのヒットとミスをカウントするために使用されます。

import random

window = []
max = 0
maxcount = 0
maxwin = 25

statCache = 0
statNonCache = 0

次に、上記の説明に従って、ウィンドウに数値を追加する関数:

def addNum(n):
    global window
    global max
    global maxcount
    if len(window) == maxwin:
        m = window[0]
        window = window[1:]
        if maxcount > 0 and m == max:
            maxcount = maxcount - 1

    window.append(n)

    if len(window) == 1:
        max = n
        maxcount = 1
        return

    if maxcount > 0 and n > max:
        max = n
        maxcount = 1
        return

    if maxcount > 0 and n == max:
        maxcount = maxcount + 1

次に、ウィンドウから最大値を返すコード:

def getMax():
    global max
    global maxcount
    global statCache
    global statNonCache

    if len(window) == 0:
        return None

    if maxcount > 0:
        statCache = statCache + 1
        return max

    max = window[0]
    maxcount = 0
    for val in window:
        if val > max:
            max = val
            maxcount = 1
        else:
            if val == max:
                maxcount = maxcount + 1
    statNonCache = statNonCache + 1

    return max

最後に、テストハーネス:

random.seed()
for i in range(1000000):
    val = int(1000 * random.random())
    addNum(val)
    newmax = getMax()

print("%d cached, %d non-cached"%(statCache,statNonCache))

テストハーネスは、ウィンドウに数値を追加するたびに最大値を取得しようとすることに注意してください。実際には、これは必要ないかもしれません。つまり、これは生成されたランダムデータの最悪のシナリオです。

疑似統計目的でそのプログラムを数回実行すると、次のようになります (レポート目的でフォーマットおよび分析されます)。

 960579 cached,  39421 non-cached
 960373 cached,  39627 non-cached
 960395 cached,  39605 non-cached
 960348 cached,  39652 non-cached
 960441 cached,  39559 non-cached
 960602 cached,  39398 non-cached
 960561 cached,  39439 non-cached
 960463 cached,  39537 non-cached
 960409 cached,  39591 non-cached
 960798 cached,  39202 non-cached
=======         ======
9604969         395031

したがって、ランダムデータの平均で、約 3.95% のケースのみが計算ヒット (キャッシュミス) になっていることがわかります。大多数は、キャッシュされた値を使用しました。これは、ウィンドウへの挿入ごとに最大値を再計算するよりもはるかに優れているはずです。

その割合に影響を与えるいくつかの事柄は次のとおりです。

ウィンドウのサイズ。サイズが大きいほど、キャッシュヒットの可能性が高くなり、パーセンテージが向上します。たとえば、ウィンドウサイズを 2 倍にすると、キャッシュミスがほぼ半分になります (1.95%)。
可能な値の範囲。ここでの選択肢が少ないということは、ウィンドウ内でキャッシュヒットが発生する可能性が高くなることを意味します。たとえば、範囲をから0..999に縮小0..9すると、キャッシュミスが大幅に減少しました (0.85%)。

score 0 · Accepted Answer

a[start]「ウィンドウ」とはまでの範囲を意味しa[start + len]、それがstart移動すると仮定しています。最小値、最大値は類似しており、ウィンドウa[start + 1]への移動はa[start + len + 1]. 次に、ウィンドウの最小値は、(a) a[start + len + 1] < min(より小さい値が入力された)、または (b) a[start] == min(最小値の 1 つが残った; 最小値を再計算する) 場合にのみ変更されます。

これを行うためのおそらくより効率的な別の方法は、プライオリティキューを最初のウィンドウで埋め、出入りする各値で更新することですが、それはあまり良いとは思いません (プライオリティキューは「ピック」に適していません)。真ん中からランダムな要素を取り出します」（ウィンドウを進めるときに必要なこと）。コードははるかに複雑になります。パフォーマンスが許容できないことが証明され、このコードが原因であることが証明されるまで、単純なソリューションに固執することをお勧めします(大部分の) リソース消費に対して。

score 0 · Accepted Answer

昨日自分のアルゴリズムを書き、改善を求めたところ、ここに紹介されました。実際、このアルゴリズムはよりエレガントです。ウィンドウサイズに関係なく一定速度の計算を提供するかどうかはわかりませんが、それでも、パフォーマンスと独自のキャッシュアルゴリズムをテストしました（かなり単純で、おそらく他の人が提案したのと同じアイデアを使用しています）。キャッシングは 8 ～ 15 倍高速です (5、50、300、1000 のローリングウィンドウでテストしましたが、それ以上は必要ありません)。以下は、ストップウォッチと結果の検証を使用した両方の代替手段です。

static class Program
{
    static Random r = new Random();
    static int Window = 50; //(small to facilitate visual functional test). eventually could be 100 1000, but not more than 5000.
    const int FullDataSize =1000;
    static double[] InputArr = new double[FullDataSize]; //array prefilled with the random input data.

    //====================== Caching algo variables
    static double Low = 0;
    static int LowLocation = 0;
    static int CurrentLocation = 0;
    static double[] Result1 = new double[FullDataSize]; //contains the caching mimimum result
    static int i1; //incrementor, just to store the result back to the array. In real life, the result is not even stored back to array.

    //====================== Ascending Minima algo variables
    static double[] Result2 = new double[FullDataSize]; //contains ascending miminum result.
    static double[] RollWinArray = new double[Window]; //array for the caching algo
    static Deque<MinimaValue> RollWinDeque = new Deque<MinimaValue>(); //Niro.Deque nuget.
    static int i2; //used by the struct of the Deque (not just for result storage)


    //====================================== my initialy proposed caching algo
    static void CalcCachingMin(double currentNum)
    {
        RollWinArray[CurrentLocation] = currentNum;
        if (currentNum <= Low)
        {
            LowLocation = CurrentLocation;
            Low = currentNum;
        }
        else if (CurrentLocation == LowLocation)
            ReFindHighest();

        CurrentLocation++;
        if (CurrentLocation == Window) CurrentLocation = 0; //this is faster
        //CurrentLocation = CurrentLocation % Window; //this is slower, still over 10 fold faster than ascending minima

        Result1[i1++] = Low;
    }

    //full iteration run each time lowest is overwritten.
    static void ReFindHighest()
    {
        Low = RollWinArray[0];
        LowLocation = 0; //bug fix. missing from initial version.
        for (int i = 1; i < Window; i++)
            if (RollWinArray[i] < Low)
            {
                Low = RollWinArray[i];
                LowLocation = i;
            }
    }

    //======================================= Ascending Minima algo based on http://stackoverflow.com/a/14823809/2381899 
    private struct MinimaValue
    {
        public int RemoveIndex { get; set; }
        public double Value { get; set; }
    }

    public static void CalcAscendingMinima (double newNum)
    { //same algo as the extension method below, but used on external arrays, and fed with 1 data point at a time like in the projected real time app.
            while (RollWinDeque.Count > 0 && i2 >= RollWinDeque[0].RemoveIndex)
                RollWinDeque.RemoveFromFront();
            while (RollWinDeque.Count > 0 && RollWinDeque[RollWinDeque.Count - 1].Value >= newNum)
                RollWinDeque.RemoveFromBack();
            RollWinDeque.AddToBack(new MinimaValue { RemoveIndex = i2 + Window, Value = newNum });
            Result2[i2++] = RollWinDeque[0].Value;
    }

    public static double[] GetMin(this double[] input, int window)
    {   //this is the initial method extesion for ascending mimima 
        //taken from http://stackoverflow.com/a/14823809/2381899
        var queue = new Deque<MinimaValue>();
        var result = new double[input.Length];

        for (int i = 0; i < input.Length; i++)
        {
            var val = input[i];

            // Note: in Nito.Deque, queue[0] is the front
            while (queue.Count > 0 && i >= queue[0].RemoveIndex)
                queue.RemoveFromFront();

            while (queue.Count > 0 && queue[queue.Count - 1].Value >= val)
                queue.RemoveFromBack();

            queue.AddToBack(new MinimaValue { RemoveIndex = i + window, Value = val });

            result[i] = queue[0].Value;
        }

        return result;
    }

    //============================================ Test program.
    static void Main(string[] args)
    { //this it the test program. 
        //it runs several attempts of both algos on the same data.
        for (int j = 0; j < 10; j++)
        {
            Low = 12000;
            for (int i = 0; i < Window; i++)
                RollWinArray[i] = 10000000;
            //Fill the data + functional test - generate 100 numbers and check them in as you go:
            InputArr[0] = 12000;
            for (int i = 1; i < FullDataSize; i++) //fill the Input array with random data.
                //InputArr[i] = r.Next(100) + 11000;//simple data.
                InputArr[i] = InputArr[i - 1] + r.NextDouble() - 0.5; //brownian motion data.

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i = 0; i < FullDataSize; i++) //run the Caching algo.
                CalcCachingMin(InputArr[i]);

            stopwatch.Stop();
            Console.WriteLine("Caching  : " + stopwatch.ElapsedTicks + " mS: " + stopwatch.ElapsedMilliseconds);
            stopwatch.Reset();


            stopwatch.Start();
            for (int i = 0; i < FullDataSize; i++) //run the Ascending Minima algo
                CalcAscendingMinima(InputArr[i]);

            stopwatch.Stop();
            Console.WriteLine("AscMimima: " + stopwatch.ElapsedTicks + " mS: " + stopwatch.ElapsedMilliseconds);
            stopwatch.Reset();

            i1 = 0; i2 = 0; RollWinDeque.Clear();
        }

        for (int i = 0; i < FullDataSize; i++) //test the results.
            if (Result2[i] != Result1[i]) //this is a test that algos are valid. Errors (mismatches) are printed.
                Console.WriteLine("Current:" + InputArr[i].ToString("#.00") + "\tLowest of " + Window + "last is " + Result1[i].ToString("#.00") + " " + Result2[i].ToString("#.00") + "\t" + (Result1[i] == Result2[i])); //for validation purposes only.

        Console.ReadLine();
    }


}

c# - 効率的なローリング最大および最小ウィンドウ

5 に答える 5

Related

Reference