如何在一组大数字中找到平均值？

Question

我有一大堆数字,可能在几千兆字节范围内.第一个问题是我无法将所有这些存储在内存中.其次是任何添加这些的尝试都会导致溢出.我在考虑使用更多的滚动平均值,但它需要准确.有任何想法吗？

这些都是浮点数.

这不是从数据库中读取的,而是从多个源收集的CSV文件.它必须准确,因为它存储为秒的一部分(例如; 0.293482888929),滚动平均值可以是.2和.3之间的差值.

它是一组#,表示用户响应某些表单操作的时间.例如,在显示消息框时,按"确定"或"取消"需要多长时间.数据发送给我存储为秒.部分秒; 例如1.2347秒.将它转换为毫秒,我溢出int,long等等.相当快.即使我不转换它,我仍然会很快溢出它.我想下面的一个答案是正确的,也许我不必100%准确,只是在一个特定的StdDev内部的某个范围内看,我会足够接近.

Answer 1

您可以从您的集合(" 人口 ")中随机抽样以获得平均值(" 平均值 ").准确度将取决于样品的变化程度(由" 标准偏差 "或方差确定).

优点是你有数十亿的观察结果,你只需要对它们中的一小部分进行采样,以获得一个不错的准确度或你选择的" 置信区间 ".如果条件合适,这会减少您将要做的工作量.

这是一个C#的数值库,包括一个随机序列生成器.只需创建一个随机的数字序列,引用元素数组中的索引(从1到x,数组中的元素数).取消引用以获取值,然后计算您的平均值和标准差.

如果您想测试数据的分布,请考虑使用Chi-Squared Fit测试或KS测试,您可以在许多电子表格和统计软件包(例如R)中找到它.这将有助于确认这种方法是否可用.

Answer 2

整数还是花车？

如果它们是整数,则需要通过读取数字并记录您看到的每个值的数量来累积频率分布.这很容易平均化.

对于浮点,这有点问题.鉴于浮动的总体范围和实际分布,您必须计算出一个bin大小,以保留您想要的精度而不保留所有数字.

编辑

首先,您需要对数据进行采样以获得均值和标准差.几千点应该足够好了.

然后,您需要确定一个可观的范围.人们在平均值周围选择±6σ(标准偏差)之类的东西.您可以将此范围划分为尽可能多的铲斗.

实际上,桶的数量决定了平均值中的有效位数.因此,选择10,000或100,000个桶来获得4或5位精度.由于它是一种测量,因此您的测量只有两位或三位数的几率很高.

编辑

你会发现你的初始样本的平均值非常接近任何其他样本的平均值.任何样本均值接近人口均值.你会注意到你的大多数(但不是全部)手段彼此之间有1个标准差.

您应该发现测量误差和误差大于标准偏差.

这意味着样本均值与总体均值一样有用.

Answer 3

滚动平均值不会像其他任何东西一样准确(折扣舍入错误,我的意思是)？由于所有分裂,它可能有点慢.

您可以对批量数字进行分组并递归地对它们求平均值.像平均100个数字100次,然后平均结果.这将是更少的颠簸和大多数添加.

事实上,如果你一次添加256或512,你可以将结果按8位或9位进行位移,(我相信你可以通过简单地改变浮点尾数来做到这一点) - 这会使你的程序非常快,它可以只用几行代码递归写入(不计算尾数移位的不安全操作).

也许除以256就已经使用了这种优化？我可能要加速测试除以255对256,看看是否有一些大的改进.我猜不是.

Answer 4

您的意思是32位和64位数字.但为什么不只使用一个合适的Rational Big Num库？如果您有这么多数据并且想要一个精确的平均值,那么只需编码即可.

class RationalBignum {
    public Bignum Numerator { get; set; }
    public Bignum Denominator { get; set; }
}

class BigMeanr {
    public static int Main(string[] argv) {
        var sum = new RationalBignum(0);
        var n = new Bignum(0);
        using (var s = new FileStream(argv[0])) {
            using (var r = new BinaryReader(s)) {
                try {
                    while (true) {
                        var flt = r.ReadSingle();
                        rat = new RationalBignum(flt);
                        sum += rat;
                        n++;
                    }
                }
                catch (EndOfStreamException) {
                    break;
                }
            }
        }
        Console.WriteLine("The mean is: {0}", sum / n);
    }
}

请记住,除了编译器为您提供的数字类型之外,还有更多的数字类型.

Answer 5

您可以将数据分成多组,例如1000个数字,平均值,然后平均值.

Answer 6

诀窍是你担心溢出。在这种情况下，一切都归结为执行顺序。基本公式是这样的：

鉴于：

A = current avg
C = count of items
V = next value in the sequence

下一个平均值 (A ₁ ) 是：

      (C * A) + V
A 1 = ———————————
        C+1

危险是在评估序列的过程中，而A应该保持相对可控的 C 会变得非常大。
最终 C * A 将溢出 integer 或 double 类型。

我们可以尝试的一件事是像这样重写它，以减少溢出的机会：

A 1 = C/(C+1) * A/(C+1) + V/(C+1)

这样，我们从不乘 C * A，只处理较小的数字。但现在关注的是除法运算的结果。如果 C 非常大，C/C+1（例如）限制为普通浮点表示时可能没有意义。我能建议的最好方法是在此处使用 C 可能的最大类型。

Answer 7

这是一个经典的分而治之类型的问题。

问题在于，一大组数字的平均值与该组前半部分的平均值相同，再与该组后半部分的平均值相同。

换句话说：

AVG(A[1..N]) == AVG( AVG(A[1..N/2]), AVG(A[N/2..N]) )

这是一个简单的 C# 递归解决方案。它通过了我的测试，应该是完全正确的。

public struct SubAverage
{
    public float Average;
    public int   Count;
};

static SubAverage AverageMegaList(List<float> aList)
{
    if (aList.Count <= 500) // Brute-force average 500 numbers or less.
    {
        SubAverage avg;
        avg.Average = 0;
        avg.Count   = aList.Count;
        foreach(float f in aList)
        {
            avg.Average += f;
        }
        avg.Average /= avg.Count;
        return avg;
    }

    // For more than 500 numbers, break the list into two sub-lists.
    SubAverage subAvg_A = AverageMegaList(aList.GetRange(0, aList.Count/2));
    SubAverage subAvg_B = AverageMegaList(aList.GetRange(aList.Count/2, aList.Count-aList.Count/2));

    SubAverage finalAnswer;
    finalAnswer.Average = subAvg_A.Average * subAvg_A.Count/aList.Count + 
                          subAvg_B.Average * subAvg_B.Count/aList.Count;
    finalAnswer.Count = aList.Count;

    Console.WriteLine("The average of {0} numbers is {1}",
        finalAnswer.Count, finalAnswer.Average);
    return finalAnswer;
}