mapreduce - 使用 MapReduce 查找大整数集的中值

Question

是否有一种快速算法可以在 MapReduce 框架上运行以从巨大的整数集中查找中位数？

Answer 1

我会这样做。这是顺序快速选择的一种并行版本。 (某些映射/归约工具可能不会让您轻松完成任务...)

从输入集中选择一个小的、任意的 block 。按顺序对此进行排序。我们将并行地将它们用作一整套枢轴。将此数组命名为pivots，并指定其大小为k。

按如下方式执行映射/归约:对于输入集中的每个值 x，进行二分搜索以查找 x 相对于 pivots< 的位置;将此位置称为bucket(x)。这是 0 和 k 之间的整数。 reduce步骤是统计每个桶中元素的数量；将 bucket[b] 定义为 x 的数量，其中 bucket(x) = b。

中位数必须位于“中位数桶”中。选出该中值桶中的所有值，并使用传统的顺序选择算法来查找具有正确索引的元素。