无溢出异常的平均函数

这个答案用于建议分别存储商和余数(mod count)。该解决方案的空间效率更低,代码更复杂。

为了精确计算平均值,必须跟踪总数。除非你愿意牺牲准确性,否则没有办法解决这个问题。您可以尝试以奇特的方式存储总数,但最终如果算法正确,您必须跟踪它。

对于单通算法,这很容易证明。假设您不能重建前面所有项目的总数,考虑到算法在处理这些项目之后的整个状态。但是等一下,我们可以模拟算法,然后接收一系列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<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]。

您需要定义两个变量:

意思是 和 余数 .

最初 mean = 0, remainder = 0.

在步骤 我 你需要改变 意思是 和 余数 按以下方式:

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<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;

当然,您可以以某种方式实现它,使其更易于重用,例如作为 IEnumerable<long> .

如果有这个问题,我会怎么做。首先,让我们定义一个非常简单的有理数类,它包含两个属性-被除数和除数,以及一个用于添加两个复数的运算符。这是它的样子:

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; }
}

第二部分非常简单。假设我们有一个数字数组。它们的平均值是通过和(数字)/长度(数字)来估计的,这与数字[0]/长度+数字[1]/长度+…+数字[N]/长度。为了能够计算出这一点,我们将把每个数字[i]/长度表示为一个整数和一个有理部分(提醒)。这是它的样子:

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 );

在最后,我们有一个有理数列表,和一个整数,我们把它们相加,得到序列的平均值,没有溢出。对于任何类型,都可以采用相同的方法,而不会出现溢出,并且不会丢失精度。

编辑:

为什么这样做:

定义:一组数字。

如果平均值(A)=sum(A)/len(A)=gt;

平均值(a)=a[0]/len(a)+a[1]/len(a)+a[2]/len(a)++a[n]/len(2)=>

如果我们把a定义为一个满足这个条件的数:a=x+(y/len(a)),这本质上是这样的,因为如果你把a除以b,我们得到x,并有一个有理数(y/b)。

=这样

平均值(A)=A1+A2+A3+…+An=x1+x2+x3+x4+…+提醒1+提醒2+…;

把所有的部分加起来,把提醒保持在有理数形式。最后,我们得到一个整数和一个有理数,求和得到平均值(A)。根据您想要的精度,您只需将其应用于末尾的有理数。

用LINQ简单回答…

var data = new[] { int.MaxValue, int.MaxValue, int.MaxValue };
var mean = (int)data.Select(d => (double)d / data.Count()).Sum();

取决于您可能想要强制的设置fo数据的大小 data .ToList() 或 .ToArray() 在处理此方法之前,不能对每个过程重新查询计数。(或者你可以在 .Select(..).Sum() )

如果你 知道 在这之前,你所有的数字都将是“大的”(意思是“更接近”)。 long.MaxValue 大于零),您可以计算 他们的距离 最大值 ,则数字的平均值为 最大值 少一些。

但是,如果(m)任何一个数字 远的 从 最大值 所以这是马的课程…

我想一定有妥协的余地。如果数字真的变大了,那么低阶的几个数字(比如低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;
}

怎么样 BigInteger 在视觉J中。

如果你愿意牺牲精度,你可以做如下的事情:

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();

你可以保持一个滚动平均值,每个大数字更新一次。

使用 IntX codeplex上的库。

nextaverage=当前平均值+(newvalue-当前平均值)/(当前观察值+1)

这是我的一个扩展方法版本,可以帮助解决这个问题。

    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;
    }

设avg(n)为前n个数的平均值,data[n]为第n个数。

Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n

可以避免数值溢出,但当n非常大时会损失精度。

以安全的方式平均特定数字类型的数字,同时也只使用该数字类型实际上是可能的,尽管我建议在实际实现中使用biginteger的帮助。我创建了一个项目 Safe Numeric Calculations 它有一个小结构(int32withboundedrollover),可以在不发生任何溢出的情况下总计2^32 int32s(该结构内部使用两个int32字段来完成此操作,因此不使用较大的数据类型)。

一旦你有了这个总数,你就需要计算总和/总数来得到平均值,你可以这样做(尽管我不建议这样做),通过创建另一个实例int32withboundedrollover,然后再加上total。在每次增量之后,您可以将其与总和进行比较,直到找到平均值的整数部分。从那里你可以剥离剩余部分,然后计算分数部分。可能有一些聪明的诀窍来提高效率,但是这个基本策略当然可以在不需要使用更大的数据类型的情况下工作。

也就是说,当前的实现并不是为此构建的(例如,在Int32WithBoundedRollover上没有比较运算符,尽管添加起来并不太难)。原因是在计算的最后使用biginteger要简单得多。从性能上看,这对大平均值来说并不重要,因为它只会做一次,而且它太干净,太容易理解,担心会想出聪明的东西(至少到目前为止…)。

对于与long数据类型相关的原始问题,只要将int32引用替换为long引用,就可以将int32withBoundedRollover转换为longwithBoundedRollover,它的工作原理应该是一样的。对于Int32,我确实注意到了性能上的巨大差异(如果有兴趣的话)。与biginteger-only方法相比,我生成的方法对于我正在测试的大型(如数据点总数)样本的速度大约快80%(此代码包含在int32withboundedRollover类的单元测试中)。这可能主要是由于在硬件而非软件中执行的Int32操作与bigInteger操作之间存在差异。