计算十亿个数字的中位数

这组数字的中位数

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 正在寻找(元素(499,999,999) + 元素(500,000,000))/2(如果数字被排序)。同时假设所有100台计算机都是平等的。

用我的笔记本电脑和 GigE。

我发现我的笔记本电脑可以在1.3秒内对10,000,000个 Int32进行排序。因此，粗略估计一下，10亿个数字排序需要100x1.3秒(2分10秒) ;)。

单向传输40MB 文件在吉比特以太网上的估计时间是0.32秒。这意味着来自所有计算机的排序结果将在大约32秒内返回(计算机99直到启动后30秒才获得文件)。从这里开始，不需要太长时间就可以丢弃最低的499,999,998个数字，然后加上接下来的2，再除以2。

我认为 Steve Jessop 的回答是最快的。

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

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.

这可以比投票的算法(n logn)更快地完成

- 订单统计分布式选择算法-O (n)
将问题简化为在未排序数组中查找 kth 数的原始问题。
- 计算排序直方图 O (n)
你必须假设一些关于数字范围的属性——这个范围能否适合内存？ - 外部合并排序 -O (n log n)-如上所述
基本上就是在第一次传递时对数字进行排序，然后在第二次传递时找到中间值。
如果有任何关于数字分布的信息 算法可以产生。

有关详细信息和实施情况，请参阅:
Http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

史蒂夫•杰瑟普(Steve Jessop)的回答是错误的:

审议以下四组:

{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已经被错误地抛弃了。

该算法只支持两组情况。

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 ^ 7位 = 1.25 * 10 ^ 6字节，即1.25 MB

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

这可以通过以下方式在节点上使用不跨节点排序的数据(比如日志文件)来完成。

有1个父节点和99个子节点，子节点有两个 api 调用:

• Stats () : 返回 min、 max 和 count
• 统计值匹配值、小于值的统计值和大于值的统计值

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

现在可以按以下方式进行二进制搜索:

1. 将最小四舍五入值和最大四舍五入值一分为二——这是中位数的“猜测值”
2. 如果大于计数大于小于计数，则将最小值设置为猜测
3. 如果大于计数小于小于计数，则将最大值设置为猜测
4. 当最小值和最大值相等时，如果计数是奇数完成
5. 如果 count 甚至在 max < = max + guess.match _ count 时结束 这可以通过以下方式在使用未排序数据(比如来自日志文件)的节点上完成。

有1个父节点和99个子节点，子节点有两个 api 调用:

• Stats () : 返回 min、 max 和 count
• 统计值匹配值、小于值的统计值和大于值的统计值

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

现在可以按以下方式进行二进制搜索:

1. 将最小四舍五入值和最大四舍五入值一分为二——这是中位数的“猜测值”
2. 如果大于计数大于小于计数，则将最小值设置为猜测
3. 如果大于计数小于小于计数，则将最大值设置为猜测
4. 当最小值和最大值相等时，如果计数是奇数完成
5. 如果 count 甚至在 max < = max + guess.match _ count 时结束

如果属性()和比较()可以用 O (N/Mlogn/M)排序预先计算，那么预先计算的内存复杂度为 O (N)的 O (N/M)预先计算。然后您可以在固定的时间内进行比较() ，因此整个事情(包括预计算)将在 O (N/MlogN/M) + O (logN)中运行

如果我做错了就告诉我！

我会这样做:

在开始所有的100个工作中找出最高和最低的数字; 每台计算机都有它查询的数据库/文件的一部分;

当发现最高和最低的数字时，一台计算机读取数据，并将每个数字均匀地分布到99个数字中的其余部分; 数字按相等的间隔分布; (一个可能从 -1亿到0，另一个可能从0到1亿，等等) ;

在接收数字时，99台计算机中的每一台都已经对它们进行了分类;

然后，很容易找到中位数... ... 看看每台计算机有多少个数字，把它们全部加起来(总和有多少个数字，而不是数字本身) ，除以2; 计算出哪台计算机是数字，在哪个索引;

翻译: Voilla

附注: 这里似乎有很多混淆; 中位数-是数字排序列表中间的数字！

中位数和第99百分位数等顺序统计量的 估计可以通过 消化或 Q 消化算法有效地进行分布。

使用任一种算法，每个节点都生成一个摘要，该摘要表示本地存储的值的分布情况。摘要在单个节点上收集，合并(有效地汇总分布) ，然后可以查找中位数或任何其他百分位数。

弹性搜索和 BigQuery(根据 QUANTILES 函数的描述)使用这种方法。

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

在这种情况下，你可以找到 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。低将开始与计数5和最高3和高与分钟8和计数5。

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

• 旧低(5)
• 低(5) : 4,4,4,4,4，最高4
• 中(3) : 5,6,6
• 高(2) : 7,7，分钟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

你需要最小和最大，因为边缘情况(例如，如果中位数是平均之间的最大旧低和下一个元素)。

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

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

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

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

我建议一种近似计算中位数的方法。:)如果这10亿个数字是随机排列的，我想我可以从10亿个数字中随机选出1/100或1/10，然后用100台机器排序，然后选出它们的中位数。或者让我们把10亿个数字分成100个部分，让每台机器随机挑选每个部分的1/10，计算它们的中位数。之后，我们有100个数字，我们可以计算100个数字的中值更容易。只是个建议，我不确定数学上是否正确。但我觉得你可以把结果给一个数学不太好的经理看。

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

一旦有了排序列表，选择中间值就变得很简单了。实际上，您不需要构造已排序的列表，只需查看桶即可。

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

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


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


// 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亿(10⁹)数字的文本文件并像这样使用 time运行

time ./median < billion

在我的机器上产生一个运行时间1m49.293. 大多数运行时间可能也是磁盘 IO。

一个更简单的方法是有加权数字。

• 在计算机之间分割大的集合
• 对每一组进行排序
• 迭代小集合，并计算重复元素的权重
• 将每2个集合合并为1(每个已经排序)更新权重
• 继续合并集，直到只得到一个集
• 循环遍历这个集合，积累权重，直到达到10亿/2

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

然后，所有机器将它们的哈希集返回给主机。主机组合了哈希集，将在哈希集中找到的相同密钥的计数相加。例如，机器 # 1的散列集的条目为(“1”，7) ，而机器 # 2的散列集的条目为(“1”，9) ，因此主机在梳理散列集时会生成一个条目为(“1”，16) ，依此类推。

一旦合并了哈希集，那么只需对键进行排序，现在您就可以很容易地从排序的哈希集中找到(n/2)第二个项和(n + 2/2)第三个项。

如果十亿个数字是不同的，那么这种方法就不会有好处。

对于一台现代计算机来说，10亿实际上是一个相当枯燥的任务。我们现在讨论的是4GB 的4字节整数... 4GB... 这是一些智能手机的内存。

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

所以这在我的机器上完成不到两分钟(1分43秒，其中0分10秒生成随机数)使用一个核心，它甚至做了一个完整的排序。没什么特别的。

对于更大的数字集来说，这无疑是一项有趣的任务。我只是想说明一点: 10亿美元是微不足道的。因此，在你开始将复杂的解决方案用于极其简单的任务之前，请三思而后行;)

那么，假设您知道不同整数的数量是(比如)40亿，那么您可以将它们装入64k 存储桶中，并从集群中的每台机器(100台计算机)获得每个存储桶的分布式计数。把这些数字合起来。现在，找到具有中间值的 bucket，并且这一次只要求存放在目标 bucket 中的64k 元素的 bucket。这需要对您的“集群”进行 O (1)(特别是2)查询。校对: D

我的价值，在所有这一切已经提出了由别人:

在一台机器上查找中间值是 O (N) : https://en.wikipedia.org/wiki/Selection_algorithm。

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

为了简短起见，我假设在合理的范围内，我们可以在不影响效率分析的情况下发送/分发数据。

然后考虑下面的方法，其中一台机器被指定为某些常规处理的“主机”。这将相对较快，因此“主人”也参与每台机器执行的常见任务。

1. 每台机器接收 N/100个数字，计算自己的中位数，并将信息发送给主机。
2. 主机编译所有不同中位数的排序列表，并将其发送回每台机器，定义一个有序的桶序列(在每台机器上相同) ，每个中位数值一个(一个单值桶) ，相邻中位数之间的每个间隔一个。当然，也有低端和高端的桶的价值低于最低中位数和高于最高。
3. 每台机器计算每个桶中有多少个数字，并将这些信息反馈给主机。
4. 主机确定哪个 bucket 包含中位数，有多少个较低的值(总共)低于这个 bucket，以及有多少个高于这个 bucket。
5. 如果选中的 bucket 是一个单值 bucket (中值之一) ，或者选中的 bucket 只包含1(N 奇数)或2(N 偶数)值，那么我们就完成了。否则，我们将重复上述步骤，并进行以下(显而易见的)修改:
6. 只有来自选定桶的数字被(重新)从主机分配到100台机器，而且
7. 我们不会计算(在每台机器上)中位数，而是 k-th 值，在这里我们要考虑有多少较高的数字从总数中被丢弃，以及有多少较低的数字。从概念上讲，每台机器也有其丢弃的高低数字的份额，并且在计算集合中包含(其份额)丢弃数字的新中值时考虑到这一点。

时间复杂度:

1. 稍微思考一下就会让你相信，每一步要分析的值总数至少减少了两个因子(2是一个相当病态的例子; 你可能期望得到更好的减少)。从这里我们得到:
2. 假设找到中值(或 k-th 值) ，即 O (N) ，需要 c * N 时间，其中前因子 c 与 N 的变化不会太大，因此我们可以把它当作一个常数，我们最多得到2 * c * N/100时间的最终结果。因此，使用100台机器使我们的加速系数至少达到100/2。
3. 正如最初提到的: 在机器之间传递数字所花费的时间可能会使在一台机器上简单地完成所有事情变得更有吸引力。但是，如果我们采用分布式方法，那么在所有步骤中一起传递的总数不会超过2 * N (第一次为 N，第二次为 < = N/2，第三次为 < = N/2的一半，依此类推)。