language-agnostic - 如何以一般方式将平均值的计算减少到子集？

Question

编辑:由于似乎没有人正在阅读此链接的原始问题，因此让我在此引入它的提要。

正如其他人所问的那样，最初的问题是，在给定大量值的情况下，总和将超过Double的数据类型所能容纳的值，那么如何计算这些值的平均值。

据说有几个答案是按集合计算的，例如取50和50个数字，并计算这些集合内部的平均值，然后最终取所有这些集合的平均值并将其组合以获得最终平均值。

我的立场是，除非您可以保证可以将所有这些值分割成许多大小相等的集合，否则不能使用此方法。有人胆敢在这里问这个问题，以便提供答案，所以就在这里。

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

我事先知道值的数量(但是，如果您不这样做，您的答案将如何变化？)

我无法收集所有数字，也无法求和(对于您编程语言中的常规数据类型，该和将太大)

如何计算平均值？

这里的其余问题概述了将方法拆分为大小相等的集合的方式以及方法的问题，但是我真的很想知道您如何做到这一点。

请注意，我非常了解数学，以数学理论的术语来说，计算A[1..N]/N的总和将得出平均值，让我们假设有很多理由认为它不仅如此简单，而且我需要分担工作量，并且值的数量不一定要除以3、7、50、1000或其他任何值。

换句话说，我追求的解决方案必须是通用的。

从这个问题:

What is a good solution for calculating an average where the sum of all values exceeds a double’s limits?

我的立场是将工作负载分成几组是不好的，除非您可以确保这些组的大小相等。

编辑:最初的问题是关于特定数据类型可以容纳的上限，并且由于他求和了很多数字(例如，示例中的计数为10 ^ 9)，因此数据类型无法容纳和。由于这是原始解决方案中的问题，因此我假设(这是我提出问题的先决条件，很遗憾错过了)这些数字太大，无法给出任何有意义的答案。

因此，直接除以值的总数是不可能的。普通SUM/COUNT解决方案出局的最初原因是SUM会溢出，但让我们假设，对于这个问题，SET-SET/SET-SIZE将会下溢，或者发生任何其他情况。

重要的部分是我不能简单地求和，也不能简单地除以总数的数量。如果我不能做到这一点，我的方法是否行得通，该如何解决？

让我概述一下问题。

假设您要计算数字1到6的平均值，但是您不能(由于任何原因)通过对数字求和，对数字进行计数，然后将总和除以计数来进行计算。换句话说，您不能简单地做(1 + 2 + 3 + 4 + 5 + 6)/6。

换句话说， SUM(1..6)/COUNT(1..6)已输出。我们在这里不考虑NULL(如数据库NULL)。

该问题的几个答案都暗示着能够将被平均的数字分成若干个集合，例如3或50或1000个数字，然后为其计算一些数字，然后最终将这些值组合起来以获得最终的平均值。

我的立场是，在一般情况下这是不可能的，因为这将使某些数字(出现在最终集合中的数字)比先前集合中的所有数字或多或少有值(value)，除非您可以将所有数字均分大小集。

例如，要计算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，该序列包含一个素数值。

不能将所有值求和并一次性计算所有值的类似方法可以工作吗？

那么，有这种方法吗？如何计算任意数值的平均值，其中以下条件成立:

无论出于何种原因，我都无法执行常规的求和/计数方法

我事先知道值的数量(如果我不知道，那会改变答案吗？)

Answer 1

好吧，假设您将三个数字相加并除以三，然后再将两个数字相加并除以二。你能从这些中得到平均值吗？

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乘以小于一的分数。

这是这里的基本要点。我既不事先将所有数字除以总数，也从未超过溢出数。

因此...如果您继续添加累加器，请跟踪已添加的数字，并始终测试下一个数字是否会导致溢出，那么您可以得到部分平均值，并计算最终平均值。

不，如果您事先不知道这些值，它不会改变任何内容(前提是您可以在对它们求和时对其进行计数)。

这是执行此操作的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)相比并没有太大区别。

PS:我想知道为什么我要解决这个问题，而不是写我的文章来获得我的代表:-)