是否有一个快速算法在MapReduce框架上运行,以从一个巨大的整数集中找到中位数？
我就是这样做的.这是顺序quickselect的一种并行版本.(有些map/reduce工具可能不会让你轻松做事......)
选择一个小的,任意的输入集块.按顺序排序.我们将并行使用这些作为一大堆枢轴.调用这个数组pivots,并让它的大小k.
执行map/reduce如下:对于x输入集中的每个值,binary-search查找x相对于的位置pivots; 叫这个职位bucket(x).这是0和之间的整数k.reduce步骤是计算每个桶中的元素数量; 定义bucket[b]为xwith 的数量bucket(x) = b.
中位数必须在"中位数桶"中.挑出该中值桶中的所有值,并使用传统的顺序选择算法来查找具有正确索引的元素.
京公网安备 11010802040832号 | 京ICP备19059560号-6 