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

啊，我的大脑刚刚起步，现在我有一个明智的建议。如果这是一次采访，可能太晚了，但不要介意：

机器1将被称为“控制机器”，并且为了争论起见它要么从所有数据开始，并且以相同的包裹将其发送到其他99台机器，否则数据开始在机器之间均匀分配，并且它将1/99的数据发送给其他每个人。分区不必相同，只需关闭即可。

每个其他机器对其数据进行排序，并且这样做有利于首先找到较低的值。因此，例如快速排序，总是首先对分区的下半部分进行排序[*]。它会尽快将其数据写回控制机器（使用异步IO以继续排序，并且可能使用Nagle：试验一下）。

控制机器在数据到达时对数据执行99路合并，但丢弃合并的数据，只保留所看到的数值的数量。它将中值计算为第二十亿分之十五十十亿以上的平均值。

这受到“牛群中最慢”问题的影响。直到分类机器发送的每个小于中值的值都不能完成该算法。有一个合理的机会，一个这样的数值在其数据包中会很高。因此，一旦数据的初始分区完成，估计的运行时间就是排序1/99数据的时间并将其发送回控制计算机，并且控制读取1/2数据的时间。“组合”介于最大值和这些时间之和之间，可能接近最大值。

我的直觉是，通过网络发送数据比排序更快（更不用说只是选择中位数），它需要成为一个相当糟糕的快速网络。如果可以假定网络是瞬时的，例如，如果您有100个内核可以访问包含数据的RAM，则可能会更好。

由于网络I / O很可能会受到限制，因此可能会出现一些技巧，至少可以将数据传回控制机器。例如，不是发送“1,2,3，... 100”，也许分拣机器可以发送一个消息，意思是“100个值小于101”。然后控制机器可以执行一个修改合并，在该合并中，它找到所有这些最高范围值中的最小值，然后告诉所有分拣机器它是什么，以便他们可以（a）告诉控制机器如何许多值“低于”该值，并且（b）从该点继续发送它们的排序数据。

更一般地说，控制机器可以使用99个分拣机器玩一个聪明的挑战 - 反应猜谜游戏。

这涉及到机器之间的往返，但是，我的简单的第一个版本避免了这种情况。我真的不知道如何盲目估计他们的相对表现，而且由于取舍是复杂的，所以我认为在那里有比我想象的更好的解决方案，假设这是一个真正的问题。

[*]可用堆栈许可 - 如果您没有O（N）额外空间，您首先要做的部分选择受到限制。但是如果你有足够的额外空间，你可以选择，如果你没有足够的空间，你至少可以使用你必须削减的一些角落，通过在前几个分区中首先做一小部分。