计算十亿数字的中位数

如果您有十亿个数字和一百台计算机,那么找到这些数字的中位数的最佳方法是什么？

我的一个解决方案是:

在计算机之间平均分割集合.

排序他们.

找到每组的中位数.

对中位数进行排序.

从最低到最高中位数一次合并两组.

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

啊,我的大脑刚刚开始装备,我现在有一个明智的建议.如果这是一次采访可能为时已晚,但没关系:

机器1应称为"控制机器",为了参数,它以所有数据开始,并以相同的包裹发送给其他99台机器,否则数据在机器之间均匀分布,并且它将1/99的数据发送给其他每个数据.分区不必相等,只需关闭即可.

每台其他机器对其数据进行排序,并以有利于首先找到较低值的方式进行排序.因此,例如快速排序,总是先排序分区的下半部分[*].它会尽快将其数据以递增的顺序写回控制机器(使用异步IO以便继续排序,并且可能与Nagle一起使用:实验一下).

控制机器在数据到达时执行99向合并,但丢弃合并的数据,只计算它看到的值的数量.它将中位数计算为十亿分之一和十亿分之一加上oneth值的平均值.

这遭受了"牛群中最慢的"问题.在分拣机发送了小于中位数的每个值之前,算法无法完成.在这个数据包中,有一个这样的价值非常高的合理机会.因此,一旦数据的初始分区完成,估计的运行时间是排序1/99数据并将其发送回控制计算机的时间的组合,以及控制读取1/2数据的时间."组合"介于这些时间的最大值和总和之间,可能接近最大值.

我的直觉是,通过网络发送数据比分类更快(更不用说只选择中位数),它需要一个非常快速的网络.如果可以假定网络是瞬时的,那么可能是一个更好的前景,例如,如果你有100个内核可以同等访问包含数据的RAM.

由于网络I/O很可能受限,因此可能会出现一些技巧,至少对于返回控制机器的数据而言.例如,代替发送"1,2,3,... 100",也许分拣机器可以发送意味着"100个值小于101"的消息.然后,控制机器可以执行修改后的合并,其中它找到所有那些顶级值的最小值,然后告诉所有分拣机它是什么,以便它们可以(a)告诉控制机器如何许多值在该值之下"计数",并且(b)从该点继续发送其排序数据.

更一般地说,可能有一个聪明的挑战 - 响应猜测游戏,控制机器可以与99分拣机一起玩.

这涉及到机器之间的往返,这是我简单的第一个版本避免的.我真的不知道如何盲目估计他们的相对表现,而且由于权衡是复杂的,我想有更好的解决方案,而不是我想到的任何事情,假设这是一个真正的问题.

[*]可用堆栈许可 - 如果您没有O(N)额外空间,则可以选择首先执行哪个部分.但是,如果你有足够的额外空间,你可以选择,如果你没有足够的空间,你至少可以使用你所拥有的削减一些角落,通过先做几个分区的小部分.

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

我不想在这里成为逆向,但我不相信排序是必需的,我认为任何涉及排序十亿/ 100数字的算法都会变慢.我们在一台计算机上考虑算法.

1)从十亿中随机选择1000个值,并使用它们来了解数字的分布,尤其是范围.

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

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

4)通过检查该桶中的值来查找实际中值.如果您愿意,可以在这里使用排序,因为您只排序10,000个数字.如果该存储桶中的值的数量很大,则可以再次使用此算法,直到您有足够小的数字进行排序.

这种方法通过在计算机之间划分值来平凡地并行化.每台计算机将每个存储桶中的总计报告给执行步骤3的"控制"计算机.对于步骤4,每台计算机将相关存储桶中的(已排序)值发送到控制计算机(您也可以同时执行这两种算法,但它可能不值得).

总过程为O(n),因为如果桶的数量足够大,则步骤3和4都是微不足道的.

对于现代计算机而言,十亿对于任务来说实际上是一件无聊的事 我们在这里谈论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

所以这在我的机器上在不到两分钟的时间内完成(1:43,其中0:10是生成随机数),使用一个核心,它甚至做了一个完整的排序.没什么好看的.

对于更大的数字集,这肯定是一项有趣的任务.我只想在此提出一点:10亿是花生.所以在你开始在简单的任务中抛出复杂的解决方案之前要三思而后行;)

的估计顺序统计等中位数和第99百分位数的可与等的算法来有效地分布叔消化或Q-消化.

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

这种方法所使用的elasticsearch和,据推测,大量查询(由分位数功能的描述去).

这组数字的中位数

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.所以一个粗略的估计是十亿数字排序需要100 x 1.3秒(2分10秒);).

在千兆位以太网上估计40MB文件的单向文件传输是0.32秒.这意味着所有计算机的排序结果将在大约32秒内返回(计算机99在启动后30秒内未获取其文件).从那里它不应该花很长时间丢弃最低的499,999,998数字,添加下一个2并除以2.

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

有了排序列表后，选择中位数就很简单了。实际上，您不需要构造排序列表，而只需查看存储桶即可。

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

#include 
#include 

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;
}

time ./median < billion