计算十亿个数字的中位数

  • 回答 (2)
  • 关注 (0)
  • 查看 (13)

如果你有十亿个数字和一百台电脑,找出这些数字的中位数的最好方法是什么?

我拥有的一个解决方案是:

  • 在计算机之间平均分配设置。
  • 对它们排序。
  • 找到每组的中位数。
  • 将集合排序在中位数上。
  • 从最低位到最高位一次合并两组。

如果我们m1 < m2 < m3 ...先合并Set1Set2并且在结果集合中,我们可以丢弃所有低于Set12(合并)中位数的数字。所以在任何时候我们都有相同尺寸的套装。顺便说一下,这不能以平行的方式完成。有任何想法吗?

土子美土子美提问于
Rom_z全职程序员,喜欢围棋回答于

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

机器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)额外空间,您首先要做的部分选择受到限制。但是如果你有足够的额外空间,你可以选择,如果你没有足够的空间,你至少可以使用你必须削减的一些角落,通过在前几个分区中首先做一小部分。

小狼学习一切回答于
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

扫码关注云+社区