无溢出异常的平均函数

Question

.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），但我在那里遇到了异常。这是因为（在我的机器上）Average扩展方法的实现，由.NET Reflector检查如下：

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版本）。

但我仍然想知道是否有一种相当简单的整数平均值计算实现，而不需要外部库。你知道这样的实现吗？

谢谢！

---

更新：

之前的示例仅是为了说明溢出问题。该问题是关于计算任何一组数字的平均数，这些数字可能相加得到一个超过类型最大值的大数字。对此混淆感到抱歉。我还更改了问题的标题以避免进一步的混淆。

感谢大家！

- Ron Klein

---

你无论如何都要将你的总和转换为double，为什么不在总和累加器中使用double类型呢？ 由于将long截断为尾数宽度可能会导致一些小错误。 - ony

@ony：感觉他没有访问Average函数代码的权限 - 否则他为什么要使用反编译工具呢？ - ANeves

@ANeves：那只是一种实现的变体，作为对“我仍然想知道是否有”的回应。 - ony

@PauliL - 哎呀，我把它修复成原始值了。 - Ron Klein

Answer 1

以前的答案建议将商和余数(模数)分别存储。这种解决方案的空间利用率较低且代码复杂度更高。

为了精确计算平均值，您必须跟踪总数。除非您愿意牺牲准确性，否则没有绕过这一点的方法。您可以尝试以花哨的方式存储总数，但如果算法正确，最终您必须跟踪它。

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

- Craig Gidney

---

在处理 Int64 范围内的任何值时，为了更准确，代码应该简洁。 - DanK

小测试：现在在不知道先验计数的情况下实现这个;) - Brady Moritz

我其实考虑了一下，更加时间和空间高效的方法是将总数存储在Int64或BigInteger中，在最后进行一次除法运算。这也使得未知计数情况变得微不足道。 - Craig Gidney

Answer 2

如果您只是想要算术平均值，可以按以下方式进行计算：

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

编辑：

回应评论中的问题，这种方法确实会导致精度损失，因为要进行多次除法和加法运算。对于问题中给出的值，这应该不是问题，但需要考虑。

- Paul Turner

---

非常好的答案 - 最小化精度损失，最小化溢出风险，并得到正确的答案！我给你点赞... 但是：IEnumerable没有.Count()方法，所以您可能需要更正参数类型（或明确说明您正在使用Linq）。哦，还有很棒的头像 ;) - Dan Puzey

@Dan，IEnumerable确实有.Count()方法，只要你在代码中包含了System.Linq的using语句。 - Tomas Aschan

如果 count 非常大，而元素很小，则精度损失可能不可忽略。您拥有的元素越多且它们越小，性能就越差... - Aviad P.

@Tomas - 说得好 - 我在 OP 中错过了 using。 不过他已经得到我的 +1 了；-) - Dan Puzey

@TomasAschan 尽管 Count() 可以通过 LINQ 访问，但在这里选择它仍然是一个糟糕的选择，因为它可能会导致对 ienumerable 的多次枚举。更适当的做法是将值作为 ICollection<T> 传入，该集合可以跟踪其计数。 - julealgon

Answer 3

您可以尝试以下方法：

假设有N个元素和数字数组arr[0], .., arr[N-1]。

你需要定义2个变量：mean 和 remainder。

初始时，mean = 0，remainder = 0。

在第i步中，您需要按以下方式更改mean和remainder：

mean += arr[i] / N;
remainder += arr[i] % N;
mean += remainder / N;
remainder %= N;

经过N步骤后，您将在mean变量中获得正确的答案，remainder / N将是答案的小数部分（我不确定您是否需要它，但无论如何请注意保留HTML标记）。

- Miollnyr

Answer 4

如果您大概知道平均值是多少（或者至少知道所有数字对之间的最大差异 < 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> 的扩展方法。

- Tomas Aschan

---

如果你不幸拥有一个列表 {long.MaxValue, long.MinValue+100, ... }，它仍然会出错。但是你的想法似乎很好。 - ANeves

@ANeves - 为了使这个工作正常，我明确假设没有两个数字的差距应该超过long.MaxValue。 - Tomas Aschan

Answer 5

如果给我这个问题，我会这样做。首先，让我们定义一个非常简单的RationalNumber类，它包含两个属性-被除数和除数以及一个用于添加两个复数的运算符。它看起来像这样：

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

最后，我们有一个有理数列表和一个整数，将它们相加并得到序列的平均值，而不会溢出。同样的方法可以用于任何类型，没有精度损失，也没有溢出。

编辑：

为什么这个方法可行：

定义：一组数字。

如果Average(A) = SUM(A) / LEN(A)，那么

Average(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 + ... + Reminder1 + Reminder2 + ...;

通过保持它们处于有理数形式来求和整数部分和余数部分。最后我们得到一个整数和一个有理数，将它们相加即可得到Average(A)。根据你想要的精度，只需在最后应用于有理数即可。

- Ivan Zlatanov

---

您使用了误导性的名称（ComplexNumber？哪里是实部和虚部？！- 您可能想使用 RationalNumber - GCD 函数的 left 和 right ？！）。您在加法过程中使用模数、除法和 GCD 算法，所以我不明白这比 @Programming Hero 的解决方案更快的原因。您也没有确切地说明它是如何工作的及其原理。-1。 - IVlad

我接受您的批评并将更新我的回答。我重新检查了我的代码以测试速度。是我的错误。我会更正我的评论。 - Ivan Zlatanov

Answer 6

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

- Matthew Whited

Answer 7

我猜一定要在某个地方做出妥协。如果数字真的变得如此大，则较低位数（比如较低的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;
}

- Tapomay

---

PS：基于原则：如果a + b = c，则a/n + b/n = c/n。 - Tapomay

抱歉，维基百科上有更好的资料。请查看http://en.wikipedia.org/wiki/Moving_average。请在“累积移动平均”一节的末尾检查公式。 - Tapomay

Answer 8

如果您事先知道所有数字都将是“大数”（即“远离零而更接近long.MaxValue”），则可以计算它们与long.MaxValue的距离的平均值，然后这些数字的平均值就是long.MaxValue减去该平均值。

然而，如果有任何数字远离long.MaxValue，那么这种方法将失败，因此需要根据实际情况进行选择...

- AakashM

---

这与我的方法大致相同，但是你的方法对于任何负数都会失败。 - Tomas Aschan

Answer 9

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

一旦您拥有这个总和，您就需要计算sum/total以获得平均值，这可以通过创建并逐个增加另一个Int32WithBoundedRollover实例来完成（虽然我不建议这样做）。每次增加后，您可以将其与总和进行比较，直到找到平均数的整数部分。从那里，您可以取出余数并计算小数部分。可能有一些聪明的技巧可以使这更有效率，但这种基本策略肯定可以正常工作，无需求助于更大的数据类型。

话虽如此，当前的实现并不适用于此（例如Int32WithBoundedRollover上没有比较运算符，尽管添加起来不会太难）。原因是在最后使用BigInteger进行计算只是更简单。对于大量平均数而言，性能方面这并不太重要，因为它只需要完成一次，而且过于清晰易懂了，不必担心想出什么聪明的东西（至少目前是这样...）。

至于你最初的问题，即与长数据类型有关的问题，只需将Int32WithBoundedRollover转换为LongWithBoundedRollover，通过交换int32引用以获得long引用，就应该可以正常工作。对于Int32s，我注意到性能上有很大的差异（如果感兴趣的话）。与仅使用BigInteger方法相比，我编写的方法在我测试的大型样本（即总数据点数）中快了约80％（此代码包含在Int32WithBoundedRollover类的单元测试中）。这主要是由于硬件执行int32操作与BigInteger操作之间的差异造成的。

- Chiune Sugihara

---

不错的项目，我会在有时间的时候深入研究它。 - Ron Klein

Answer 10

如果你愿意牺牲精度，你可以做类似这样的事情：

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;

- Andreas Brinck