std::deque 内存使用

Question

我已经实现了一个简单的统计引擎，使用双端队列提供数据队列来返回滚动平均值和方差。

双端队列由多个条目构成，条目数量等于滚动值的数量。

当新值到达时，最旧的值将从前面弹出，并将新值推到后面。

我需要确保这不会在内存中增长，因为它预计会作为后台任务运行很长时间。

双端队列是否在正在使用的堆上分配？ 是否有可以用来固定其大小的标志？

我在 RHEL 5.3 上使用 G++ 4.1.2

Answer 1

本质上，任何动态大小的容器都会从堆中分配内存。另一个问题提供了双端队列实现的概述。

但在您的特定情况下，队列始终具有相同的大小。如果您遇到双端队列问题，使用 循环缓冲区实现简单的固定大小队列可能会有所帮助 在固定大小的数组上。此实现应该具有从根本上更好的内存行为（因为它从不需要重新分配）。如果不分析数据，很难评估其优势是否值得实施。

Answer 2

提示一下，如果您不需要跟踪这些值，可以使用这个很棒的算法，它非常轻量级（我什至在 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 的《计算机编程艺术》第 2 卷第 232 页第 3 版中介绍。

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

Answer 3

该规范将实施细节留给供应商。然而，由于两端的插入效率很高，因此它很可能在堆上实现为链接结构。话虽如此，当您从堆中弹出某些内容时，它应该被解构，因此您的总内存使用量不应增加。