4

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

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

totalor值迟早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溢出？

4

6 回答 6

7

聚合桶。

我们选择一个小于 squareRoot(MAXINT) 的存储桶大小。为简单起见，我们选择 10 个。

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

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

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

于 2010-07-23T08:07:46.847 回答
2

使用double total; unsigned long long count;. 您仍然应该担心准确性，但与float.

于 2010-07-23T07:58:50.250 回答
1

您想使用 kahan 的求和算法：

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

另请参阅“每个计算机科学家应该了解的浮点运算”中关于求和错误的部分

http://docs.sun.com/source/806-3568/ncg_goldberg.html#1262

于 2010-07-23T08:49:32.007 回答
1

使用任意精度算术怎么样？

您可以在 Wikipedia 上使用一个库列表：http ://en.wikipedia.org/wiki/Bignum#Libraries

在存储的位数填满可用内存之前，大多数任意精度算术库都不会溢出（这不太可能）。

于 2010-07-23T08:15:37.537 回答
0

您可以使用这些特殊数据类型，其中整数可以无限增长，直到您的 RAM 已满。

于 2010-07-23T08:14:07.197 回答
0

我也只是在想这个。我认为这个解决方案在“动针”的新价值方面是有效的。它仅将其移动到对迄今为止的平均值有贡献的先前值数量的一个因子（自身加 1）。随着输入的增长，它会失去准确性，但平均而言应该是可以接受的。这是一些似乎可以工作的Java代码。我在这里使用浮点数和整数来证明它可以解决这些限制，但你可以使用双精度来获得准确性。这只是为了让您了解如何平均接近最大整数的数组。您需要跟踪输入的总数和当前平均值，而不是输入的总和。如果您的输入总数接近 MAX_INT，这最终将不起作用，您应该使用上面的存储桶建议，

    public float calcAverageContinuous(int[] integers)
{
    float ave = 0;
    for (int i = 0; i < integers.length; i++) {
        ave += (((float)integers[i] - ave) / (float)(i + 1));
    }
    return ave;
}
于 2019-08-17T20:35:39.197 回答