防止长时间运行平均溢出？

Question

假设我想计算数据集的平均值,例如

class Averager {
   float total;
   size_t count;
   float addData (float value) {
       this->total += value;
       return this->total / ++this->count;
   }
}

早晚total或count值会溢出,所以我让不记得总价值:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage = (this->currentAverage*count + value) / ++count;
       return this->currentAverage;
   }
}

看来他们会溢出较长,但之间的乘法average和count导致溢出的问题,所以接下来的解决办法是:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage += (value - this->currentAverage) / ++count;
       return this->currentAverage;
   }
}

似乎更好,接下来的问题是如何防止count溢出？

Answer 1

聚合桶.

我们选择的铲斗尺寸比squareRoot(MAXINT)小得多.为了简单起见,我们选择10.

每个新值都会添加到当前存储桶中,并且可以按照您的描述计算移动平均值.

当存储桶已满时,启动一个新存储桶,记住完整存储桶的平均值.我们可以通过结合满桶的平均值和当前的部分桶来安全地计算总体平均值.当我们达到10个满桶时,我们会创建一个更大的桶,容量为100.

为了计算总平均值,我们首先计算"10s"的平均值,然后将其与"100s"相结合.这种模式重复"1,000s""10,000s"等等.在每个阶段,我们只需要考虑比前一个大10倍的两个级别.