你真的需要精确的中位数和分位数吗？
很多时候，您最好只获取近似值，并使用它们，特别是当您将其用于数据分区时。
实际上，您可以使用近似分位数来加快查找精确分位数的速度（实际上是 O(n/p) 时间），这里是战略的大致轮廓：
每个分区都有一个Map器来计算所需的分位数，并将它们输出到一个新的数据集。这个数据集应该小几个数量级（除非你要求太多的分位数！）
在这个数据集中，再次计算分位数，类似于“中位数”。这是你的初步估计。
根据这些分位数重新划分数据（甚至通过这种方式获得额外的分区）。目标是最终保证真正的分位数在一个分区中，并且每个分区中最多应该有一个期望的分位数
在每个分区中，执行快速选择（in O(n) )找到真正的分位数。
每一步都是线性时间。最昂贵的步骤是第3部分，因为它需要重新分配整个数据集，所以它会生成 O(n) 网络流量。您可能可以通过为第一次迭代选择“备用”分位数来优化过程。比如说，你想找到全球的中位数。在线性过程中很难找到它，但是当它被划分为k个分区时，可以将它缩小到数据集的1/kt。因此，不是让每个节点报告其中值，而是让每个节点额外报告（k-1）/（2k）和（k+1）/（2k）处的对象。这将允许您缩小真实中值必须显著存在的值的范围。因此，在下一步中，您可以将每个节点都发送到一个主节点，并且只选择该范围内的中间值。

在许多实际场景中，数据集中值的基数相对较小。在这种情况下，可以通过两个mapreduce作业有效地解决问题：
计算数据集中值的频率（基本上是字数计算工作）
身份Map器+一个基于对计算中值的缩减器
工作1。将大大减少数据量，并且可以完全并行执行。工作2的减速器。只需处理 n ( n = cardinality of your value set )项而不是所有值，就像使用naive方法一样。
下面是作业2的示例。它是可以直接在hadoop流媒体中使用的python脚本。假设数据集中的值是 ints ，但很容易被采用 double s

import sys

item_to_index_range = []
total_count = 0

# Store in memory a mapping of a value to the range of indexes it has in a sorted list of all values

for line in sys.stdin:
    item, count = line.strip().split("\t", 1)
    new_total_count = total_count + int(count)
    item_to_index_range.append((item, (total_count + 1,   new_total_count + 1)))
    total_count = new_total_count

# Calculate index(es) of middle items

middle_items_indexes = [(total_count / 2) + 1]
if total_count % 2 == 0:
    middle_items_indexes += [total_count / 2]

# Retrieve middle item(s)

middle_items = []
for i in middle_items_indexes:
    for item, index_range in item_to_index_range:
        if i in range(*index_range):
            middle_items.append(item)
            continue

print sum(middle_items) / float(len(middle_items))

这个答案建立在最初来自chriswhite的答案的建议之上。答案是使用组合器作为平均值来计算值的频率。然而，在mapreduce中，合并器不能保证总是被执行。这有一些副作用：
reducer首先需要计算final对，然后计算中值。
在最坏的情况下，组合器将永远不会被执行，而reducer仍然需要处理所有单个值

o（（n logn）/p）对其排序，然后o（1）得到中值。
对。。。可以得到o（n/p），但不能使用hadoop中现成的排序功能。我只会排序并获取中心项，除非您可以证明2-20小时的开发时间来编写并行第k个最大的算法。

试图在一个系列中找到中位数（中间数）需要将1个减速机传递给整个数字范围，以确定哪个是“中间”值。
根据输入集中值的范围和唯一性，您可以引入一个组合器来输出每个值的频率—减少发送到单个缩减器的map输出的数量。然后，reducer可以使用排序值/频率对来识别中值。
另一种扩展方法（如果您知道值的范围和粗略分布的话）是使用自定义分区器，它按范围桶（0-99到reducer 0，100-199到reducer 2，依此类推）分配键。但是，这将需要一些辅助工作来检查减速机输出并执行最终的中值计算（例如知道每个减速机中的键数，您可以计算哪个减速机输出将包含中值，以及在哪个偏移处）