l*****n
发帖数: 246 | 1 1PB 数据排序，数值范围2^64, 每台机器16G内存，10T数据，普通硬盘，写算法，估算
时间 |
j**********3
发帖数: 3211 | |
w*****t
发帖数: 485 | 3 分块, 然后归并排序吧.
nlogn.
"1PB数据排序", 后面还有个"10T数据",这个啥意思? |
b******e
发帖数: 52 | |
l*****n
发帖数: 246 | 5 分块，然后归并排序会不会太慢？
10T数据是指硬盘空间是10T
总共1PB也就是需要100台机器
【在 w*****t 的大作中提到】
: 分块, 然后归并排序吧.
: nlogn.
: "1PB数据排序", 后面还有个"10T数据",这个啥意思?
|
l*****n
发帖数: 246 | 6 bucket sort行不通，你看题目中数字范围是2^64
任何一个内存都放不下这个range的数字
【在 b******e 的大作中提到】
: just bucket sort.
|
l*****n
发帖数: 246 | 7 如果用 Hadoop 来 MapReduce 怎么做这题？ |
w*****t
发帖数: 485 | 8 这样的话就是并行处理了， 每台机器先将本机的数据排好序，最后再做多机的两两归
并。
如果预先知道重复元素比较多的话，可以考虑用{int64 value:int64 count}来节省内
存占用。
【在 l*****n 的大作中提到】
: 分块，然后归并排序会不会太慢？
: 10T数据是指硬盘空间是10T
: 总共1PB也就是需要100台机器
|
w*****d
发帖数: 105 | |
f******y
发帖数: 54 | 10 "如果用 Hadoop 来 MapReduce 怎么做这题？"
这个就太简单了，map生产以这个些数值为key的pair，
到reduce，其实啥都不做，直接输出这个值。当然有没有重复value要注意下。
因为“sort”过程被shuffle过程完成了（hadoop默认内存是quick sort，然后加上多
轮merge sort）。
你只要定义什么做key就行了。 |
