我实现了一个简单的统计引擎,使用deque提供数据队列来返回滚动平均值和方差。
deque由与值的滚动数相等的条目数构成。
当一个新值到达时,最旧的值会从前面弹出,新的值会推到后面。
我需要确保这不会在内存中增长,因为它预计将作为后台任务运行很长一段时间。
deque在使用中的堆上分配吗?是否有可以用来调整其大小的标志?
我在RHEL 5.3 上使用G++4.1.2
本质上,任何动态大小的容器都会从堆中分配内存。另一个问题概述了deque的实施情况。
但在您的特定情况下,队列总是具有相同的大小。如果您遇到deque的问题,那么在固定大小的数组上使用循环缓冲区来实现一个简单的固定大小队列可能是有益的。这个实现应该具有从根本上更好的内存行为(因为它从不需要重新分配)。如果没有分析数据,很难评估它的优势是否值得实施。
作为一个提示,如果你不需要跟踪值,有一个很棒的算法,它非常轻量级(我甚至在8bit micros上使用它),而且是准确的。
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;
};
该算法由B.p.Welford创建,发表在Donald Knuth的《计算机编程艺术》第2卷第232页第3版中。
http://www.johndcook.com/standard_deviation.html
规范将实现细节留给供应商。然而,由于在两端插入是有效的,因此它很可能是作为堆上的链接结构来实现的。也就是说,当你从堆里弹出一些东西时,它应该被解构,所以你的总内存使用量不应该攀升。