我在网上搜索过并访问了中位数算法的维基页面。但好像没有找到明确回答我的问题：
如果有一个非常非常大（TB级别）的整数列表，想以分布式方式查找此列表的中位数，将该列表分成不同大小的子列表（或等大小的子列表），然后继续计算这些较小子列表的中位数，那么计算出来的中位数列表再计算一次中位数能不能得到原始大列表的中位数?
此外，对于任何第k个统计信息，此说明是否也正确? 我会对这个领域的研究链接感兴趣。
中位数算法理解
4
- Jared Krumsie
1
1这个问题非常适合即将推出的计算机科学Stack Exchange，如果您希望有一个像这样的问题平台，请帮助该提案获得成功！ - Raphael
2个回答
12
您的问题的答案是否定的。
如果您想了解如何在并行设置中（当然，分布式设置并没有真正不同）实际选择第k个顺序统计量（包括中位数），请查看这篇最近的论文。在这篇论文中，我提出了一种新的算法，改进了之前现有的最优算法，用于并行选择： 基于粗粒度多计算机的确定性并行选择算法 在这里，我们使用两个加权的3分位数作为主元，并围绕这些主元使用五分区进行划分。我们还使用MPI实现和测试了该算法。结果非常好，考虑到这是一种利用最坏情况O(n)选择算法的确定性算法。使用随机化的O(n) QuickSelect算法提供了一种极快的并行算法。
如果您想了解如何在并行设置中（当然，分布式设置并没有真正不同）实际选择第k个顺序统计量（包括中位数），请查看这篇最近的论文。在这篇论文中，我提出了一种新的算法，改进了之前现有的最优算法，用于并行选择： 基于粗粒度多计算机的确定性并行选择算法 在这里，我们使用两个加权的3分位数作为主元，并围绕这些主元使用五分区进行划分。我们还使用MPI实现和测试了该算法。结果非常好，考虑到这是一种利用最坏情况O(n)选择算法的确定性算法。使用随机化的O(n) QuickSelect算法提供了一种极快的并行算法。
- Massimo Cafaro
1
2你有没有一个不需要付款的网站链接？因为我真的很想读你的论文。 - Jared Krumsie
7
如果有一个非常大的整数列表（以TB为单位），想要以分布式的方式找到该列表的中位数，那么将该列表分成大小不同（或相等）的子列表，然后计算这些较小子列表的中位数，再计算这些中位数的中位数是否能得到原始大列表的中位数呢？
不行。整个列表的实际中位数不一定是任何子列表的中位数。
通过中位数法可以选择快速选择的枢轴，因为它比随机选取的元素更接近实际中位数，但是您需要执行剩余的快速选择算法来找到较大列表的实际中位数。
不行。整个列表的实际中位数不一定是任何子列表的中位数。
通过中位数法可以选择快速选择的枢轴，因为它比随机选取的元素更接近实际中位数，但是您需要执行剩余的快速选择算法来找到较大列表的实际中位数。
- Don Roby
1
因此，快速选择部分必须是在每个节点上运行的计算，我遇到的问题是如何合并结果，如果可能的话。 - Jared Krumsie
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接