algorithm - 计算十亿个数字的中位数

Question

如果您有 10 亿个数字和 100 台计算机，那么找出这些数字中位数的最佳方法是什么？

我拥有的一种解决方案是：

• 在计算机之间平均分配集合。
• 对它们进行排序。
• 找出每组的中位数。
• 按中位数对集合进行排序。
• 一次合并两组从最低到最高的中位数。

如果我们m1 < m2 < m3 ...首先合并Set1并且Set2在结果集中我们可以丢弃所有低于Set12（合并）中位数的数字。所以在任何时候我们都有相同大小的集合。顺便说一句，这不能以并行方式完成。有任何想法吗？

Answer 1

啊，我的大脑刚刚开始运转，我现在有一个明智的建议。如果这是一次采访，可能为时已晚，但没关系：

机器 1 应称为“控制机器”，为了论证起见，它要么从所有数据开始，然后将其等分发送给其他 99 台机器，要么数据开始在机器之间均匀分布，并且它将其数据的 1/99 发送给其他每个人。分区不必相等，只需关闭即可。

每台其他机器都会对其数据进行排序，并且这样做的方式有利于首先找到较低的值。因此，例如快速排序，总是首先对分区的下部进行排序[*]。它会尽快将其数据以递增的顺序写回控制机器（使用异步 IO 以继续排序，并且可能在 Nagle 开启的情况下：进行一些实验）。

控制机器在数据到达时对数据执行 99 路合并，但丢弃合并的数据，只记录它看到的值的数量。它将中值计算为 1/2 十亿和 1/2 亿加 1 值的平均值。

这遭受了“群中最慢”的问题。直到每个小于中位数的值都由分拣机发送后，该算法才能完成。一个这样的值在其数据包中相当高的可能性是合理的。所以一旦数据的初始分区完成，估计的运行时间是排序1/99数据并将其发送回控制计算机的时间，以及控制读取1/2数据的时间的组合。 . “组合”介于最大值和这些时间的总和之间，可能接近最大值。

我的直觉是，为了通过网络发送数据比排序更快（更不用说选择中位数），它需要一个非常快的网络。如果可以假定网络是瞬时的，那么前景可能会更好，例如，如果您有 100 个内核可以平等地访问包含数据的 RAM。

由于网络 I/O 可能是限制因素，因此您可能会玩一些技巧，至少对于返回控制机器的数据而言。例如，不是发送“1,2,3,.. 100”，也许分拣机可以发送一条消息，意思是“100 个值小于 101”。然后，控制机器可以执行修改后的合并，在该合并中它找到所有范围顶部值中的最小值，然后告诉所有分拣机它是什么，以便它们可以 (a) 告诉控制机器如何许多值要“计数”低于该值，并且（b）从该点继续发送它们的排序数据。

更一般地说，控制机器可能会与 99 台分拣机一起玩一个聪明的挑战-响应猜谜游戏。

不过，这涉及机器之间的往返，而我更简单的第一个版本避免了这种情况。我真的不知道如何盲目估计他们的相对表现，而且由于权衡很复杂，我想有比我自己想象的更好的解决方案，假设这是一个真正的问题。

[*] 可用堆栈允许 - 如果您没有 O(N) 额外空间，您对首先执行哪个部分的选择会受到限制。但是如果你有足够的额外空间，你可以选择，如果你没有足够的空间，你至少可以使用你必须做的事情来减少一些角落，首先为前几个分区做一小部分。

Answer 2

sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

Answer 3

我讨厌在这里成为逆势者，但我认为不需要排序，而且我认为任何涉及对十亿/ 100 个数字进行排序的算法都会很慢。让我们考虑一台计算机上的算法。

1）从十亿中随机选择1000个值，并用它们来了解数字的分布，尤其是一个范围。

2) 不要对值进行排序，而是根据您刚刚计算的分布将它们分配到存储桶中。选择桶的数量以便计算机可以有效地处理它们，但在其他方面应该尽可能大。存储桶范围应该使得每个存储桶中的值数量大致相等（这对算法来说并不重要，但它有助于提高效率。100,000 个存储桶可能是合适的）。请注意每个存储桶中的值的数量。这是一个 O(n) 过程。

3）找出中位数所在的桶范围。这可以通过简单地检查每个桶中的总数来完成。

4）通过检查该桶中的值来找到实际的中位数。如果您愿意，您可以在此处使用排序，因为您只对可能 10,000 个数字进行排序。如果该桶中的值的数量很大，那么您可以再次使用此算法，直到您有足够小的数量进行排序。

这种方法通过在计算机之间划分值来实现微不足道的并行化。每台计算机将每个桶中的总数报告给执行第 3 步的“控制”计算机。对于第 4 步，每台计算机将相关桶中的（排序）值发送到控制计算机（您也可以并行执行这两种算法，但这可能不值得）。

总过程是 O(n)，因为步骤 3 和 4 都很简单，只要桶的数量足够大。

Answer 4

对于现代计算机来说，10 亿实际上是一项相当无聊的任务。我们在这里谈论的是 4 GB 的 4 字节整数...... 4 GB ......这是一些智能手机的 RAM。

public class Median {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] numbers = new int[1_000_000_000];

        System.out.println("created array after " +  (System.currentTimeMillis() - start) + " ms");

        Random rand = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = rand.nextInt();
        }

        System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");

        Arrays.sort(numbers);

        System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");

        if (numbers.length % 2 == 1) {
            System.out.println("median = " + numbers[numbers.length / 2 - 1]);
        } else {
            int m1 = numbers[numbers.length / 2 - 1];
            int m2 = numbers[numbers.length / 2];
            double m = ((long) m1 + m2) / 2.0;
            System.out.println("median = " + new DecimalFormat("#.#").format(m));
        }
}

我机器上的输出：

created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196

因此，这在我的机器上使用单核不到两分钟（其中 0:10 用于生成随机数的 1:43）就完成了，它甚至可以进行完整的排序。真的没有什么花哨的。

对于更大的数字集，这无疑是一项有趣的任务。我只想在这里说明一点：十亿是花生。因此，在您开始将复杂的解决方案用于令人惊讶的简单任务之前，请三思而后行；）

Answer 5

可以使用t-digest或Q-digest等算法有效地分配中位数和第 99 个百分位数等顺序统计信息的估计。

使用任一算法，每个节点都会生成一个摘要，它表示本地存储的值的分布。摘要在单个节点收集，合并（有效地对分布求和），然后可以查找中位数或任何其他百分位数。

这种方法被 elasticsearch 使用，大概还有BigQuery （根据QUANTILES函数的描述）。

Answer 6

这组数字的中位数

2、3、5、7、11、13、67、71、73、79、83、89、97

是 67 岁。

这组数字的中位数

2、3、5、7、11、13、67、71、73、79、83、89

是40。

假设问题是大约 1,000,000,000 个整数（x），其中 0 >= x <= 2,147,483,647 并且 OP 正在寻找 (element(499,999,999) + element(500,000,000)) / 2（如果数字已排序）。 还假设所有 100 台计算机都是平等的。

使用我的笔记本电脑和 GigE...

我发现我的笔记本电脑可以在 1.3 秒内对 10,000,000 个 Int32 进行排序。所以粗略估计十亿个数字排序需要 100 x 1.3 秒（2 分 10 秒）;)。

在千兆以太网上单向传输 40MB 文件的估计时间为 0.32 秒。这意味着所有计算机的排序结果将在大约 32 秒内返回（计算机 99 直到启动后 30 秒才得到他的文件）。从那里很快就可以丢弃最低的 499,999,998 个数字，加上下一个 2 并除以 2。

Answer 7

这可能会让人们感到惊讶，但如果数字是足够小的整数以适合 32 位（或更小） - 只需进行桶排序！对于任意数量的 32 位整数只需要 16GB 的内存并在 O(n) 中运行，这在合理的 n（例如十亿）内应该优于任何分布式系统。

一旦你有了排序列表，挑选中位数就很简单了。实际上，您不需要构建排序列表，只需查看存储桶即可。

一个简单的实现如下所示。仅适用于 16 位整数，但扩展到 32 位应该很容易。

#include <stdio.h>
#include <string.h>

int main()
{
    unsigned short buckets[65536];
    int input, n=0, count=0, i;

    // calculate buckets
    memset(buckets, 0, sizeof(buckets));
    while (scanf("%d", &input) != EOF)
    {
        buckets[input & 0xffff]++;
        n++;
    }

    // find median 
    while (count <= n/2)
    {
        count += buckets[i++];
    }

    printf("median: %d\n", i-1);

    return 0;
}

使用具有十亿 (10 ⁹ ) 个数字的文本文件并time像这样运行

time ./median < billion

在我的机器上产生运行时间 1m49.293s。大部分运行时间也可能是磁盘 IO。

Answer 8

奇怪的是，我认为如果你有足够的计算机，你最好进行排序而不是使用O(n)中值查找算法。（除非您的内核非常非常慢，否则我只会使用一个并使用O(n)仅针对 1e9 数字的中值查找算法；但是，如果您有 1e12，那可能不太实用。）

无论如何，假设我们有超过 log n 个内核来处理这个问题，并且我们不关心功耗，只是快速得到答案。让我们进一步假设这是一台 SMP 机器，所有数据都已加载到内存中。（例如，Sun 的 32 核机器就是这种类型。）

一个线程盲目地将列表分成大小相等的部分，并告诉其他 M 个线程对它们进行排序。这些线程及时地努力这样做(n/M) log (n/M)。然后，它们不仅返回中位数，而且还返回第 25 和第 75 个百分位数（如果您选择稍微不同的数字，则反常的最坏情况会更好）。现在您有 4M 范围的数据。然后，您对这些范围进行排序并在列表中向上工作，直到找到一个数字，如果您丢弃小于或包含该数字的每个范围，您将丢弃一半的数据。这是中位数的下限。对上限做同样的事情。这需要一些M log M时间，并且所有内核都必须等待它，所以这真的很浪费M^2 log M潜在的时间。现在你有你的单线程告诉其他人扔掉范围之外的所有数据（你应该在每次传递中扔掉大约一半）并重复 - 这是一个非常快速的操作，因为数据已经排序。您不必多次重复此log(n/M)操作，就可以更快地获取剩余数据并在其上使用标准O(n)中值查找器。

因此，总复杂度类似于O((n/M) log (n/M) + M^2 log M log (n/M)). 因此，这比O(n)一个核心上的中位数排序更快 ifM >> log(n/M)和M^3 log M < n，这对于您描述的场景是正确的。

考虑到它的效率很低，我认为这是一个非常糟糕的主意，但它更快。

Answer 9

这可以比投票算法更快完成（n log n）

- 顺序统计分布式选择算法 - O(n)
将问题简化为在未排序数组中查找第 k 个数字的原始问题。
- 计数排序直方图 O(n)
你必须假设一些关于数字范围的属性 - 范围是否适合内存？- 外部合并排序 - O(n log n) - 如上所述
您基本上在第一遍对数字进行排序，然后在第二遍找到中位数。
- 如果知道关于数字分布的任何信息，则可以生成其他算法。

更多细节和实现见：
http ://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

Answer 10

一台电脑足以解决问题。

但是让我们假设有 100 台计算机。您应该做的唯一复杂的事情是对列表进行排序。将其拆分为 100 个部分，将一个部分发送到每台计算机，让它们在那里分类，然后合并部分。

然后从排序列表的中间取数字（即索引为 5 000 000 000）。

Answer 11

这取决于您的数据。最坏的情况是它是均匀分布的数字。

在这种情况下，您可以在 O(N) 时间内找到中位数，如下例所示：

假设您的数字是 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3（范围是 1-10） .

我们创建了 3 个桶：1-3、4-7、8-10。请注意，顶部和底部的大小相同。

我们用数字填充桶，计算每个下降的数量，最大值和最小值

• 低 (5)：2,1,1,3,3，最小 1，最大 3
• 中间 (10): 7,5,6,4,4,6,4,7,4,4, 最少 4, 最多 7
• 高 (5): 10, 10, 8, 9, 9, 最小 8, 最大 10

平均值落在中间的桶中，我们忽略其余部分

我们创建了 3 个桶：4、5-6、7。Low 将从 5 开始，最大值为 3，high 以最小值 8 和 5 开始。

对于每个数字，我们计算有多少落在低桶和高桶中，最大值和最小值，并保留中间桶。

• 旧低 (5)
• 低 (5): 4, 4, 4, 4, 4, 最大 4
• 中间（3）：5,6,6
• 高 (2): 7, 7, min 7
• 老高 (5)

现在我们可以直接计算中位数：我们有这样的情况

old low    low          middle  high  old high
x x x x x  4 4 4 4 4 4   5 6 6  7 7   x x x x x

所以中位数是 4.5。

假设您对分布有所了解，您可以微调如何定义范围以优化速度。无论如何，性能应该与 O(N) 一致，因为 1 + 1/3 + 1/9... = 1.5

由于边缘情况，您需要 min 和 max（例如，如果中位数是旧低点的最大值与下一个元素之间的平均值）。

所有这些操作都可以并行化，你可以将 1/100 的数据给每台计算机，计算每个节点的 3 个桶，然后分配你保留的桶。这再次使您可以有效地使用网络，因为每个数字平均传递 1.5 次（所以 O(N)）。如果你只在节点之间传递最少的数字，你甚至可以击败它（例如，如果节点 1 有 100 个数字，节点 2 有 150 个数字，那么节点 2 可以给节点 1 25 个数字）。

除非您对分布有更多了解，否则我怀疑您是否能比 O(N) 做得更好，因为您实际上需要至少计算一次元素。

Answer 12

一种更简单的方法是使用加权数字。

• 在计算机之间拆分大集合
• 对每组进行排序
• 遍历小集合，并计算重复元素的权重
• 将每 2 个集合合并为 1 个（每个都已排序）更新权重
• 继续合并集合，直到你只得到一个集合
• 遍历这组累积权重，直到达到 OneBillion/2

Answer 13

将 10^9 个数字，10^7 拆分到每台计算机 ~ 每台计算机上 80MB。每台计算机都会对其编号进行排序。然后计算机 1 将自己的数字与计算机 2、计算机 3 和 4 等的数字合并排序......然后计算机 1 将一半的数字写回 2、3 到 4 等。然后 1 合并对来自计算机的数字进行排序1,2,3,4，将它们写回。等等。根据计算机上 RAM 的大小，您可能不会在每一步都将所有数字都写回各个计算机，您可能可以将计算机 1 上的数字累积几个步骤，但您会进行数学运算。

哦，终于得到第 500000000 个和第 500000001 个值的平均值（但检查那里有足够的 00，我没有）。

编辑：@Roman——好吧，如果你不能相信它，即使它是真的，那么我揭示这个命题的真假是没有意义的。我的意思是，蛮力有时在比赛中胜过聪明。我花了大约 15 秒的时间来设计一个我有信心可以实现的算法，该算法可以工作，并且可以适应各种输入大小和计算机数量，并且可以根据计算机的特性和网络安排。如果您或其他任何人需要 15 分钟来设计一个更复杂的算法，我有 14 分 45 秒的优势来编写我的解决方案并开始运行。

但我坦率地承认这都是断言，我没有衡量任何东西。

Answer 14

这可以使用未按以下方式跨节点排序的数据（例如从日志文件）在节点上完成。

有 1 个父节点和 99 个子节点。子节点有两个 api 调用：

• stats()：返回最小值、最大值和计数
• compare(median_guess)：返回计数匹配值，计数小于值和计数大于值

父节点在所有子节点上调用 stats()，注意所有节点的最小值和最大值。

现在可以通过以下方式进行二分搜索：

1. 将最小值和最大值四舍五入 - 这是中值“猜测”
2. 如果大于计数大于小于计数，则将最小值设置为猜测
3. 如果大于计数小于小于计数，则将最大值设置为猜测
4. 如果计数是奇数，当最小值和最大值相等时完成
5. 如果在最大值 <= 最小值 +guess.match_count 时计数甚至完成这可以通过以下方式在使用未排序数据（例如来自日志文件）的节点上完成。

有 1 个父节点和 99 个子节点。子节点有两个 api 调用：

• stats()：返回最小值、最大值和计数
• compare(median_guess)：返回计数匹配值，计数小于值和计数大于值

父节点在所有子节点上调用 stats()，注意所有节点的最小值和最大值。

现在可以通过以下方式进行二分搜索：

1. 将最小值和最大值四舍五入 - 这是中值“猜测”
2. 如果大于计数大于小于计数，则将最小值设置为猜测
3. 如果大于计数小于小于计数，则将最大值设置为猜测
4. 如果计数是奇数，当最小值和最大值相等时完成
5. 如果在最大值 <= 最小值 + guess.match_count 时计数甚至完成

如果 stats() 和 compare() 可以使用 O(N/Mlogn/M) 排序预先计​​算，那么预先计算的内存复杂度为 O(N/M)，预计算的内存复杂度为 O(N)计算。然后你可以在恒定时间内做 compare()，所以整个事情（包括预计算）将在 O(N/MlogN/M)+O(logN) 中运行

让我知道我是否犯了错误！

Answer 15

我们先来研究一下如何在一台机器上找到n个数字的中位数：我基本上是使用分区策略。

问题：selection(n,n/2)：从最少的数字中找到第 n/2 个数字。

您选择说中间元素 k 并将数据划分为 2 个子数组。第一个包含所有元素< k，第二个包含所有元素> = k。

如果 sizeof(1st sub-array) >= n/2，你知道这个子数组包含中位数。然后，您可以丢弃第二个子阵列。解决这个问题selection(sizeof 1st sub-array,n/2)。

在其他情况下，扔掉这个第一个子数组并解决选择（第二个子数组，n / 2 - sizeof（第一个子数组））

递归执行。

时间复杂度为O(n) 预期时间。

现在如果我们有很多机器，在每次迭代中，我们必须处理一个要拆分的数组，我们将数组分配到不同的机器中。每台机器处理它们的数组块并将摘要发送回集线器控制机器，即第一个子数组的大小和第二个子数组的大小。集线器机器将汇总汇总并决定进一步处理哪个子阵列（第一个或第二个）和第二个选择参数并将其发送回每台机器。等等。

这个算法用map reduce可以很巧妙的实现吗？

它看起来怎么样？

Answer 16

这个怎么样：- 每个节点可以接受 10 亿/100 个数字。在每个节点上，可以对元素进行排序并找到中位数。求中位数的中位数。我们可以通过汇总所有节点上小于中位数中位数的数字计数，找出中位数中位数的 x%:y% 分裂。现在要求所有节点删除小于中位数中位数的元素（以 30%:70% 拆分为例）。删除 30% 的数字。10亿的70%是7亿。现在，所有删除少于 300 万个节点的节点都可以将这些额外的节点发送回主计算机。主计算机以这样的方式重新分配，现在所有节点将拥有几乎相同数量的节点（700 万）。现在问题已减少到 7 亿个数字……继续进行，直到我们有一个可以在一个 comp 上计算的更小的集合。

Answer 17

我认为史蒂夫杰索普的回答将是最快的。

如果网络数据传输大小是瓶颈，这里有另一种方法。

Divide the numbers into 100 computers (10 MB each). 
Loop until we have one element in each list     
    Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
    Send the medians to a central computer and find the median of medians. Then send the median back to each computer. 
    For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.

Answer 18

您可以使用锦标赛树方法来查找中位数。我们可以创建一个有 1000 个叶子节点的树，这样每个叶子节点都是一个数组。然后我们在不同的数组之间进行 n/2 次锦标赛。在 n/2 次锦标赛之后的根上的值就是结果。

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

Answer 19

我会这样做：

一开始，所有 100 项工作都是为了找到最高和最低的数字；每台计算机都有其查询的数据库/文件的一部分；

当找到最高和最低数字时，一台计算机读取数据，并将每个数字平均分配给其余 99 个数字；数字按等间隔分布；（一个可能从 -1 亿到 0，另一个 - 从 0 到 1 亿，等等）；

在接收号码时，这 99 台计算机中的每一台都已经对它们进行了排序；

然后，很容易找到中位数......看看每台计算机有多少个数字，将它们全部相加（有多少个数字的总和，而不是数字本身），除以2；计算在哪台计算机中是数字，在哪个索引处；

:) 瞧

PS这里似乎有很多混乱；中位数 - 是排序后的数字列表中间的数字！

Answer 20

如果数字不明显，只属于某个范围，即重复，那么我想到的一个简单的解决方案是在 99 台机器之间平均分配数字，并保持一台机器为主。现在，每台机器都会迭代其给定的数字，并将每个数字的计数存储在哈希集中。每次该数字在分配给该特定计算机的数字集中重复时，它都会更新其在哈希集中的计数。

然后所有机器将它们的哈希集返回给主机。主机组合散列集，将在散列集中找到的相同键的计数相加。例如，机器#1 的哈希集有一个条目 ("1",7)，而机器#2 的哈希集有一个条目 ("1",9)，因此主机在组合哈希集时会生成一个条目("1", 16) 等等。

哈希集合并后，只需对键进行排序，现在您可以轻松地从排序的哈希集中找到第 (n/2) 项和第 (n+2/2) 项。

如果十亿个数字是不同的，则此方法将无济于事。

Answer 21

好吧，假设您知道不同整数的数量是（比如说）40 亿，那么您可以将它们分桶到 64k 桶中，并从集群中的每台机器（100 台计算机）中获取每个桶的分布式计数。结合所有这些计数。现在，找到具有中位数的存储桶，这一次只请求目标存储桶中的 64k 个元素的存储桶。这需要对您的“集群”进行 O(1)（特别是 2）查询。:D

Answer 22

毕竟，我的一分钱价值已经被其他人提出：

在单台机器上找到中位数是 O(N)：https ://en.wikipedia.org/wiki/Selection_algorithm 。

向 100 台机器发送 N 个数字也是 O(N)。因此，为了让使用 100 台机器变得有趣，要么通信必须相对较快，要么 N 太大以至于单台机器无法处理，而 N/100 是可行的，或者我们只想考虑数学问题而不必理会数据通讯。

简而言之，我假设在合理的范围内，我们可以在不影响效率分析的情况下发送/分发数字。

然后考虑以下方法，其中一台机器被分配为某些一般处理的“主机”。这会比较快，所以“主人”也参与了每台机器执行的共同任务。

1. 每台机器接收 N/100 个数字，计算自己的中位数并将该信息发送给主机。
2. 主机编译所有不同中位数的排序列表并将其发送回每台机器，定义一个有序的桶序列（在每台机器上相同），一个用于每个中值（单值桶），一个用于每个间隔相邻的中位数。当然，对于低于最低中位数和高于最高值的值，也有低端和高端桶。
3. 每台机器计算每个桶中有多少数字，并将该信息传回给主机。
4. 主节点确定哪个桶包含中位数，有多少较低的值（总共）低于该桶，以及有多少高于该桶。
5. 如果所选桶是单值桶（中位数之一），或者所选桶仅包含 1（N 个奇数）或 2（N 个偶数）值，我们就完成了。否则，我们通过以下（明显的）修改重复上述步骤：
6. 只有所选存储桶中的数字从主服务器（重新）分配到 100 台机器，此外
7. 我们不会（在每台机器上）计算中位数，而是计算第 k 个值，其中我们考虑了从总数中丢弃了多少较高的数字，以及有多少较低的数字。从概念上讲，每台机器也有其丢弃的低/高数字的份额，并在计算集合中（概念上）包括丢弃数字（其份额）的新中位数时将其考虑在内。

时间复杂度：

1. 稍加思考就会使您相信，在每一步中，要分析的值的总数至少减少了两倍（2 将是一个相当病态的案例；您可能期望减少得更好）。由此我们得到：
2. 假设找到 O(N) 的中值（或第 k 个值）需要 c*N 时间，其中前因数 c 不会随 N​​ 变化太大，因此我们暂时可以将其视为常数，我们' 将在最多 2*c*N/100 次内得到我们的最终结果。因此，使用 100 台机器可以使我们获得 100/2 的加速因子（至少）。
3. 正如最初所说：在机器之间传递数字所涉及的时间可能会使在一台机器上简单地完成所有事情更具吸引力。但是，如果我们采用分布式方法，则所有步骤中要通信的总数不会超过 2*N（第一次 N，第二次 <=N/2，<= 一半第三，以此类推）。

Answer 23

1. 将 10 亿个数字分成 100 台机器。每台机器将有 10^7 个数字。

2. 对于机器的每个传入数字，将数字存储在频率图中，数字 -> 计数。还要在每台机器中存储最小值。

3. 在每台机器中查找中位数：从每台机器中的最小值开始，将计数相加，直到达到中位数索引。每台机器的中位数将是大约。小于和大于 5*10^6 的数字。

4. 找到所有中位数的中位数，这将小于和大于约。50*10^7 个数字，即 10 亿个数字的中位数。

现在对第二步进行一些优化：将计数存储在可变位数组中，而不是存储在频率图中。例如：假设从机器中的最小数字开始，这些是频率计数：

[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count

以上可以存储在位数组中：

[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000

请注意，每台机器总共将花费大约 10^7 位，因为每台机器只处理 10^7 个数字。10^7bits = 1.25*10^6 字节，也就是 1.25MB

因此，使用上述方法，每台机器将需要 1.25MB 的空间来计算本地中位数。中位数的中位数可以从这 100 个局部中位数中计算出来，得到 10 亿个数字的中位数。

Answer 24

我建议一种近似计算中位数的方法。:) 如果这十亿个数字是随机排序的，我想我可以随机选择十亿个数字的 1/100 或 1/10，用 100 台机器对它们进行排序，然后选择它们的中位数。或者让我们将十亿个数字分成 100 个部分，让每台机器随机选择每个部分的 1/10，计算它们的中位数。之后我们有 100 个数字，我们可以更容易地计算 100 个数字的中位数。只是一个建议，我不确定它在数学上是否正确。但我认为你可以将结果展示给数学不太好的经理。

Answer 25

史蒂夫杰索普的回答是错误的：

考虑以下四组：

{2、4、6、8、10}

{21、21、24、26、28}

{12、14、30、32、34}

{16、18、36、38、40}

中位数为 21，包含在第二组中。

四组的中位数分别为 6、24、30、36，总中位数为 27。

所以在第一个循环之后，四个组将变为：

{6、8、10}

{24、26、28}

{12、14、30}

{16、18、36}

21 已经被错误地丢弃了。

该算法只支持有两组的情况。