rec*_*ion 2 parallel-processing median
我被问过这个问题一次,仍然无法弄清楚:
你有一个N整数数组,其中N很大,比如十亿.您想要计算此数组的中值.假设您有m+1机器(m工人,一个主人)来分配作业.你会怎么做呢？
由于中位数是一个非线性算子,你不能只找到每台机器的中位数,然后取这些值的中位数.
小智 6
根据并行计算模型,算法可能会有所不同.(注意:在前一句中链接的pdf只包含许多可能的内容).
找到中位数是找到第i 个元素的特例.此问题称为"选择问题",因此您需要在Web上搜索并行选择.
这是一篇可能有用的论文(遗憾的是,不是免费的):并行选择算法和集群分析.
谷歌查询"并行选择"的第一个链接给出:http://www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.html实际上使用中位数的中位数来解决一般问题而不仅仅是中位数发现.