algorithm - 计算十亿个数字的中位数

Question

如果您有 10 亿个数字和一百台计算机，找出这些数字的中位数的最佳方法是什么？

我的一个解决方案是:

• 在计算机之间平均分配集合。
• 对它们进行排序。
• 找出每组的中位数。
• 按中位数对集合进行排序。
• 一次合并两个集合，从最低到最高中位数。

如果我们有m1 < m2 < m3 ...然后先合并Set1和 Set2在结果集中，我们可以丢弃所有低于 Set12 中位数的数字(合并)。所以在任何时候我们都有相同大小的集合。顺便说一句，这不能以并行方式完成。有什么想法吗？

Answer 1

啊，我的脑子刚开始运转，我现在有一个明智的建议。如果这是一次采访，可能为时已晚，但没关系:

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

每台其他机器对其数据进行排序，并以有利于首先找到较低值的方式进行排序。因此，例如快速排序，总是首先对分区的较低部分进行排序[*]。它会尽快以递增的顺序将其数据写回控制机器(使用异步 IO 以继续排序，并且可能会启用 Nagle:进行一些实验)。

控制机器在数据到达时对数据执行 99 路合并，但丢弃合并的数据，只记录它看到的值的数量。它将中位数计算为十亿分之 1/2 和十亿分之一以上的平均值。

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

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

由于网络 I/O 很可能是受限的，因此您可以使用一些技巧，至少对于返回控制机器的数据而言。例如，不是发送“1,2,3,.. 100”，也许分拣机可以发送一条消息，意思是“100 个值小于 101”。控制机器然后可以执行修改后的合并，在其中它找到所有这些最高范围值中的最小值，然后告诉所有分拣机器它是什么，以便它们可以 (a) 告诉控制机器如何许多值“计数”低于该值，并且 (b) 从该点恢复发送它们的排序数据。

更一般地，控制机器可以与 99 分选机一起玩一个聪明的挑战-响应猜谜游戏。

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

[*] 可用堆栈允许 - 如果您没有 O(N) 额外空间，您选择先执行哪一部分将受到限制。但是如果你有足够的额外空间，你可以随意选择，如果你没有足够的空间，你至少可以使用你所需要的东西来偷工减料，首先为前几个分区做小部分。