防止长期平均溢出? [英] prevent long running averaging from overflow?

问题描述

假设我要计算数据集的平均值，例如

suppose I want to calculate average value of a data-set such as

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

迟早total或count值将溢出，因此我使它不记得该值的总和:

sooner or later the total or count value will overflow, so I make it doesn't remember the total value by :

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

似乎它们会溢出更长的时间，但是average和count之间的乘法会导致溢出问题，因此下一个解决方案是:

it seems they will overflow longer, but the multiplication between average and count lead to overflow problem, so next solution is:

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

似乎更好，下一个问题是如何防止count溢出?

seems better, next problem is how to prevent count from overflow?

推荐答案

聚合存储桶.

我们选择的水桶大小要比squareRoot(MAXINT)小得多.为了简单起见，我们选择10.

We pick a bucket size that's comfortably less than squareRoot(MAXINT). To keep it simple, let's pick 10.

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

Each new value is added to the current bucket, and the moving average can be computed as you describe.

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

When the bucket is full start a new bucket, remembering the average of the full bucket. We can safely calculate the overall average by combining the averages of the full buckets and the current, partial bucket. When we get to 10 full buckets, we create a bigger bucket, capacity 100.

要计算总平均值，我们首先计算"10s"的平均值，然后将其与"100s"组合.此模式重复"1,000s"，"10,000s"，依此类推.在每个阶段，我们只需要考虑两个级别，该级别比上一个级别大10倍.

To compute the total average we first compute the average of the "10s" and then combine that with the "100s". This pattern repeats for "1,000s" "10,000s" and so on. At each stage we only need to consider two levels one 10 x bigger than the previous one.

这篇关于防止长期平均溢出?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！