a*******o 发帖数: 67 | 1 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
BILLION数据,要怎么办?
我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
重新PARTITION
然后面试官貌似不满意
然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
要求太大了。
这题还有什么其他好的方法吗? |
s**x 发帖数: 7506 | 2 分段counting ?
比如每百万个分组统计,最后对要的组再细分。 |
c*****t 发帖数: 48 | 3 这题要考虑分布式那块的点吗?
可以先在每台机器本地排序取前1B的数据,如果不足1B就全取,记录下这1B数据的mean
然后再用quicksort,pivot的值可以取所有mean值里的mean
然后一直下去。。直到最后总共剩下1B数据
瞎想的
TOP1
HEAP
【在 a*******o 的大作中提到】 : 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1 : BILLION数据,要怎么办? : 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个 : 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数 : 重新PARTITION : 然后面试官貌似不满意 : 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞 : 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP : 要求太大了。 : 这题还有什么其他好的方法吗?
|
z****s 发帖数: 409 | 4 一共有多少机器?每台大约存多少?每台内存多大?相互传输速率多少?
毛都不知道想个屌。 |
l*******g 发帖数: 82 | 5 我觉得,LZ是不是可以考虑Divide and conque排序,比如MergeSort,或者用类似
MapReduce的方式来处理。
浅见,不对不要见怪! |
s*w 发帖数: 729 | 6 参见 M 马 N 道,赛马找前 K 的问题
TOP1
HEAP
【在 a*******o 的大作中提到】 : 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1 : BILLION数据,要怎么办? : 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个 : 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数 : 重新PARTITION : 然后面试官貌似不满意 : 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞 : 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP : 要求太大了。 : 这题还有什么其他好的方法吗?
|
b****t 发帖数: 112 | 7 基本步骤无非是sort(per machine)和merge(external merge).
1) Sort
for each machine:
sort top 1 Billion
2) Merge
merge 1 * 10 Billion into 1 Billion
优化设计:并行处理。设立中央控制器。
效果:a. 不必每个机器都占用1 billion内存 b.并行处理, 节约时间
Assume there is one independent server as the sorting controller.
The controller does the external file merge.
On each machine:
while (true)
{
communicate with controller:
{
get current low boundary
upload sorted value to the controller to merge
empty local cached
}
sort
{
Sort for 5 minutes or preset intervals, only keep the value above the
latest low boundary
}
if done file scan, exit
}
TOP1
HEAP
【在 a*******o 的大作中提到】 : 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1 : BILLION数据,要怎么办? : 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个 : 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数 : 重新PARTITION : 然后面试官貌似不满意 : 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞 : 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP : 要求太大了。 : 这题还有什么其他好的方法吗?
|
c***0 发帖数: 449 | 8 可以分配k个heap给100billon的数,使得每个heap的容量足以放在内存中。
heap的特性是,第m个的最大数小于m+1的最小数,这样遍历一遍所有数,有溢出的heap
就向上溢出给下一个heap。
最后统计所需要的1billon的heap总数就可以了 |
p****U 发帖数: 109 | 9 对每部机子bucket sort 然后合并sort的结果。100 billion 数据 如果都是int 的话
大约400g吧。 算算几部机器handle得到 |
w*******e 发帖数: 395 | 10 假设每个数据是4B的int,100B需要400GB的存储,假设一台server有8GB可用的memory
,需要50台机器,另外有一台机器做controller
每台机器用bucket sorting,分成100个bucket,每台机器把每个bucket内数据的个数
报给controller,controller可以决定那个1B数据的边界会落在哪个bucket内
然后每台机器在相应的bucket内继续划分100个bucket,重复上一步,直到找到所有1B
数据为止。
TOP1
HEAP
【在 a*******o 的大作中提到】 : 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1 : BILLION数据,要怎么办? : 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个 : 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数 : 重新PARTITION : 然后面试官貌似不满意 : 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞 : 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP : 要求太大了。 : 这题还有什么其他好的方法吗?
|
z****e 发帖数: 54598 | 11 re这个,我也是这么想的
不过我一般不叫这个controller,而叫master
memory
1B
【在 w*******e 的大作中提到】 : 假设每个数据是4B的int,100B需要400GB的存储,假设一台server有8GB可用的memory : ,需要50台机器,另外有一台机器做controller : 每台机器用bucket sorting,分成100个bucket,每台机器把每个bucket内数据的个数 : 报给controller,controller可以决定那个1B数据的边界会落在哪个bucket内 : 然后每台机器在相应的bucket内继续划分100个bucket,重复上一步,直到找到所有1B : 数据为止。 : : TOP1 : HEAP
|