w****f 发帖数: 684 | 1 有一个文件含1000000000个(user, login-timing,...)
要求登陆时间前1000名,以及median。请问那种算法最好? |
s******n 发帖数: 3946 | 2 根据userid hash分配到k台机器。每台机器上统计,排序。
然后k-way合并(用heap),得到总排名的前1000和median |
w****f 发帖数: 684 | 3 谢谢,swan。
这种算法好像对占memory较多,有无更好的算法? |
z*********8 发帖数: 2070 | 4 求前1000个用 maxheap就行了, 求median就只能那么做
【在 w****f 的大作中提到】 : 谢谢,swan。 : 这种算法好像对占memory较多,有无更好的算法?
|
s******n 发帖数: 3946 | 5 求median必须要排序,可以用external sort |
d****n 发帖数: 1637 | 6 +1
好像1 billion 的数据不是都load 到memory.
是不是要把user 放进bst 或者hash里面,只保留最早时间?
1 billion user, 多少unique names?
【在 z*********8 的大作中提到】 : 求前1000个用 maxheap就行了, 求median就只能那么做
|
w****f 发帖数: 684 | 7 It's 1 billion user, and only 1 million unique userid.
"求median必须要排序,可以用external sort". What's external sort?
Does the below work?
1.) take first 1001, use 501th as the initial median values of login-
timing.
2.) read next one and shift the median to fit the new one.
3.) repeat step 2 till the end.
(But this one only give the values of timing, not the associated useid) |
w****x 发帖数: 2483 | 8 1. 把文件切成2^n个大小相同的小文件, 每两个可以装入内存
2. 两两载入内存, 对每个pair做median merge, 2 个 file merge成一个大小相同的
file
3. 如此merge下去, 直到所有的file浓缩成一个file, 取这个file的median, 不过这题
因该允许取得非精确median |