1

データ キューを提供する両端キューを使用してローリング平均と分散を返す単純な統計エンジンを実装しました。

両端キューは、値のローリング数に等しいエントリ数で構築されます。

新しい値が到着すると、最も古い値が前面からポップされ、新しい値が背面にプッシュされます。

バックグラウンド タスクとして長時間実行されることが予想されるため、これがメモリ内で大きくならないようにする必要があります。

deque は使用中のヒープに割り当てますか? サイズを修正するために使用できるフラグはありますか?

RHEL 5.3 で G++ 4.1.2 を使用しています

4

3 に答える 3

9

基本的に、動的にサイズ設定されたコンテナは、ヒープからメモリを割り当てます。別の質問は、dequeの実装の概要を提供します。

ただし、特定のケースでは、キューのサイズは常に同じです。dequeで問題が発生した場合は、固定サイズの配列に循環バッファを使用して単純な固定サイズのキューを実装すると便利な場合があります。この実装は、基本的に優れたメモリ動作を備えている必要があります（再割り当てが必要ないため）。その利点が実装の手間をかける価値があるかどうかは、データをプロファイリングせずに評価するのは困難です。

于 2011-06-28T13:33:15.550 に答える
3

ヒントとして、値を追跡する必要がない場合は、非常に軽量で (私は 8 ビット マイクロでも使用しています)、正確なこの優れたアルゴリズムがあります。

 class RunningStat
{
public:
    RunningStat() : m_n(0) {}

    void Clear()
    {
        m_n = 0;
    }

    void Push(double x)
    {
        m_n++;

        // See Knuth TAOCP vol 2, 3rd edition, page 232
        if (m_n == 1)
        {
            m_oldM = m_newM = x;
            m_oldS = 0.0;
        }
        else
        {
            m_newM = m_oldM + (x - m_oldM)/m_n;
            m_newS = m_oldS + (x - m_oldM)*(x - m_newM);

            // set up for next iteration
            m_oldM = m_newM; 
            m_oldS = m_newS;
        }
    }

    int NumDataValues() const
    {
        return m_n;
    }

    double Mean() const
    {
        return (m_n > 0) ? m_newM : 0.0;
    }

    double Variance() const
    {
        return ( (m_n > 1) ? m_newS/(m_n - 1) : 0.0 );
    }

    double StandardDeviation() const
    {
        return sqrt( Variance() );
    }

private:
    int m_n;
    double m_oldM, m_newM, m_oldS, m_newS;
};

このアルゴリズムは BP Welford によって作成され、Donald Knuth の Art of Computer Programming、第 2 巻、232 ページ、第 3 版で紹介されています。

http://www.johndcook.com/standard_deviation.html

于 2011-06-28T13:38:21.383 に答える
0

仕様は、実装の詳細をベンダーに任せています。ただし、両端での挿入は効率的であるため、ヒープ上のリンク構造として実装される可能性があります。そうは言っても、ヒープから何かをポップすると、それは分解されるはずなので、合計メモリ使用量が増えないようにする必要があります。

于 2011-06-28T13:34:15.650 に答える