今天面试问题:有一个整数数组,如何find kth smallest element,如果数据是dynamic# JobHunting - 待字闺中a*e2013-01-25 08:011 楼就是说不断有新数据输入,而且数据量很大,分布在多个机器上,(新的data push到哪个机器上是随机的)。怎样做效率比较高?谢谢。
c*t2013-01-25 08:012 楼maintain a k size min-heap on each machine. Then merge-sort them to a mastermachine.
j*y2013-01-25 08:013 楼每台机器用一个 max queue of size k 保留 k个最小的数然后再 merge 这些不同机器上的 queque【在 a**********e 的大作中提到】: 就是说不断有新数据输入,而且数据量很大,分布在多个机器上,(新的data push到: 哪个机器上是随机的)。: 怎样做效率比较高?谢谢。
P*r2013-01-25 08:014 楼max heap of the smallest k numbers?如果有个新数,小于max, delete max,heapify。master【在 c********t 的大作中提到】: maintain a k size min-heap on each machine. Then merge-sort them to a master: machine.
c*t2013-01-25 08:015 楼你说得对!【在 P******r 的大作中提到】: max heap of the smallest k numbers?如果有个新数,小于max, delete max,: heapify。: : master
e*s2013-01-25 08:016 楼delete max 应该是 replace max with new value吧?【在 P******r 的大作中提到】: max heap of the smallest k numbers?如果有个新数,小于max, delete max,: heapify。: : master
a*e2013-01-25 08:017 楼谢谢。既然涉及master machine,可不可以每次有data进来,(在store在各个机器上的同时),直接把data也push一份到master machine上,这样只要在master machine上维持max heap就可以了。这样有什么问题呢?master【在 c********t 的大作中提到】: maintain a k size min-heap on each machine. Then merge-sort them to a master: machine.
c*t2013-01-25 08:018 楼我觉得,选择push还是poll要看requirement,如果这k个数据很常用,时时刻刻都会被调用,那就push吧,如果只是偶尔查,那就要用的时候再从各个机器上poll.无论哪种,都要在每台机器上存这个heap,否则传输出什么问题怎么办?【在 a**********e 的大作中提到】: 谢谢。: 既然涉及master machine,可不可以每次有data进来,(在store在各个机器上的同时: ),直接: 把data也push一份到master machine上,这样只要在master machine上维持max heap就: 可以了。: 这样有什么问题呢?: : master