平均函数没有溢出exception
.NET Framework 3.5。
我试图计算一些相当大的数字的平均值。
例如：
using System; using System.Linq; class Program { static void Main(string[] args) { var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 }; try { var avg = items.Average(); Console.WriteLine(avg); } catch (OverflowException ex) { Console.WriteLine("can't calculate that!"); } Console.ReadLine(); } } 显然，数学结果是9223372036854775607（ long.MaxValue - 200 ），但我在那里得到了例外。 这是因为.NET Reflector检查的平均扩展方法的实现（在我的机器上）是：
public static double Average(this IEnumerable source) { if (source == null) { throw Error.ArgumentNull("source"); } long num = 0L; long num2 = 0L; foreach (long num3 in source) { num += num3; num2 += 1L; } if (num2 <= 0L) { throw Error.NoElements(); } return (((double) num) / ((double) num2)); }
我知道我可以使用BigInt库（是的，我知道它包含在.NET Framework 4.0中，但我与3.5相关）。
但我仍然想知道在没有外部库的情况下计算整数平均值是否非常直接。 你碰巧知道这样的实施吗？
谢谢！！
更新：
前面的三个大整数的例子只是一个例子来说明溢出问题。 问题是关于计算任何数字集合的平均值， 这些数字可能总和超过类型的最大值的大数字。 抱歉这个混乱。 我也改变了问题的标题，以避免额外的混淆。
谢谢大家!!
这个答案过去常常建议分别存储商和余数（mod计数）。 该解决方案节省空间并且代码复杂度更高。
为了准确计算平均值，您必须跟踪总计。 除非你愿意牺牲准确性，否则没有办法解决这个问题。 您可以尝试以奇特的方式存储总数，但如果算法正确，最终您必须跟踪它。
对于单通道算法，这很容易certificate。 假设在处理完这些项后算法的整个状态，您无法重建所有前面项的总和。 但是等等，我们可以模拟算法然后接收一系列0项，直到我们完成序列。 然后我们可以将结果乘以计数并得到总数。 矛盾。 因此，单程算法必须在某种意义上跟踪总数。
因此，最简单的正确算法将只是总结项目并除以计数。 您所要做的就是选择一个具有足够空间的整数类型来存储总数。 使用BigInteger保证没有问题，所以我建议使用它。
var total = BigInteger.Zero var count = 0 for i in values count += 1 total += i return total / (double)count //warning: possible loss of accuracy, maybe return a Rational instead?
如果您只是在寻找算术平均值，您可以执行如下计算：
public static double Mean(this IEnumerable source) { if (source == null) { throw Error.ArgumentNull("source"); } double count = (double)source.Count(); double mean = 0D; foreach(long x in source) { mean += (double)x/count; } return mean; }
编辑：
在回应评论时，由于执行了大量的划分和补充，这种方式肯定会失去精确度。 对于问题所指出的值，这应该不是问题，但应该考虑。
您可以尝试以下方法：
let元素的数量是N ，数字是arr [0]，..，arr [N-1]。
您需要定义2个变量：
平均值和余数 。
最初mean = 0, remainder = 0.
在步骤i，您需要通过以下方式更改平均值和余数 ：
mean += arr[i] / N; remainder += arr[i] % N; mean += remainder / N; remainder %= N;
在N个步骤之后，你将得到平均变量的正确答案， 余数/ N将是答案的小数部分（我不确定你是否需要它，但无论如何）
如果您大致了解平均值（或者，至少所有数字对将具有最大差异< long.MaxValue ），则可以计算该值的平均差异 。 我举了一个低数字的例子，但它对大数字同样有效。
// Let's say numbers cannot exceed 40. List numbers = new List () { 31 28 24 32 36 29 }; // Average: 30 List diffs = new List (); // This can probably be done more effectively in linq, but to show the idea: foreach(int number in numbers.Skip(1)) { diffs.Add(numbers.First()-number); } // diffs now contains { -3 -6 1 5 -2 } var avgDiff = diffs.Sum() / diffs.Count(); // the average is -1 // To get the average value, just add the average diff to the first value: var totalAverage = numbers.First()+avgDiff;
您当然可以通过某种方式实现这一点，以便更容易重用，例如作为IEnumerable的扩展方法。
如果遇到这个问题，我会怎么做。 首先让我们定义一个非常简单的RationalNumber类，它包含两个属性 – Dividend和Divisor以及一个用于添加两个复数的运算符。 以下是它的外观：
public sealed class RationalNumber { public RationalNumber() { this.Divisor = 1; } public static RationalNumberoperator +( RationalNumberc1, RationalNumber c2 ) { RationalNumber result = new RationalNumber(); Int64 nDividend = ( c1.Dividend * c2.Divisor ) + ( c2.Dividend * c1.Divisor ); Int64 nDivisor = c1.Divisor * c2.Divisor; Int64 nReminder = nDividend % nDivisor; if ( nReminder == 0 ) { // The number is whole result.Dividend = nDividend / nDivisor; } else { Int64 nGreatestCommonDivisor = FindGreatestCommonDivisor( nDividend, nDivisor ); if ( nGreatestCommonDivisor != 0 ) { nDividend = nDividend / nGreatestCommonDivisor; nDivisor = nDivisor / nGreatestCommonDivisor; } result.Dividend = nDividend; result.Divisor = nDivisor; } return result; } private static Int64 FindGreatestCommonDivisor( Int64 a, Int64 b) { Int64 nRemainder; while ( b != 0 ) { nRemainder = a% b; a = b; b = nRemainder; } return a; } // a / b = a is devidend, b is devisor public Int64 Dividend { get; set; } public Int64 Divisor { get; set; } }
第二部分非常简单。 假设我们有一系列数字。 它们的平均值由Sum（数字）/ Length（数字）估算，与Number [0] / Length + Number [1] / Length + … + Number [n] / Length相同。 为了能够计算这个，我们将每个数字[i] /长度表示为整数和理性部分（提醒）。 以下是它的外观：
Int64[] aValues = new Int64[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 }; List list = new List (); Int64 nAverage = 0; for ( Int32 i = 0; i < aValues.Length; ++i ) { Int64 nReminder = aValues[ i ] % aValues.Length; Int64 nWhole = aValues[ i ] / aValues.Length; nAverage += nWhole; if ( nReminder != 0 ) { list.Add( new RationalNumber() { Dividend = nReminder, Divisor = aValues.Length } ); } } RationalNumber rationalTotal = new RationalNumber(); foreach ( var rational in list ) { rationalTotal += rational; } nAverage = nAverage + ( rationalTotal.Dividend / rationalTotal.Divisor );
最后，我们得到了一个有理数的列表，以及一个整数，我们将它们相加并得到序列的平均值而没有溢出。 对于没有溢出的任何类型都可以采用相同的方法，并且不会丢失精度。
编辑：
为何如此有效：
定义：一组数字。
如果平均值（A）= SUM（A）/ LEN（A）=>
平均值（A）= A [0] / LEN（A）+ A [1] / LEN（A）+ A [2] / LEN（A）+ ..... + A [N] / LEN（2） =>
如果我们将An定义为一个满足这个数的数：An = X +（Y / LEN（A）），这实际上是因为如果你将A除以B，我们得到X带有提示的有理数（Y / B） 。
=>所以
平均值（A）= A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... + Reminder1 + Reminder2 + ...;
对整个部分求和，并通过将它们保持在有理数字forms来总结提醒。 最后，我们得到一个整数和一个有理数，它们总和得到平均值（A）。 根据您的精度，您只能将其应用于最后的有理数。
简单回答LINQ …
var data = new[] { int.MaxValue, int.MaxValue, int.MaxValue }; var mean = (int)data.Select(d => (double)d / data.Count()).Sum();
根据数据集的大小，您可能希望在处理此方法之前强制data .ToList()或.ToArray() ，因此无法在每次传递时重新计数。 （或者你可以在.Select(..).Sum()之前调用它。）
如果您事先知道所有数字都将是“大”（在“更接近long.MaxValue不是零”的意义上），您可以计算它们距long.MaxValue的距离的long.MaxValue ，然后计算数字的平均值很长long.MaxValue少了。
但是，如果（m）任何数字远远不是long.MaxValue ，那么这种方法将失败long.MaxValue ，所以它是课程的马匹……
我想在某个地方或另一个地方必须有妥协。 如果数字确实变得如此之大，那么较低位数（比如低5位数）的几位数字可能不会对结果造成太大影响。
另一个问题是您并不真正了解数据集的大小，特别是在流/实时案例中。 除了（previousAverage * oldCount + newValue）/（oldCount < - oldCount + 1）之外，我没有看到任何其他解决方案
这是一个建议：
*LargestDataTypePossible* currentAverage; *SomeSuitableDatatypeSupportingRationalValues* newValue; *int* count; addToCurrentAverage(value){ newValue = value/100000; count = count + 1; currentAverage = (currentAverage * (count-1) + newValue) / count; } getCurrentAverage(){ return currentAverage * 100000; }
在Visual J＃中如何使用BigInteger 。
如果你愿意牺牲精确度，你可以这样做：
long num2 = 0L; foreach (long num3 in source) { num2 += 1L; } if (num2 <= 0L) { throw Error.NoElements(); } double average = 0; foreach (long num3 in source) { average += (double)num3 / (double)num2; } return average;
也许您可以通过计算调整后的值的平均值来减少每个项目，然后将其乘以集合中的元素数量。 但是，您将在浮点上找到不同数量的操作。
var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 }; var avg = items.Average(i => i / items.Count()) * items.Count();
您可以保持滚动平均值，您为每个大数字更新一次。
在CodePlex上使用IntX库。
NextAverage = CurrentAverage +（NewValue – CurrentAverage）/（CurrentObservations + 1）
这是我的扩展方法版本，可以帮助解决这个问题。
public static long Average(this IEnumerable longs) { long mean = 0; long count = longs.Count(); foreach (var val in longs) { mean += val / count; } return mean; }
设Avg（n）为前n个数的平均值，data [n]为第n个数。
Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n
当n非常大时，可以避免值溢出但损失精度。
虽然我建议在实际实现中使用BigInteger的帮助，但是以安全的方式平均特定数字类型的数字，同时也只使用该数字类型。 我创建了一个安全数值计算项目，它具有一个小结构（Int32WithBoundedRollover），它可以总计最多2 ^ 32个int32而没有任何溢出（该结构内部使用两个int32字段来执行此操作，因此不使用更大的数据类型）。
一旦你得到这个总和，你需要计算总和/总数来得到平均值，你可以做（虽然我不推荐它）通过创建然后再增加另一个Int32WithBoundedRollover实例。 在每个增量之后，您可以将它与总和进行比较，直到找到平均值的整数部分。 从那里你可以剥离剩余部分并计算分数部分。 可能有一些聪明的技巧可以提高效率，但这种基本策略肯定无需采用更大的数据类型。
话虽如此，当前的实现并不是为此构建的（例如，Int32WithBoundedRollover上没有比较运算符，尽管添加起来并不太难）。 原因是最后使用BigInteger进行计算要简单得多。 性能方面，这对于大型平均值来说并不重要，因为它只会进行一次，并且它太干净且易于理解而担心想出一些聪明的东西（至少到目前为止……）。
至于你关于长数据类型的原始问题，Int32WithBoundedRollover可以通过交换长引用的int32引用转换为LongWithBoundedRollover，它应该工作相同。 对于Int32s，我确实注意到性能上有很大差异（如果感兴趣的话）。 与仅使用BigInteger的方法相比，我生成的方法对于我正在测试的大型（如数据点的总数）样本快了大约80％（此代码包含在Int32WithBoundedRollover类的unit testing中）。 这可能主要是由于Big32teger操作在硬件而不是软件中完成的int32操作之间的差异。