求出大型数字列表的平均值

Question

遇到了这个面试问题。

编写一个算法来找到一个大列表的平均(平均值)。此列表可以包含数万亿或万亿个数字。每一个数字都是可以管理的，有数百，数千，甚至几百万。

谷歌给了我所有的Median of Medians解决方案。我应该如何处理这个问题？

分而治之是否足以应付数以万亿计的数字？

如何处理这么大的清单？

Answer 1

如果列表的大小是可计算的，这实际上只是一个问题，你有多少内存，它应该花多长时间，以及算法应该有多简单。

基本上，你可以把所有的东西加起来，除以大小。

如果您没有足够的内存，那么先除法可能会奏效(请注意，这样可能会丢失一些精度)。

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

但是，如果列表如此庞大，以至于无法计算其大小，则无法将其拆分为两个子列表。在这种情况下，递归方法的工作方式正好相反。与其使用n/2元素拆分为2个列表，不如将其拆分为带有2个元素的n/2列表(或者更确切地说，立即计算它们的平均值)。基本上，你可以计算元素1和2的平均值，也就是新元素1。3和4的平均值是新的第二个元素，依此类推。然后对新列表应用相同的算法，直到只剩下一个元素。如果遇到奇数大小的列表，可以在末尾添加一个元素，或者忽略最后一个元素。如果你加了一个，你应该尽量接近你预期的平均值。

虽然这不能精确地计算出这个大小的列表的平均值，但它将足够接近。这几乎是一种mean of means方法。您还可以选择median of medians路径，在这种情况下，您可以递归地选择子列表的中位数。同样的原则也适用，但是你通常希望得到一个奇数。

你甚至可以将这些方法结合起来，计算出如果你的列表是偶数大小的话的平均值，如果它是奇数大小的，则计算中值。通过许多递归步骤这样做将产生相当准确的结果。

Answer 2

首先，这是一个面试问题。上述问题在实践中不会出现。此外，这里所述的问题是不准确的。这可能是故意的。(他们想看看你是如何解决一个不精确的问题的。)

编写一个算法来找到一个大列表的平均(平均值)。

• “发现”这个词很有弹性。它可能意味着计算(达到某种精度)，也可能意味着估计。
• “大名单”这个词很有弹性。如果可以表示内存中的列表或数组数据结构，或者“列表”可能是数据库查询的结果，则是一个或多个文件的内容。
• 没有提到在系统上实现这一目标的硬件限制。

所以>>I<<会做的第一件事就是通过问面试官的一些问题来缩小范围。

但假设你做不到，那么一个完整的答案需要包括以下几点：

• 数据集可能无法同时存储在内存中。(但如果是这样的话，那就好了。)
• 如果按顺序计算N数的平均值，则为O(N)。对于N的大小，这可能是一个棘手的问题。
• 另一种方法是将等号划分为子列表，计算平均值和平均值。理论上，这给出了O(N/P)，其中P是分区的数量。并行可以用多个线程、同一台机器上的多个进程或分布式实现。
• 实际上，限制因素将是计算、内存和/或I/O带宽。如果您能够解决这些限制，并行解决方案将是有效的。例如，您需要平衡每个“工作人员”对其“子列表”的无竞争访问权的问题和创建数据副本的问题，以便实现这一目标。
• 如果列表以允许抽样的方式表示，则可以在不查看整个数据集的情况下估计平均值。实际上，这可能是O(C)，这取决于您的示例方式。但有一个风险，你的样本将是没有代表性的，平均将是太不准确。
• 在进行计算的所有情况下，都需要防止(整数)溢出和(浮点)舍入错误。尤其是在计算总和的时候。
• 有必要讨论如何使用“大数据”平台(例如Hadoop)来解决这个问题，以及这种方法的局限性(例如加载数据所需的时间.)。