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 |
