在所有值的总和超过双精度限制的情况下计算平均值的好的解决方案是什么？

Question

我需要计算一组非常大的双打（10^9 值）的平均值。这些值的总和超过了双精度数的上限，那么有没有人知道计算不需要计算总和的平均值的巧妙小技巧？

我正在使用 Java 1.5。

原文由 Simon 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以 迭代计算平均值。该算法简单、快速，您只需处理每个值一次，并且变量永远不会大于集合中的最大值，因此不会溢出。

 double mean(double[] ary) {
  double avg = 0;
  int t = 1;
  for (double x : ary) {
    avg += (x - avg) / t;
    ++t;
  }
  return avg;
}

在循环内部 avg 始终是迄今为止处理的所有值的平均值。换句话说，如果所有值都是有限的，则不应发生溢出。

原文由 martinus 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我想问你的第一个问题是：

• 你事先知道值的数量吗？

如果不是，那么你别无选择，只能求和、计数、除以求平均。如果 Double 不够高的精度来处理这个，那么运气不好，你不能使用 Double ，你需要找到可以处理它的数据类型。

另一方面，如果您 确实 事先知道值的数量，则可以查看您真正在做什么并更改 您 的操作方式，但保持总体结果不变。

存储在某个集合 A 中的 N 个值的平均值是这样的：

 A[0]   A[1]   A[2]   A[3]          A[N-1]   A[N]
---- + ---- + ---- + ---- + .... + ------ + ----
 N      N      N      N               N       N

要计算此结果的子集，您可以将计算拆分为大小相等的集合，因此您可以对 3 值集合执行此操作（假设值的数量可以被 3 整除，否则您需要一个不同的除数）

 / A[0]   A[1]   A[2] \   / A[3]   A[4]   A[5] \   //      A[N-1]   A[N] \
| ---- + ---- + ---- |   | ---- + ---- + ---- |   \\    + ------ + ---- |
\  3      3      3   /   \  3      3      3   /   //        3       3   /
 --------------------- +  --------------------  + \\      --------------
          N                        N                        N
         ---                      ---                      ---
          3                        3                        3

请注意，您需要 大小相同的集合，否则最后一组中的数字与之前的所有集合相比没有足够的值，会对最终结果产生更大的影响。

依次考虑数字 1-7，如果您选择 set-size 为 3，您将得到以下结果：

 / 1   2   3 \   / 4   5   6 \   / 7 \
| - + - + - | + | - + - + - | + | - |
\ 3   3   3 /   \ 3   3   3 /   \ 3 /
 -----------     -----------     ---
      y               y           y

这使：

      2   5   7/3
     - + - + ---
     y   y    y

如果所有集合的 y 都是 3，您会得到：

      2   5   7/3
     - + - + ---
     3   3    3

这使：

 2*3   5*3    7
--- + --- + ---
 9     9     9

这是：

 6   15   7
- + -- + -
9    9   9

总计：

 28
-- ~ 3,1111111111111111111111.........1111111.........
 9

1-7的平均值，是4。显然这不行。请注意，如果您使用数字 1、2、3、4、5、6、7、0、0（注意末尾的两个零）进行上述练习，那么您将得到上述结果。

换句话说，如果您不能将值的数量拆分为大小相等的集合，则最后一个集合将被计算为与它之前的所有集合具有相同数量的值，但它将用零填充所有缺失值。

所以， 你需要同样大小的集合。如果您的原始输入集包含质数个值，那就倒霉了。

不过，我在这里担心的是精度损失。我不完全确定 Double 在这种情况下是否会给你足够好的精度，如果它最初不能保存值的全部总和。

原文由 Lasse V. Karlsen 发布，翻译遵循 CC BY-SA 2.5 许可协议