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

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 倍的两个级别。