代码之家  ›  专栏  ›  技术社区  ›  Lasse V. Karlsen

如何将平均数的计算一般化为子集?

  •  5
  • Lasse V. Karlsen  · 技术社区  · 15 年前

    编辑: 由于似乎没有人阅读这个链接到的原始问题,让我在这里介绍一下它的概要。

    正如其他人所问,最初的问题是,给定大量的值,其和将超过数据类型 Double 如果可以,如何计算这些值的平均值。

    有几个答案据说是以集合计算的,比如取50和50个数字,然后计算这些集合内的平均值,最后取所有这些集合的平均值,并将它们组合得到最终的平均值。

    我的立场是,除非你能保证所有这些价值观都能被分割成 大小相等的集 ,您不能使用此方法。有人为了提供答案而在这里问我这个问题,所以在这里。

    基本上,给定任意数量的值,其中:

    • 我事先知道数值的数目(但是,如果你不知道,你的答案会怎样改变呢?`
    • 我不能收集所有的数字,也不能对它们求和(对于您的编程语言中的普通数据类型,求和太大了)

    如何计算平均值?

    这里剩下的问题概述了如何以及如何将方法拆分为大小相等的集合,但我真的很想知道如何才能做到这一点。

    请注意,我非常了解数学,知道在数学理论术语中,计算 A[1..N]/N 我会给出平均值,假设有一些原因,它不那么简单,我需要拆分工作负载,并且值的数量不一定能被3、7、50、1000或其他东西整除。

    换句话说,我想要的解决方案必须是通用的。


    从这个问题:

    我的立场是,将工作负载拆分为多个集合是不好的,除非您可以确保这些集合的大小相等。


    编辑 :最初的问题是特定数据类型所能容纳的上限,由于他正在求和大量的数字(作为示例给出的计数是10^9),因此数据类型不能容纳该和。因为这是原始解决方案中的一个问题,所以我假设(这是我的问题的先决条件,很抱歉错过了这一点)数字太大,无法给出任何有意义的答案。

    所以,直接除以总数值就可以了。通常求和/计数解决方案出现的最初原因是求和会溢出,但让我们假设,对于这个问题,集/集大小会下溢,或者其他什么。

    重要的是,我不能简单地求和,我不能简单地除以总值。如果我不能做到这一点,我的方法是否有效,我能做些什么来解决它?


    让我概述一下这个问题。

    假设您要计算数字1到6的平均值,但您不能(无论出于何种原因)通过求和、计算数字,然后除以计数来计算。换句话说,你不能简单地做(1+2+3+4+5+6)/6。

    换言之, SUM(1..6)/COUNT(1..6) 出去了。这里我们不考虑空值(在数据库空值中)。

    对这个问题的几个答案暗示着能够将被平均的数字分成几组,比如说3个或50个或1000个数字,然后为此计算一些数字,最后结合这些值得到最终的平均值。

    我的立场是,在一般情况下,这是不可能的,因为这将使一些数字,那些出现在最后一组中的数字,比以前所有的数字或多或少有价值,除非你能把所有的数字分成大小相等的集合。

    例如,要计算1-6的平均值,可以将其拆分为3组数字,如下所示:

    / 1   2   3 \   / 4   5   6 \
    | - + - + - | + | - + - + - |
    \ 3   3   3 /   \ 3   3   3 /  <-- 3 because 3 numbers in the set
     ----------      -----------
          2               2        <-- 2 because 2 equally sized groups
    

    这给了你这个:

          2               5
          -       +       - = 3.5
          2               2
    

    (注:(1+2+3+4+5+6)/6=3.5,此处正确)

    但是,我的观点是,一旦值的数量不能拆分成大小相等的集合,这个方法就会崩溃。例如,序列1-7怎么样,它包含质数的值。

    一个类似的方法,不能加起来 全部的 值和计数 全部的 价值观,一劳永逸,有效吗?

    那么,有这样的方法吗?我如何计算以下条件成立的任意数值的平均值:

    1. 无论出于什么原因,我都不能用普通的求和/计数方法。
    2. 我事先知道值的数目(如果我不知道,会改变答案吗?)
    8 回复  |  直到 14 年前
        1
  •  7
  •   Daniel C. Sobral    15 年前

    好吧,假设你加了三个数字,再除以三,再加上两个数字,再除以二。你能从中得出平均值吗?

    x = (a + b + c) / 3
    y = (d + e) / 2
    z = (f + g) / 2
    

    你想要什么?

    r = (a + b + c + d + e + f + g) / 7
    

    等于

    r = (3 * (a + b + c) / 3 + 2 * (d + e) / 2 + 2 * (f + g) / 2) / 7
    r = (3 * x + 2 * y + 2 * z) / 7
    

    当然,上面的两行都是溢出的,但是由于除法是分布式的,所以我们可以这样做。

    r = (3.0 / 7.0) * x + (2.0 / 7.0) * y + (2.0 / 7.0) * z
    

    这保证了你不会溢出,因为我把x,y和z乘以小于1的分数。

    这是这里的基本点。我不是预先把所有的数除以总数,也不是永远超过溢出量。

    所以…如果你一直在向一个累加器中添加,跟踪你添加了多少个数字,并且总是测试下一个数字是否会导致溢出,然后你可以得到部分平均值,然后计算最终的平均值。

    不,如果你事先不知道这些值,它不会改变任何东西(前提是你可以在求和的时候计算它们)。

    这是一个scala函数。它不是惯用的scala,因此更容易理解:

    def avg(input: List[Double]): Double = {
      var partialAverages: List[(Double, Int)] = Nil
      var inputLength = 0
      var currentSum = 0.0
      var currentCount = 0
      var numbers = input
    
      while (numbers.nonEmpty) {
        val number = numbers.head
        val rest = numbers.tail
        if (number > 0 && currentSum > 0 && Double.MaxValue - currentSum < number) {
          partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
          currentSum = 0
          currentCount = 0
        } else if (number < 0 && currentSum < 0 && Double.MinValue - currentSum > number) {
          partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
          currentSum = 0
          currentCount = 0
        }
        currentSum += number
        currentCount += 1
        inputLength += 1
        numbers = rest
      }
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
    
      var result = 0.0
      while (partialAverages.nonEmpty) {
        val ((partialSum, partialCount) :: rest) = partialAverages
        result += partialSum * (partialCount.toDouble / inputLength)
        partialAverages = rest
      }
    
      result
    }
    

    编辑: 不乘以2和3,我会回到“不支持数据类型”的范围吗?

    不,如果你在最后7点跳水,那当然。但在这里,你们要在和的每一步上进行划分。即使在你的真实情况下,重量( 2/7 3/7 )在可管理的数字范围内(例如 1/10 ~ 1/10000 )这与你的体重(即 1 )

    附言:我想知道为什么我要写这个答案,而不是写我的,在那里我可以获得我的代表:-)

        2
  •  4
  •   Peter    15 年前

    如果你事先知道数值的数目(比如 N 你只要加 1/N + 2/N + 3/N 等等,假设你有价值观 1, 2, 3 . 您可以将其拆分为任意多个计算,并将结果相加。这可能会导致轻微的精度损失,但这不应该是一个问题,除非您还需要一个超精确的结果。

    如果你不知道提前的物品数量,你可能需要更有创造性。但你也可以,循序渐进地去做。说清单是 1, 2, 3, 4 . 从开始 mean = 1 . 然后 mean = mean*(1/2) + 2*(1/2) . 然后 mean = mean*(2/3) + 3*(1/3) . 然后 mean = mean*(3/4) + 4*(1/4) 等等。很容易归纳,你只需要确保括号内的数量是预先计算的,以防止溢出。

    当然,如果你想要极端的准确度(比如说,超过0.001%的准确度),你可能需要比这更小心一点,否则你就可以了。

        3
  •  3
  •   jason    15 年前

    X 做你的样品。把它分成两组 A B 以你喜欢的任何方式。定义 delta = m_B - m_A 在哪里? m_S 表示集合的平均值 S . 然后

    m_X = m_A + delta * |B| / |X|
    

    在哪里? |S| 表示集合的基数 S .现在您可以重复地将其应用于分区并计算平均值。

    为什么是这样?让 s = 1 / |A| t = 1 / |B| u = 1 / |X| (为了方便记法)并让 aSigma bSigma 表示中元素的和 分别使:

      m_A + delta * |B| / |X|
    = s * aSigma + u * |B| * (t * bSigma - s * aSigma)
    = s * aSigma + u * (bSigma - |B| * s * aSigma)
    = s * aSigma + u * bSigma - u * |B| * s * aSigma
    = s * aSigma * (1 - u * |B|) + u * bSigma
    = s * aSigma * (u * |X| - u * |B|) + u * bSigma
    = s * u * aSigma * (|X| - |B|) + u * bSigma
    = s * u * aSigma * |A| + u * bSigma
    = u * aSigma + u * bSigma
    = u * (aSigma + bSigma)
    = u * (xSigma)
    = xSigma / |X|
    = m_X
    

    证据是完整的。

    从这里可以很明显地看出,如何使用它来递归地计算一个平均值(比如重复地将一个集合分成两部分),或者如何使用它来并行计算一个集合的平均值。

    众所周知的在线平均值计算算法就是这种情况的一个特例。这是一个算法,如果 m 的意思是 {x_1, x_2, ... , x_n} 那么平均值 {x_1, x_2, ..., x_n, x_(n+1)} m + ((x_(n+1) - m)) / (n + 1) . 所以用 X = {x_1, x_2, ..., x_(n+1)} , A = {x_(n+1)} B = {x_1, x_2, ..., x_n} 我们恢复了在线算法。

        4
  •  1
  •   Peter    15 年前

    跳出框框思考: 用中间值代替。计算起来要容易得多——外面有很多算法(例如,使用队列),你可以经常构造好的参数来解释为什么它对数据集更有意义(不受极端值的影响等),并且你在数值精度上不会有任何问题。它将是快速和高效的。另外,对于大型数据集(听起来像您的数据集),除非分布真的很奇怪,否则平均值和中位数的值将相似。

        5
  •  0
  •   Troubadour    15 年前

    当你把数字分成几组时,你只是除以总数,还是我遗漏了什么?

    你写的是

    / 1   2   3 \   / 4   5   6 \
    | - + - + - | + | - + - + - |
    \ 3   3   3 /   \ 3   3   3 /
     ----------      -----------
          2               2
    

    但那只是

    / 1   2   3 \   / 4   5   6 \
    | - + - + - | + | - + - + - |
    \ 6   6   6 /   \ 6   6   6 /
    

    所以对于从1到7的数字,一个可能的分组是

    / 1   2   3 \   / 4   5   6 \   / 7 \
    | - + - + - | + | - + - + - | + | - |
    \ 7   7   7 /   \ 7   7   7 /   \ 7 /
    
        6
  •  0
  •   Steve Jessop    15 年前

    Average of x_1 .. x_N
        = (Sum(i=1,N,x_i)) / N
        = (Sum(i=1,M,x_i) + Sum(i=M+1,N,x_i)) / N
        = (Sum(i=1,M,x_i)) / N + (Sum(i=M+1,N,x_i)) / N
    

    这可以重复应用,并且无论求和大小是否相等,都是正确的。所以:

    • 继续添加条款,直到:
      • 添加另一个将溢出(否则会丢失精度)
      • 除以n不会下溢
    • 将和除以n
    • 把结果加到目前的平均值上

    有一个明显的尴尬的情况,那就是在序列的末尾有一些非常小的项,这样在满足“除以n不会下溢”的条件之前,值就会用完。在这种情况下,只需丢弃这些值——如果它们对平均值的贡献不能用您的浮点类型表示,那么它尤其小于平均值的精度。所以不管你是否包含这些术语,对结果都没有任何影响。

    还有一些不太明显的尴尬情况与个别求和的精度损失有关。例如,值的平均值是多少:

    10^100, 1, -10^100
    

    数学上说是1,但浮点算术上说这取决于你把这些项加起来的顺序,在6种可能性中有4种是0,因为(10^100)+1=10^100。但是我认为浮点运算的非交换性是一个与这个问题不同的更普遍的问题。如果对输入进行排序是不可能的,那么我认为有一些事情是可以做到的,即您可以维护许多不同大小的累加器,并将每个新值添加到其中任何一个累加器中,以获得最佳的精度。但我真的不知道。

        7
  •  0
  •   Community CDub    8 年前

    这是另一种方法。你正在从某个来源一个接一个地接收数字,但是你可以在每个步骤中跟踪平均值。

    首先,我将写出步骤中的平均值公式。 n+1 :

    mean[n+1] = mean[n] - (mean[n] - x[n+1]) / (n+1)
    

    初始条件:

    mean[0] = x[0]
    

    (索引从零开始)。

    第一个方程可以简化为:

    mean[n+1] = n * mean[n] / (n+1) + x[n+1]/(n+1)
    

    我们的想法是,跟踪平均值,当您“接收”序列中的下一个值时,您计算出它与当前平均值的偏移量,并将其平均分配给 N+ 1 到目前为止看到的样本,并相应地调整您的平均值。如果你的数字没有太多的差异,你的平均值将需要调整非常轻微的新数字作为 n 变大。

    显然,即使您在开始时不知道值的总数,这个方法也可以工作。它还有一个额外的优点,就是您随时都知道当前平均值的值。我能想到的一个缺点是,它可能会给开头看到的数字赋予更多的“权重”(不是严格的数学意义上的,而是因为浮点表示)。

    最后,如果计算不够仔细,所有这些计算都会遇到浮点“错误”。见 my answer to another question 对于浮点数计算的一些问题以及如何测试潜在问题。

    作为测试,我生成 N=100000 正态分布随机数,均值为零,方差为1。然后我用三种方法计算了它们的平均值。

    1. 求和(数字)/n,称之为m ,
    2. 我上面的方法叫m ,请
    3. 对数字排序,然后使用上面的方法,称之为m .

    我发现的是:M 埃米 α×4.6×10 17 ,米 埃米 α×3×10 15 ,米 埃米 α×3×10 -15个 . 因此,如果对数字进行排序,那么错误可能不够小。(但请注意,即使是最严重的错误也是10 15 每100000个数字分成1个部分,所以不管怎样都足够好。)

        8
  •  0
  •   P Daddy    14 年前

    这里的一些数学解非常好。这是一个简单的技术解决方案。

    使用较大的数据类型。这可以分为两种可能性:

    1. 使用高精度浮点库。一个需要平均10亿个数字的人可能拥有购买128位(或更长)浮点库所需的资源,或者大脑编写能力。

      我理解这里的缺点。它肯定比使用内部类型慢。如果值的数量增长得太多,则仍可能出现溢出/下溢。亚达亚达。

    2. 如果您的值是整数或者可以很容易地缩放为整数,请将您的和保存在整数列表中。溢出时,只需添加另一个整数。这基本上是第一个选项的简化实现。简单的 (未经测试) C中的示例如下

    class BigMeanSet{
        List<uint> list = new List<uint>();
    
        public double GetAverage(IEnumerable<uint> values){
            list.Clear();
            list.Add(0);
    
            uint count = 0;
    
            foreach(uint value in values){
                Add(0, value);
                count++;
            }
    
            return DivideBy(count);
        }
    
        void Add(int listIndex, uint value){
            if((list[listIndex] += value) < value){ // then overflow has ocurred
                if(list.Count == listIndex + 1)
                    list.Add(0);
                Add(listIndex + 1, 1);
            }
        }
    
        double DivideBy(uint count){
            const double shift = 4.0 * 1024 * 1024 * 1024;
    
            double rtn       = 0;
            long   remainder = 0;
    
            for(int i = list.Count - 1; i >= 0; i--){
                rtn *= shift;
                remainder <<= 32;
                rtn += Math.DivRem(remainder + list[i], count, out remainder);
            }
    
            rtn += remainder / (double)count;
    
            return rtn;
        }
    }
    

    就像我说的,这是未经测试的我没有10亿的价值,我真的想平均所以我可能犯了一两个错误,特别是在 DivideBy 函数,但它应该演示一般的思想。

    这应该提供尽可能多的双精度,并且应该适用于任何数量的32位元素,最多2个 三十二 -1.如果需要更多的元素,则 count 变量将需要扩展,并且 迪比 函数的复杂性会增加,但我将把它留给读者作为练习。

    在效率方面,它应该和这里的任何其他技术一样快或更快,因为它只需要遍历列表一次,只执行一个除法运算(好的,一组除法运算),并且它的大部分工作都是用整数完成的。不过,我没有对它进行优化,而且我很确定,如果必要的话,它可以稍微快一点。放弃递归函数调用和列表索引将是一个很好的开始。再一次,给读者一个练习。该代码旨在易于理解。

    如果有人比我现在更有动机,想要验证代码的正确性,并修复可能存在的任何问题,请做我的客人。


    我现在已经测试了这段代码,并做了一些小的更正(在 List<uint> 构造函数调用,并且在 迪比 函数)。

    我首先测试了1000组随机长度(范围在1到1000之间),填充了随机整数(范围在0到2之间)。 三十二 - 1)。这些集合我可以通过在它们上运行一个标准的平均值来轻松快速地验证其准确性。

    然后我用100 * 大系列,随机长度10 5个 和10 . 这些序列的下界和上界也是随机选择的,受到约束,这样序列就可以在32位整数的范围内。对于任何系列,结果都很容易验证,因为 (lowerbound + upperbound) / 2 .

    * 好吧,那是个善意的谎言。在大约20或30次成功运行后,我中止了大型系列测试。一系列长度10 在我的机器上运行只需要不到一分半钟的时间,所以测试这个程序大约半小时就足以满足我的口味了。

    对于感兴趣的人,我的测试代码如下:

    static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
        for(uint i = lowerbound; i <= upperbound; i++)
            yield return i;
    }
    
    static void Test(){
        Console.BufferHeight = 1200;
        Random rnd = new Random();
    
        for(int i = 0; i < 1000; i++){
            uint[] numbers = new uint[rnd.Next(1, 1000)];
            for(int j = 0; j < numbers.Length; j++)
                numbers[j] = (uint)rnd.Next();
    
            double sum = 0;
            foreach(uint n in numbers)
                sum += n;
    
            double avg = sum / numbers.Length;
            double ans = new BigMeanSet().GetAverage(numbers);
    
            Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);
    
            if(avg != ans)
                Debugger.Break();
        }
    
        for(int i = 0; i < 100; i++){
            uint length     = (uint)rnd.Next(100000, 1000000001);
            uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
            uint upperbound = lowerbound + length;
    
            double avg = ((double)lowerbound + upperbound) / 2;
            double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));
    
            Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);
    
            if(avg != ans)
                Debugger.Break();
        }
    }