一道大数据题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道大数据题

一道大数据题# JobHunting - 待字闺中

q*w2014-03-08 08:03

1 楼

在glassdoor上facebook版上看的的。
Given 10,000 servers containing a Billion integers each how would you find
how to find the median?
1. 用2 heap? 全部数走这个two heap内存消耗太大吧。
2. 用类似 find median of two sorted array 方法？那每台机都要把全部数放到内存
去。每台机都是2^32*4，也就是4GB内存（假设int32）。感觉消耗太大。
3. bucket sort将所有server的所有数都放到master的bucket中去，这样只要master开
一个4G的内存就好了。而且可以并行。锁的粒度可以到bucket。
大家怎么认为？

f*e2014-03-08 08:03

2 楼

ha最新的hadoop-example.jar里有，用binary search。bucket sort也不错。

【在 q*****w 的大作中提到】

: 在glassdoor上facebook版上看的的。
: Given 10,000 servers containing a Billion integers each how would you find
: how to find the median?
: 1. 用2 heap? 全部数走这个two heap内存消耗太大吧。
: 2. 用类似 find median of two sorted array 方法？那每台机都要把全部数放到内存
: 去。每台机都是2^32*4，也就是4GB内存（假设int32）。感觉消耗太大。
: 3. bucket sort将所有server的所有数都放到master的bucket中去，这样只要master开
: 一个4G的内存就好了。而且可以并行。锁的粒度可以到bucket。
: 大家怎么认为？

q*w2014-03-08 08:03

3 楼

能说一下具体是怎么用binary search的吗？谈一下memory消耗和时间复杂度?

【在 f*****e 的大作中提到】

: ha最新的hadoop-example.jar里有，用binary search。bucket sort也不错。

f*e2014-03-08 08:03

4 楼

和quicksort差不多，可以先以0为pivot，然后算出>0和<0的数的数目，发给reducer，
reducer确定median是大于0还是小于0，然后several round like this。

【在 q*****w 的大作中提到】

: 能说一下具体是怎么用binary search的吗？谈一下memory消耗和时间复杂度?