计算所有值的总和超过双倍限制的平均值是一个很好的解决scheme？
我有一个要求来计算一个非常大的双打（10 ^ 9值）的平均值。 这些值的总和超过了双倍的上限，所以有人知道计算平均值的任何巧妙的小技巧，也不需要计算总和？
我正在使用Java 1.5。
我想问你的第一个问题是：
- 你事先知道数值吗？
如果没有，那么你别无select，只能总结，计数和分裂，做平均。 如果Double精度不够高来处理这个问题，那么运气不好，你不能使用Double ，你需要find一个可以处理的数据types。
另一方面，如果你事先知道数值，你可以看看你在做什么，并改变你的做法，但保持整体结果。
存储在某个集合A中的N个值的平均值为：
A[0] A[1] A[2] A[3] A[N-1] A[N] ---- + ---- + ---- + ---- + .... + ------ + ---- NNNNNN
要计算此结果的子集，可以将计算拆分为相同大小的集合，因此您可以对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 / --------------------- + -------------------- + \\ -------------- NNN --- --- --- 3 3 3
请注意，您需要相同大小的集合 ，否则最后集合中的数字与之前的所有集合相比将没有足够的值，将对最终结果产生较大的影响。
按顺序考虑数字1-7，如果你select一个3的设置大小，你会得到这个结果：
/ 1 2 3 \ / 4 5 6 \ / 7 \ | - + - + - | + | - + - + - | + | - | \ 3 3 3 / \ 3 3 3 / \ 3 / ----------- ----------- --- yyy
这使：
2 5 7/3 - + - + --- yyy
如果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（注意结尾的两个零）做上面的练习，那么你会得到上面的结果。
换句话说，如果你不能将值的数量分成相同大小的集合，那么最后的集合将被计算为与所有集合之前的集合具有相同数量的值，但是它将被填充为零所有缺失的值。
所以， 你需要同样大小的集合 。 如果您的原始input集合包含一个素数的值，那么运气不好。
我在这里担心的是失去精度。 我不完全确定Double在这种情况下会给你足够好的精度，如果它最初不能保持整个值的总和。
你可以反复计算平均值 。 这个algorithm很简单，快速，你只需要处理每个值一次，variables永远不会超过集合中最大的值，所以你不会得到溢出。
double mean(double[] ary) { double avg = 0; int t = 1; for (double x : ary) { avg += (x - avg) / t; ++t; } return avg; }
avg内部的值始终是迄今处理的所有值的平均值。 换句话说，如果所有的值都是有限的，你不应该得到溢出。
恕我直言，解决您的问题最健壮的方式是
- sorting你的设置
- 以总和不会溢出的元素组进行拆分 – 因为它们被sorting，这是快速和容易的
- 做每组的总和 – 除以组的大小
- 做组的总和（可能调用相同的algorithmrecursion） – 要知道，如果组的大小不一样，你将不得不按他们的大小加权
这种方法的一个好处就是它可以很好地扩展，如果你有非常多的元素可以加总的话 – 还有大量的处理器/机器用来做math
除了使用已经build议的更好的方法之外，您可以使用BigDecimal来进行计算。 （牢记这是不可改变的）
请澄清这些值的潜在范围。
假设一个double有一个范围〜= +/- 10 ^ 308，并且你总结了10 ^ 9的值，那么在你的问题中build议的表观范围就是10 ^ 299的值。
这似乎有点，不太可能…
如果你的数值真的很大，那么用一个正常的双数你只有17位有效的十进制数字来处理，所以你甚至会想到平均数值，然后丢掉大约280位数的信息。
我也会注意到（因为没有其他人），任何一组数字X ：
mean(X) = sum(X[i] - c) + c ------------- N
任何任意常数c 。
在这个特定的问题中，设置c = min(X) 可能会大大降低求和过程中溢出的风险。
我可以虚心地提出问题陈述是不完整的吗？
将所有值除以设定的大小，然后总结
一个double可以除以2的幂而不会损失精度。 所以如果你唯一的问题是如果总和的绝对大小，你可以预先缩放你的数字，然后总结他们。 但是对于这样一个大小的数据集，仍然存在一个风险，那就是你将会遇到一个小数目的情况，而小数字最终会被大部分（或完全）忽略掉。
例如，当您将2.2e-20添加到9.0e20时，结果为9.0e20，因为一旦调整了缩放比例以使它们的数字可以相加，那么较小的数字就是0.双精度只能保持大约17位数字，需要超过40位数字将这两个数字加在一起而不会丢失。
所以，根据你的数据集和你能承受的精度数字，你可能需要做其他事情。 将数据分解为集合将有所帮助，但是更好的方法来保持精度可能是确定一个粗略的平均值（您可能已经知道这个数字）。 然后在总和之前从粗略平均值中减去每个值。 这样，你总结的距离平均，所以你的总和不应该变得很大。
然后你把平均三angular洲，并加上你的粗略总和得到正确的平均值。 跟踪最小和最大三angular洲也将告诉你在求和过程中你失去了多less精度。 如果你有很多时间，需要一个非常准确的结果，你可以迭代。
您可以取平均数量不超过限制的平均数。
选项1是使用任意精度的库，所以你没有上限。
其他选项（失去精确度）是一次总结，而不是一次总结，或在总结前划分。
所以我不再重复自己，让我说我假设数字列表是正态分布的，而且在溢出之前可以总结许多数字。 该技术仍然适用于非正常的发行版，但有些东西不符合我在下面描述的期望。
–
总结一个子系列，跟踪你吃了多less数字，直到你接近溢出，然后取平均值。 这会给你一个平均值a0，并计数n0。 重复，直到你用尽了名单。 现在你应该有很多爱妳
每个爱和ni应该是相对接近，可能是例外的最后一口。 你可以通过在列表的最后附近咬下来来减轻这种负担。
你可以将这些ai的任何子集合起来，通过挑选子集中的任何ni（称之为np），并将该子集中的所有ni都除以该值。 要组合的子集的最大尺寸是n的大致恒定的值。
ni / np应该接近一个。 现在求和ni / np * ai和np /（sum ni）的倍数，跟踪和ni。 如果你需要重复这个程序，这给你一个新的ni，ai组合。
如果需要重复（即ai的数量，ni对比典型的ni大得多），首先尝试将所有的平均值合并到一个n水平，然后再合并到下一个水平，等等。
首先，让你自己熟悉double值的内部表示。 维基百科应该是一个很好的起点。
然后，认为双指数是指数是2的幂的“值加指数”。 最大双值的限制是指数的上限，而不是数值的限制！ 所以你可以将所有大的input数字分成两个足够大的幂。 对于所有足够大的数字，这应该是安全的。 您可以重新乘以该因子的结果来检查是否失去了乘法精度。
在这里，我们将使用一个algorithm
public static double sum(double[] numbers) { double eachSum, tempSum; double factor = Math.pow(2.0,30); // about as large as 10^9 for (double each: numbers) { double temp = each / factor; if (t * factor != each) { eachSum += each; else { tempSum += temp; } } return (tempSum / numbers.length) * factor + (eachSum / numbers.length); }
不要担心增加分裂和繁殖。 FPU会优化它们，因为它们是用两个幂来完成的（比较想象在十进制数的末尾添加和删除数字）。
PS： 另外，你可能想用卡汉求和来提高精度。 Kahan求和避免了当非常大和非常小的数字被总结时的精度损失。
我发布了 一个从这个问题产生的问题 的答案 ，事后意识到我的答案更适合这个问题，而不是那个问题。 我已经在下面转载了。 但我注意到，我的答案类似于Bozho和Anon的组合。 的 。
由于另一个问题被标记为与语言无关，我select了C＃作为我包含的代码示例。 它的相对易用性和易于遵循的语法，以及包含了一些便于这个例程的特性（BCL中的DivRem函数，以及对迭代器函数的支持）以及我自己熟悉的特性这是一个很好的select。 由于这里的OP对Java解决scheme感兴趣，但是我不够Java的stream畅写法，所以如果有人可以把这个代码翻译成Java的话，这可能会很好。
这里的一些math解决scheme是非常好的。 这是一个简单的技术解决scheme。
使用更大的数据types。 这分解成两种可能性：
-
使用高精度的浮点库。 一个人平均需要十亿个数字，可能有资源去购买一个128位（或更长）的浮点库。
我明白这里的缺点。 肯定会比使用内在types慢。 如果值的数量变得太高，你仍然可能会上/下溢。 亚达亚达。
-
如果你的值是整数或者可以很容易地缩放到整数，那么把你的总和保存在一个整数列表中。 当你溢出时，只需添加另一个整数。 这实质上是第一个选项的简化实施。 下面是一个简单的
（未经testing的）C＃示例
class BigMeanSet{ List<uint> list = new List<uint>(); public double GetAverage(IEnumerable<uint> values){ list.Clear(); list.Add(0); uint count = 0; foreach(uint value in values){ Add(0, value); count++; } return DivideBy(count); } void Add(int listIndex, uint value){ if((list[listIndex] += value) < value){ // then overflow has ocurred if(list.Count == listIndex + 1) list.Add(0); Add(listIndex + 1, 1); } } double DivideBy(uint count){ const double shift = 4.0 * 1024 * 1024 * 1024; double rtn = 0; long remainder = 0; for(int i = list.Count - 1; i >= 0; i--){ rtn *= shift; remainder <<= 32; rtn += Math.DivRem(remainder + list[i], count, out remainder); } rtn += remainder / (double)count; return rtn; } }
就像我说的，这是没有经过testing的 – 我没有十亿个值，我真的很想平均 – 所以我可能犯了一两个错误，特别是在 DivideBy函数中，但它应该展示一般的想法。
这应该提供尽可能多的精度，双可以表示，应该适用于任何数量的32位元素，高达2 32 – 1.如果需要更多的元素，那么countvariables将需要扩大， DivideBy函数将增加在复杂性方面，但是我会把它作为读者的一个练习。
就效率而言，它应该比其他任何技术都快或者更快，因为它只需要遍历一次，只执行一次除法操作（也就是其中一组操作），而且大部分的工作都是整数。 尽pipe如此，我并没有对它进行优化，而且我相当肯定，如果有必要的话，它可以稍快些。 开始recursion函数调用和列表索引将是一个好的开始。 再次，为读者做一个练习。 代码旨在易于理解。
如果现在比我更有动力的人觉得要validation代码的正确性，并解决可能出现的问题，请成为我的客人。
我现在testing了这个代码，并做了一些小的更正（在List<uint>构造函数调用中缺less一对括号，并且在DivideBy函数的最后一个分区中有一个不正确的除数）。
我首先运行了1000个随机长度（范围在1到1000之间）的随机整数（范围介于0和2 32 – 1之间）。 这些都是我可以轻松快速地validation准确性的集合，同时对它们运行规范的意思。
然后我用100 *大系列testing，随机长度在10 5到10 9之间 。 这些序列的下限和上限也是随机select的，受到限制，使得该序列适合在32位整数的范围内。 对于任何系列，结果都很容易validation为(lowerbound + upperbound) / 2 。
好吧，这是一个小小的谎言。 大约20或30次成功运行后，我中止了大型testing。 一系列长度为10 9的机器在我的机器上运行不到一分半钟，所以testing这个程序的半小时左右就足以满足我的口味。
对于那些感兴趣的，我的testing代码如下：
static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){ for(uint i = lowerbound; i <= upperbound; i++) yield return i; } static void Test(){ Console.BufferHeight = 1200; Random rnd = new Random(); for(int i = 0; i < 1000; i++){ uint[] numbers = new uint[rnd.Next(1, 1000)]; for(int j = 0; j < numbers.Length; j++) numbers[j] = (uint)rnd.Next(); double sum = 0; foreach(uint n in numbers) sum += n; double avg = sum / numbers.Length; double ans = new BigMeanSet().GetAverage(numbers); Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans); if(avg != ans) Debugger.Break(); } for(int i = 0; i < 100; i++){ uint length = (uint)rnd.Next(100000, 1000000001); uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length); uint upperbound = lowerbound + length; double avg = ((double)lowerbound + upperbound) / 2; double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound)); Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans); if(avg != ans) Debugger.Break(); } }
对整个数据集的一小组随机抽样通常会产生一个“足够好”的解决scheme。 你显然必须根据系统要求自己做出这个决定。 样本量可能非常小，仍然可以获得相当好的答案。 这可以通过计算随机select样本的数量的平均值来自适应计算 – 平均值将在一定的时间间隔内收敛。
抽样不仅解决了双重溢出问题，而且速度更快。 不适用于所有问题，但对于许多问题肯定有用。
考虑一下：
avg(n1) : n1 = a1 avg(n1, n2) : ((1/2)*n1)+((1/2)*n2) = ((1/2)*a1)+((1/2)*n2) = a2 avg(n1, n2, n3) : ((1/3)*n1)+((1/3)*n2)+((1/3)*n3) = ((2/3)*a2)+((1/3)*n3) = a3
因此，对于任意大小的双精度集合，您可以这样做（这是用C＃编写的，但是我很确定它可以很容易地转换为Java）：
static double GetAverage(IEnumerable<double> values) { int i = 0; double avg = 0.0; foreach (double value in values) { avg = (((double)i / (double)(i + 1)) * avg) + ((1.0 / (double)(i + 1)) * value); i++; } return avg; }
实际上，这很好地融入（已经由martinus提供）：
static double GetAverage(IEnumerable<double> values) { int i = 1; double avg = 0.0; foreach (double value in values) { avg += (value - avg) / (i++); } return avg; }
我写了一个快速testing，试用这个函数来对付总结值和除以计数（ GetAverage_old ）的常规方法。 对于我的input，我写了这个快速函数，根据需要返回任意数量的随机正数。
static IEnumerable<double> GetRandomDoubles(long numValues, double maxValue, int seed) { Random r = new Random(seed); for (long i = 0L; i < numValues; i++) yield return r.NextDouble() * maxValue; yield break; }
这里是几个testing试验的结果：
long N = 100L; double max = double.MaxValue * 0.01; IEnumerable<double> doubles = GetRandomDoubles(N, max, 0); double oldWay = GetAverage_old(doubles); // 1.00535024998431E+306 double newWay = GetAverage(doubles); // 1.00535024998431E+306 doubles = GetRandomDoubles(N, max, 1); oldWay = GetAverage_old(doubles); // 8.75142021696299E+305 newWay = GetAverage(doubles); // 8.75142021696299E+305 doubles = GetRandomDoubles(N, max, 2); oldWay = GetAverage_old(doubles); // 8.70772312848651E+305 newWay = GetAverage(doubles); // 8.70772312848651E+305
好的，但10 ^ 9的值呢？
long N = 1000000000; double max = 100.0; // we start small, to verify accuracy IEnumerable<double> doubles = GetRandomDoubles(N, max, 0); double oldWay = GetAverage_old(doubles); // 49.9994879713857 double newWay = GetAverage(doubles); // 49.9994879713868 -- pretty close max = double.MaxValue * 0.001; // now let's try something enormous doubles = GetRandomDoubles(N, max, 0); oldWay = GetAverage_old(doubles); // Infinity newWay = GetAverage(doubles); // 8.98837362725198E+305 -- no overflow
当然，这个解决scheme的可接受程度将取决于您的精度要求。 但值得考虑。
查看该部分的累计移动平均线
（n 1 + n 2 + … + n k ）/ k =（n 1 + n 2 ）/ k +（n 3 + n 4 ）/ k + … +（n k-1 + n k ） / k，如果k是偶数
（n 1 + n 2 + … + n k ）/ k = n 1 / k +（n 2 + n 3 ）/ k + … +（n k-1 + n k ）/ k，很奇怪
为什么这么多复杂的长答案。 这里是find运行平均值的最简单的方法，直到现在，无需知道有多less元素或大小等。
long int i = 0; 双平均数= 0; （仍有元素）{average = average *（i / i + 1）+ X [i] /（i + 1）; 我++; } return average;
