计算十亿个数字的中位数

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

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

如果你有10亿个数字和100台计算机,那么找到这些数字的中位数的最好方法是什么?

我有一个解决办法是:

  • 在电脑间平均分配这台电视机。
  • 把它们分类。
  • 为每一组找到中间值。
  • 对中间装置进行排序。
  • 每次合并两组,从最低到最高的中位数。

如果我们有m1 < m2 < m3 .然后第一次合并Set1Set2在结果集中,我们可以丢弃所有低于Set12(合并)。因此,在任何时候,我们都有相同大小的集合。顺便说一句,这不能以并行的方式进行。有什么想法吗?

提问于
用户回答回答于

机器1应称为“控制机器”,为了便于论证,它要么以所有数据开始,然后以等量的方式发送给其他99台机器,要么数据开始在机器之间均匀分布,然后将其数据的1/99发送给其他机器。分区不必相等,只需关闭。

彼此的机器对其数据进行排序,这样做的方式有利于首先找到较低的值。例如,快速排序,总是首先对分区的下部进行排序。

控制机器在数据到达时对数据执行99路合并,但是丢弃合并的数据,只需计算它所看到的值的数量。它计算的中位数是1/20亿和1/20亿加上1/20数值的平均值。

这就受到了“羊群中最慢的”问题的困扰。在每一个小于中值的值被排序机发送之前,该算法无法完成。有一个合理的机会,这样的价值将是相当高的包内的数据。因此,一旦数据的初始分区完成,估计的运行时间就是将1/99的数据排序并发送回控制计算机的时间和控件读取1/2数据的时间的组合。“组合”介于最大值和时间之和之间,可能接近最大值。

我的直觉是,要想在网络上发送数据比排序更快(更不用说选择中值了),它需要是一个非常快的网络。如果可以假定网络是瞬时的,例如,如果您有100个具有相同访问权限的RAM(包含数据)的内核,则可能是一个更好的前景。

由于网络I/O很可能是绑定的,所以可能会玩一些技巧,至少对于返回到控制机器的数据是这样的。例如,与其发送“1,2,3”,“100”,一台分拣机可能会发送一条消息,意思是“100值小于101”。然后,控制机器可以执行一个修改后的合并,在其中找到所有顶级值中最少的值,然后告诉所有排序机器它是什么,这样它们就可以(A)告诉控制机器在该值以下要“计数”多少个值,以及(B)继续从这个点发送他们排序的数据。

不过,这涉及到机器之间的往返旅行,而我的第一个简单版本则避免了这一点。我真的不知道如何盲目估计他们的相对表现,而且由于权衡是复杂的,我想有比我自己想的更好的解决方案,假设这是一个真正的问题。

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

用户回答回答于
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

扫码关注云+社区