问计算十亿个数字的中位数

EN

啊，我的大脑刚刚开始运转，我现在有一个明智的建议。如果这是一次面试，可能已经太晚了，但没关系：

机器1应称为“控制机器”，为了便于论证，它要么从所有数据开始，然后将其以相等的包发送给其他99台机器，要么开始在机器之间均匀分配数据，并将其数据的1/99发送给其他每台机器。分区不必相等，只需接近即可。

每台机器对其数据进行排序，并以一种倾向于首先找到较低值的方式进行排序。例如，快速排序，总是先对分区的较低部分进行排序*。它尽快将其数据以递增的顺序写回控制机器(使用异步IO以便继续排序，并可能使用Nagle on:实验一下)。

控制机器在数据到达时对其执行99路合并，但丢弃合并后的数据，仅对它看到的值的数量进行计数。它将中位数计算为1/2亿分之一和1/2亿加1的平均值。

这是一个“群体中最慢”的问题。直到分选机发送了小于中位数的每个值，该算法才能完成。有一个合理的机会，其中一个这样的值将在其数据包中相当高。因此，一旦完成数据的初始分区，估计的运行时间是排序1/99的数据并将其发送回控制计算机的时间和控件读取1/2数据的时间的组合。“组合”是介于这些时间的最大值和总和之间的某个地方，可能接近最大值。

我的直觉是，为了通过网络发送数据比排序更快(更不用说只选择中位数了)，它需要一个非常快的网络。如果可以假定网络是即时的，则可能是一个更好的前景，例如，如果您有100个内核，可以平等地访问包含数据的RAM。

由于网络I/O很可能是受限制的，因此可能会有一些技巧可以使用，至少对于返回到控制计算机的数据是这样。例如，不发送"1,2,3，.. 100"，也许分类机可以发送一条消息，意思是"100个值小于101“。然后，控制机器可以执行修改的合并，在该合并中，它找到所有那些范围顶端的值中的最小值，然后告诉所有排序机器它是什么，这样它们就可以(a)告诉控制机器有多少值比该值“计数”，以及(b)从这一点开始发送它们的排序数据。

更广泛地说，可能有一个巧妙的挑战-响应猜测游戏，控制机器可以与99台分拣机一起玩。

然而，这涉及到机器之间的往返，而我的更简单的第一个版本避免了这一点。我真的不知道如何盲目估计它们的相对性能，而且由于权衡是复杂的，我认为有比我自己认为的任何解决方案更好的解决方案，假设这是一个真正的问题。

*可用堆栈允许-如果您没有O(N)额外空间，那么您对先做哪一部分的选择会受到限制。但是如果你确实有足够的额外空间，你可以随意选择，如果你没有足够的空间，你至少可以使用你必须做的一些角落，通过首先为前几个分区做小部分。

我讨厌在这里做逆向投资者，但我不认为排序是必需的，而且我认为任何涉及对十亿/100个数字进行排序的算法都将是缓慢的。让我们考虑一台计算机上的一个算法。

1)从十亿中随机选择1000个值，并使用它们来了解数字的分布情况，特别是范围。

2)不是对值进行排序，而是根据您刚才计算的分布将其分配到存储桶中。选择存储桶的数量是为了使计算机能够有效地处理它们，但在其他情况下应该尽可能大。存储桶范围应该使每个存储桶中的值数量大致相等(这对算法并不关键，但有助于提高效率。100,000个存储桶可能是合适的)。注意每个存储桶中的值的数量。这是一个O(n)过程。

3)找出中位数所在的存储桶范围。这可以通过简单地检查每个存储桶中的总数来完成。

4)通过检查该桶中的值来找到实际的中位数。如果您愿意，您可以在这里使用排序，因为您只能对大约10,000个数字进行排序。如果该存储桶中的值的数量很大，则可以再次使用此算法，直到有足够小的值进行排序。

这种方法通过在计算机之间划分值来实现微不足道的并行。每台计算机将每个存储桶中的总和报告给执行步骤3的“控制”计算机。对于步骤4，每台计算机将相关存储桶中的(排序的)值发送到控制计算机(您也可以并行执行这两个算法，但可能不值得这样做)。

整个过程是O(n)，因为只要存储桶的数量足够大，步骤3和4都是微不足道的。