是否有一种快速算法可以在 MapReduce 框架上运行以从巨大的整数集中找到中位数？
我就是这样做的。这是顺序快速选择的一种并行版本。 （某些映射/归约工具可能无法让您轻松完成任务......）
选择输入集中的一个任意小块。按顺序对此进行排序。我们将并行地将它们用作一整套枢轴。调用这个数组pivots，并设其大小为k.
按如下方式执行映射/归约：对于每个值x在输入集中，二分查找查找x的位置相对于pivots;调用这个位置bucket(x)。这是一个介于0 and k。 reduce步骤是统计每个桶中元素的数量；定义bucket[b]为x with bucket(x) = b.
中位数必须位于“中位数桶”中。选出该中值桶中的所有值，并使用传统的顺序选择算法来查找具有正确索引的元素。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
