。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();
}
}
很显然,数学结果是9223372036854754775607(long.MaxValue - 200
),但我在那里遇到了一个例外。这是因为.NET Reflector检查的(在我的机器上)Average扩展方法的实现是:
public static double Average(this IEnumerable<long> 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中的included,但我绑定到3.5)。
但是我仍然想知道是否有一个非常简单的实现,无需外部库就可以计算整数的平均值。您碰巧知道这种实现吗?
谢谢!
UPDATE:
先前的示例,由三个大整数组成,仅是说明溢出问题的示例。问题是要计算any组数字的平均值,这些平均值可能加起来超过类型最大值的最大值。对不起,这种混乱。我还更改了问题的标题,以免造成其他混乱。
谢谢大家!
此答案用于建议分别存储商和余数(模数)。该解决方案空间效率较低,代码复杂度更高。
为了准确计算平均值,您必须跟踪总数。除非您愿意牺牲准确性,否则无法解决此问题。您可以尝试以总计的方式存储总数,但是如果算法正确,最终您必须对其进行跟踪。
对于单遍算法,这很容易证明。假设在处理完这些项目后算法的整个状态下,您无法重构所有前面的项目。但是,等等,我们可以模拟算法,然后接收一系列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?
如果您愿意牺牲精度,则可以执行以下操作:
也许您可以通过计算调整值的平均值,然后将其乘以集合中元素的数量来减少每一项。但是,您会发现对浮点数的操作数量略有不同。
您可以保持滚动平均值,每增加一个大数就更新一次。
使用CodePlex上的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;
库。
NextAverage = CurrentAverage +(NewValue-CurrentAverage)/(CurrentObservations + 1)
这是我的扩展方法版本,可以帮助解决这个问题。
让Avg(n)为前n个数的平均值,而data [n]为第n个数。
尽管可以建议在实际实现中使用BigInteger的帮助,但实际上可以以安全的方式对特定数字类型的数字进行平均,同时也仅使用该数字类型。我为 public static long Average(this IEnumerable<long> longs)
{
long mean = 0;
long count = longs.Count();
foreach (var val in longs)
{
mean += val / count;
}
return mean;
}
创建了一个具有较小结构(Int32WithBoundedRollover)的项目,该项目可以总计2 ^ 32个int32,而没有任何溢出(该结构内部使用两个int32字段来执行此操作,因此不使用较大的数据类型)。 >
一旦有了这个总和,您就需要计算总和/求和,以得到平均值,您可以通过创建一个Int32WithBoundedRollover实例,然后再对其进行累加来实现(尽管我不建议这样做)。每次增加之后,您可以将其与总和进行比较,直到找到平均值的整数部分为止。从那里可以剥离剩余部分并计算小数部分。可能有一些巧妙的技巧可以提高效率,但是这种基本策略肯定会起作用,而无需诉诸更大的数据类型。
对于两个正数(或两个负数),我从Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n
找到了一个非常优雅的解决方案。
如果您只是在寻找算术平均值,则可以像这样执行计算:
public static double Mean(this IEnumerable<long> 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;
}
编辑:
为了回应评论,由于执行了许多除法和加法运算,因此肯定会失去精度。对于问题所指示的值,这应该不成问题,但应予以考虑。
您可以尝试以下方法:
元素的个数为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;
在步骤之后,您将在mean变量中获得正确的答案,而remainder / N将是答案的一部分(我不确定您是否需要它,但是无论如何)N
C0]),则可以计算平均值与该值的差异。我以数字较小的示例为例,但对于较大的数字同样适用。
long.MaxValue
当然,您可以通过某种方式实现此目的,使其更易于重用,例如作为// Let's say numbers cannot exceed 40.
List<int> numbers = new List<int>() { 31 28 24 32 36 29 }; // Average: 30
List<int> diffs = new List<int>();
// 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;
的扩展方法。
如果遇到此问题,我将怎么办。首先让我们定义一个非常简单的RationalNumber类,它包含两个属性-Dividend和Divisor以及一个用于添加两个复数的运算符。外观如下:
IEnumerable<long>
第二部分确实很容易。假设我们有一个数字数组。它们的平均值由Sum(Numbers)/ Length(Numbers)估计,与Number [0] / Length + Number [1] / Length + ... + Number [n] / Length相同。为了能够对此进行计算,我们将每个Number [i] / Length表示为一个整数和一个有理数部分(提醒)。外观如下:
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; }
}
最后,我们有一个有理数的列表,还有一个我们求和在一起的整数,得到序列的平均值而没有溢出。任何类型都可以采用相同的方法而不会产生溢出,并且不会丢失任何精度。
编辑:
为什么有效:
定义:一组数字。
如果平均值(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)。
=>如此
[Average(A)= A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... +提醒1 +提醒2 + ...;
将所有部分加起来,并通过将它们保持在合理的数字形式中来对提醒进行求和。最后,我们得到一个整数和一个有理数,它们的总和得出平均值(A)。根据您想要的精度,可以将其仅应用于最后的有理数。
使用LINQ的简单答案...
Int64[] aValues = new Int64[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };
List<RationalNumber> list = new List<RationalNumber>();
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 );
根据所设置的数据大小,您可能需要在处理此方法之前强制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()
比零更接近”),则可以计算出它们与[C0的距离],则数字的平均值要少long.MaxValue
。
但是,如果(m)个数字中的任何一个离long.MaxValue
far],则此方法将失败,因此,这是课程必不可少的东西...
我想在某个地方或其他地方必须做出妥协。如果数字真的变大了,那么较低位数的几位数字(例如较低的5位数字)可能不会对结果产生太大影响。
关于Visual J#中的long.MaxValue
。