c# - 没有溢出异常的平均函数

Question

.NET 框架 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 检查的 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 中，但我与 3.5 相关联）。

但我仍然想知道是否有一个非常直接的实现来计算整数的平均值而无需外部库。你碰巧知道这样的实现吗？

谢谢！！

更新：

前面的三个大整数的例子只是说明溢出问题的一个例子。问题是关于计算任何一组数字的平均值，这些数字总和可能超过类型的最大值。对这种混乱感到抱歉。我还更改了问题的标题以避免额外的混乱。

谢谢大家！！

score 18 · Accepted Answer

该答案用于建议分别存储商和余数（模数）。该解决方案的空间效率较低且代码更复杂。

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

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

score 13 · Accepted Answer

如果您只是在寻找算术平均值，则可以执行如下计算：

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

编辑：

作为对评论的回应，由于执行了许多除法和加法，这种方式肯定会降低精度。对于问题所指示的值，这应该不是问题，但应该是一个考虑因素。

score 7 · Accepted Answer

您可以尝试以下方法：

设元素数为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将是答案的小数部分（我不确定您是否需要它，但无论如何）

score 2 · Accepted Answer

如果您大致知道平均值是多少（或者，至少，所有数字对的最大差值 < 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>.

score 2 · Accepted Answer

如果遇到这个问题，我会这样做。首先让我们定义一个非常简单的 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(Numbers)/Length(Numbers) 估算，与 Number[ 0 ] / Length + Number[ 1 ] / Length + ... + Number[ n ] / Length 相同。为了能够计算这一点，我们将每个 Number[ i ] / Length 表示为一个整数和一个有理部分（提醒）。这是它的外观：

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）=>

平均（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 + ...;

对所有部分求和，并通过保持有理数形式对提醒进行求和。最后我们得到一个整数和一个有理数，它们相加得到平均值（A）。根据您想要的精度，您仅将其应用于最后的有理数。

score 2 · Accepted Answer

使用 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()。）

score 1 · Accepted Answer

如果您事先知道所有数字都会“大”（在“long.MaxValue比零更接近”的意义上），您可以计算它们与的距离long.MaxValue的平均值，那么数字的平均值会long.MaxValue小于。

但是，如果 (m) 任何数字远离，这种方法将失败long.MaxValue，因此它是课程的马...

score 1 · Accepted Answer

我想必须在某个地方或其他地方达成妥协。如果数字真的变得如此之大，那么低位的几位数字（比如低 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;
}

score 1 · Accepted Answer

以安全的方式平均特定数字类型的数字，同时仅使用该数字类型实际上是可能的，尽管我建议在实际实现中使用 BigInteger 的帮助。我为Safe Numeric Calculations创建了一个项目，该项目具有一个小结构 (Int32WithBoundedRollover)，它可以总计 2^32 个 int32s 而没有任何溢出（该结构内部使用两个 int32 字段来执行此操作，因此不使用更大的数据类型）。

一旦你有了这个总和，你就需要计算总和/总计来获得平均值，你可以通过创建 Int32WithBoundedRollover 的另一个实例然后将其增加总和来做到这一点（尽管我不推荐它）。每次增量后，您可以将其与总和进行比较，直到找出平均值的整数部分。从那里你可以剥离余数并计算小数部分。可能有一些巧妙的技巧可以提高效率，但这种基本策略肯定会起作用，而无需求助于更大的数据类型。

That being said, the current implementation isn't build for this (for instance there is no comparison operator on Int32WithBoundedRollover, although it wouldn't be too hard to add). The reason is that it is just much simpler to use BigInteger at the end to do the calculation. Performance wise this doesn't matter too much for large averages since it will only be done once, and it is just too clean and easy to understand to worry about coming up with something clever (at least so far...).

As far as your original question which was concerned with the long data type, the Int32WithBoundedRollover could be converted to a LongWithBoundedRollover by just swapping int32 references for long references and it should work just the same. For Int32s I did notice a pretty big difference in performance (in case that is of interest). Compared to the BigInteger only method the method that I produced is around 80% faster for the large (as in total number of data points) samples that I was testing (the code for this is included in the unit tests for the Int32WithBoundedRollover class). This is likely mostly due to the difference between the int32 operations being done in hardware instead of software as the BigInteger operations are.

score 0 · Accepted Answer

0

Visual J# 中的BigInteger怎么样。

于 2010-05-24T08:03:21.747 回答

score 0 · Accepted Answer

如果您愿意牺牲精度，您可以执行以下操作：

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;

score 0 · Accepted Answer

也许您可以通过计算调整值的平均值来减少每个项目，然后将其乘以集合中的元素数。但是，您会发现浮点运算的数量有所不同。

var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };
var avg = items.Average(i => i / items.Count()) * items.Count();

score 0 · Accepted Answer

0

您可以保留一个滚动平均值，为每个大数字更新一次。

于 2010-05-24T08:13:10.013 回答

score 0 · Accepted Answer

0

使用 CodePlex 上的IntX库。

于 2010-05-24T08:29:00.893 回答

score 0 · Accepted Answer

0

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

于 2013-02-26T00:58:12.390 回答

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

令 Avg(n) 为前 n 个数的平均值，data[n] 为第 n 个数。

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

可以避免值溢出，但是当 n 很大时会损失精度。

score 0 · Accepted Answer

For two positive numbers (or two negative numbers) , I found a very elegant solution from here.

where an average computation of (a+b)/2 can be replaced with a+((b-a)/2.

c# - 没有溢出异常的平均函数

18 回答 18

Related

Reference