没有溢出异常的平均函数

问题描述 投票:19回答:18

。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组数字的平均值,这些平均值可能加起来超过类型最大值的最大值。对不起,这种混乱。我还更改了问题的标题,以免造成其他混乱。

谢谢大家!

c# .net algorithm overflow average
18个回答
17
投票

此答案用于建议分别存储商和余数(模数)。该解决方案空间效率较低,代码复杂度更高。

为了准确计算平均值,您必须跟踪总数。除非您愿意牺牲准确性,否则无法解决此问题。您可以尝试以总计的方式存储总数,但是如果算法正确,最终您必须对其进行跟踪。

对于单遍算法,这很容易证明。假设在处理完这些项目后算法的整个状态下,您无法重构所有前面的项目。但是,等等,我们可以模拟算法,然后接收一系列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?

0
投票

如果您愿意牺牲精度,则可以执行以下操作:


0
投票

也许您可以通过计算调整值的平均值,然后将其乘以集合中元素的数量来减少每一项。但是,您会发现对浮点数的操作数量略有不同。


0
投票

您可以保持滚动平均值,每增加一个大数就更新一次。


0
投票

使用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; 库。


0
投票

NextAverage = CurrentAverage +(NewValue-CurrentAverage)/(CurrentObservations + 1)


0
投票

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


0
投票

让Avg(n)为前n个数的平均值,而data [n]为第n个数。


0
投票

尽管可以建议在实际实现中使用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实例,然后再对其进行累加来实现(尽管我不建议这样做)。每次增加之后,您可以将其与总和进行比较,直到找到平均值的整数部分为止。从那里可以剥离剩余部分并计算小数部分。可能有一些巧妙的技巧可以提高效率,但是这种基本策略肯定会起作用,而无需诉诸更大的数据类型。


0
投票

对于两个正数(或两个负数),我从Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n 找到了一个非常优雅的解决方案。


12
投票

如果您只是在寻找算术平均值,则可以像这样执行计算:

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

编辑:

为了回应评论,由于执行了许多除法和加法运算,因此肯定会失去精度。对于问题所指示的值,这应该不成问题,但应予以考虑。


6
投票

您可以尝试以下方法:

元素的个数为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

步骤之后,您将在mean变量中获得正确的答案,而remainder / N将是答案的一部分(我不确定您是否需要它,但是无论如何)

2
投票
如果您大概知道平均值是多少(或者至少所有数字对都将具有最大差异

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; 的扩展方法。


2
投票

如果遇到此问题,我将怎么办。首先让我们定义一个非常简单的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)。根据您想要的精度,可以将其仅应用于最后的有理数。


2
投票

使用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()之前调用它。)


1
投票

如果您知道事先所有数字都将为“大”(即“ .Select(..).Sum()比零更接近”),则可以计算出它们与[C0的距离],则数字的平均值要少long.MaxValue

但是,如果(m)个数字中的任何一个离long.MaxValue far],则此方法将失败,因此,这是课程必不可少的东西...


1
投票

我想在某个地方或其他地方必须做出妥协。如果数字真的变大了,那么较低位数的几位数字(例如较低的5位数字)可能不会对结果产生太大影响。


0
投票

关于Visual J#中的long.MaxValue

© www.soinside.com 2019 - 2024. All rights reserved.