C++のブーストの場合、最小値とローリングの最大値は？

Question

Boostアキュムレータを使用してローリングウィンドウ全体の平均を追跡するコードがあります。これは「ローリング平均」です。ローリング平均に加えて、この同じローリングウインドウで最小値と最大値を追跡したいと思います。

ブーストアキュムレータと転がり分とローリング最大を計算する方法はありますか？私はrolling_meanに使用アキュムレータに最小値と最大値のタグを追加しようとしたが、それは私が欲しいものを私に与えていない...

をする方法を見ていないです。

typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t; 

は

typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t; 

なるしかし、minとmaxは、ここで提供さは、平均値と同じローリングウィンドウに限定されるものではなく、全体アキュムレータにわたって計算されます。

ブーストdocumentationは、最小および最大がすべてのサンプルにわたって計算され、ローリングウィンドウに限定されないことを示しています。彼らはサンプルを制限したり重み付けする方法を提供していないようです。

ローリングウィンドウ全体に平均/最小/最大をレポートしたいと考えています。

私は現在Boostバージョン1.48.0を使用しています。私は、最新バージョン（1.54.0）のドキュメントを見て、そこに実装されている最小/最大のローリングを見ていません。

私はsliding window minimumを追跡する非ブースト方法を発見したが、これは私はどちらか欲しいものではありません。前回の最小値/最大値より大きい/小さい値であるため、値を削除したくない場合は、rolling_meanが不正確になる可能性があります。

Answer 1

アキュムレータが最小/最大のローリングを行うことはできません。

問題は非常に簡単です：定義により、かなりのアキュムレータはOを使用しています（1）データ - それは、処理されるデータを格納しません。現在の最小値/最大値の範囲外になると現在の最小値/最大値を変更するだけで、O（1）データで最小値または最大値を維持できます。ウィンドウの

は、しかし、それは逆を行うために準備する必要があります：現在の分が窓の外に出るとき、それは新しい最小を見つける必要がある - ウィンドウ内の次に小さい番号を。もちろん、最大限のために同様に。

ここで、（たとえば）入力がソートされている場合、最小限になることを考えてみましょう。アイテムがウィンドウから削除されるたびに、最小値が異なります。換言すれば、アキュムレータは現在の最小値を適切に維持するためにウィンドウ内にすべてのデータを格納する必要がある。同様に、降順でソートされた入力の最大値。

要するに、アキュムレータを使用することはできません。すべてのデータをウィンドウに保存する必要があります。

Answer 2

は（そこにおそらく実際には）もっと巧妙なアルゴリズムがあるかもしれませんが、私の頭の上から、私は単に循環バッファにウィンドウを保存して、オンデマンドローリング最小/最大を計算します。結果がキャッシュされ、ウィンドウが変更されたときにダーティ・フラグを設定します。これは、O（1）の累積演算とO（K）の最悪の場合の償却されたO（1）抽出演算を与えます。ここで、Kはウィンドウのサイズです。