平均函数没有溢出异常

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),但我在那里得到了例外.这是因为.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相关).

但我仍然想知道在没有外部库的情况下计算整数平均值是否非常直接.你碰巧知道这种实施吗？

谢谢!!

---

更新:

前面的三个大整数的例子只是一个例子来说明溢出问题.问题是关于计算任何数字集合的平均值,这些数字可能总和超过类型的最大值的大数字.抱歉这个混乱.我也改变了问题的标题,以避免额外的混淆.

谢谢大家!!

Answer 1

这个答案用于建议分别存储商和余数(mod计数).该解决方案节省空间并且代码复杂度更高.

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

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

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

编辑:

在回应评论时,由于执行了大量的划分和补充,这种方式肯定会失去精确度.对于问题所指出的值,这应该不是问题,但应该考虑.

Answer 3

您可以尝试以下方法:

let元素的数量是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将是答案的小数部分(我不确定你是否需要它,但无论如何)