algorithm - 中位数算法理解的中位数

Question

我在网上搜索并访问了中位数算法的 wiki 页面。但似乎找不到我的问题的明确陈述：

如果一个人有一个非常大的整数列表（大小为 TB），并且想要以分布式方式找到该列表的中位数，则将列表分解为不同大小的子列表（或相等并不重要），然后继续计算那些较小子列表的中位数，然后计算这些中位数的中位数导致原始大列表的中位数？

此外，对于任何第 k 个统计数据，此语句是否也正确？我会对这个领域的研究等链接感兴趣。

Answer 1

The answer to your question is no.

If you want to understand how to actually select the k-th order statistics (including the median of course) in a parallel setting (distributed setting is of course not really different), take a look at this recent paper, in which I proposed a new algorithm improving the previous state of the art algorithm for parallel selection:

Deterministic parallel selection algorithms on coarse-grained multicomputers

Here, we use two weighted 3-medians as pivots, and partition around these pivots using five-way partitioning. We also implemented and tested the algorithm using MPI. Results are very good, taking into account that this is a deterministic algorithm exploiting the worst-case O(n) selection algorithm. Using the randomized O(n) QuickSelect algorithm provides an extremely fast parallel algorithm.

Answer 2

如果一个人有一个非常大的整数列表（大小为 TB），并且想要以分布式方式找到该列表的中位数，则将列表分解为不同大小的子列表（或相等并不重要），然后继续计算那些较小子列表的中位数，然后计算这些中位数的中位数导致原始大列表的中位数？

不是。整个列表的实际中位数不一定是任何子列表的中位数。

Median-of-medians 可以通过比随机选择的元素更接近实际中值来为您提供一个很好的快速选择枢轴选择，但是您必须执行其余的快速选择算法来定位较大列表的实际中值.