parallel-processing - 并行计算大型数组的中位数

Question

我曾经被问过这个问题，但仍然无法弄清楚：

你有一个N整数数组，其中N很大，比如十亿。你想计算这个数组的中值。假设你有m+1机器（m工人，一个主人）来分配工作。你会怎么做呢？

由于中位数是非线性算子，因此您不能只在每台机器中找到中位数，然后取这些值的中位数。

Answer 1

根据并行计算模型，算法可能会有所不同。（注意：上一句中链接到的 pdf 仅包含许多可能的 pdf 中的一些）。

^{求中位数是求第 i个}元素的特例。这个问题被称为“选择问题”，所以你需要在网上搜索并行选择。

这是一篇可能有用的论文（不幸的是，不是免费的）：Parallel Selection Algorithms With Analysis on Clusters。

谷歌查询“并行选择”的第一个链接给出：http ://www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.html它实际上使用中位数的中位数来解决一般问题，而不仅仅是中位数发现。

Answer 2

您可以进行高度可并行化的排序（如合并排序）并从结果中获取中值。

Answer 3

对数组进行排序会过大吗？如果没有，那么划分数组然后将结果合并在一起是我的建议。