algorithm - 查找大量数字的平均值

Question

遇到这个面试问题。

Write an algorithm to find the mean(average) of a large list. This list could contain trillions or quadrillions of number. Each number is manageable in hundreds, thousands or millions.

谷歌搜索它给了我所有的 Medians of Medians 解决方案。我该如何解决这个问题？
分而治之是否足以应对数万亿的数字？
这么大的列表怎么处理？

Answer 1

如果列表的大小是可计算的，那么这实际上只是您有多少可用内存、应该花费多长时间以及算法应该有多简单的问题。
基本上，您可以将所有内容相加并除以大小。
如果您没有足够的内存，则先除法可能会起作用(请注意，那样您可能会失去一些精度)。

另一种方法是递归地将列表分成两半并计算子列表的均值。您的递归终止条件是列表大小为 1，在这种情况下，平均值只是列表的唯一元素。如果遇到奇数大小的列表，请使第一个或第二个子列表更长，这几乎是任意的，甚至不必保持一致。

但是，如果您的列表太大以至于无法计算其大小，则无法将其拆分为 2 个子列表。在这种情况下，递归方法的工作方式几乎相反。不是拆分为包含 n/2 元素的 2 个列表，而是拆分为包含 2 个元素的 n/2 列表(或者更确切地说，立即计算它们的平均值)。所以基本上，你计算元素 1 和 2 的平均值，它成为你的新元素 1。3 和 4 的平均值是你的新第二个元素，依此类推。然后将相同的算法应用于新列表，直到只剩下 1 个元素。如果遇到奇数大小的列表，要么在末尾添加一个元素，要么忽略最后一个。如果你加一个，你应该尽量接近你的预期平均值。
虽然这不会精确地计算出数学上的平均值，但对于那种大小的列表，它已经足够接近了。这几乎是一种mean of means 方法。您也可以采用 median of medians 路线，在这种情况下，您可以递归地选择子列表的中值。同样的原则也适用，但您通常希望获得奇数。
如果您的列表大小均匀，您甚至可以结合这些方法并计算平均值，如果列表大小奇数，则计算中值。在许多递归步骤中执行此操作将生成非常准确的结果。