c*****0
发帖数: 171 | 1 k sorted list, with one list with n integers. Sort all the lists.
单机版，比较简单，maintain一个heap就行了。kn*lg(k)
extention, 给m个机器，请充分利用，加快sort的速度。
我大概从几个方面来解，都被否决了。
1，每个slave machine， 分配一个list，然后再主机merge，（他说没有加快时间）
2，我想两个两个merge，（他还是不够满意）
3，我想利用bucket的想法，（他说数可能不是平均分布）
真的不知道怎么玩了，谁懂的给讲讲.谢谢! | g*********s
发帖数: 1782 | 2
yes, it doesn't help at all.
this should be right.
【在 c*****0 的大作中提到】
: k sorted list, with one list with n integers. Sort all the lists.
: 单机版，比较简单，maintain一个heap就行了。kn*lg(k)
: extention, 给m个机器，请充分利用，加快sort的速度。
: 我大概从几个方面来解，都被否决了。
: 1，每个slave machine， 分配一个list，然后再主机merge，（他说没有加快时间）
: 2，我想两个两个merge，（他还是不够满意）
: 3，我想利用bucket的想法，（他说数可能不是平均分布）
: 真的不知道怎么玩了，谁懂的给讲讲.谢谢!
| c*****0
发帖数: 171 | 3 第二个时间复杂度，我分析的不好。
感觉应该是 小于 k*n*lg(k), 大于 k*n. 请指点一二。
【在 g*********s 的大作中提到】
:
: yes, it doesn't help at all.
: this should be right.
| g*********s
发帖数: 1782 | 4 merge in parallel. draw a picture and u will see the total complexity is
x + x/2 + x/4 ... = 2x, where x = k*n.
【在 c*****0 的大作中提到】
: 第二个时间复杂度，我分析的不好。
: 感觉应该是 小于 k*n*lg(k), 大于 k*n. 请指点一二。
| p******r
发帖数: 2999 | 5 ...
x equals the total length of previous two lists
it's not constant k*n
【在 g*********s 的大作中提到】
: merge in parallel. draw a picture and u will see the total complexity is
: x + x/2 + x/4 ... = 2x, where x = k*n.
| g*********s
发帖数: 1782 | 6 k lists, each n long. total x=k*n ah.
【在 p******r 的大作中提到】
: ...
: x equals the total length of previous two lists
: it's not constant k*n
| c*****0
发帖数: 171 | 7 Thanks, that should be correct for k machines.
By the way, if the two way-merging method is used in one machine, then the
total complexity should be (2^k) * n, is that right?
【在 g*********s 的大作中提到】
: merge in parallel. draw a picture and u will see the total complexity is
: x + x/2 + x/4 ... = 2x, where x = k*n.
| l*****a
发帖数: 559 | 8 i think it is k*n*lg(n).
because there are lg(n) levels.
each level the complexity is k*n in total.
【在 c*****0 的大作中提到】
: 第二个时间复杂度，我分析的不好。
: 感觉应该是 小于 k*n*lg(k), 大于 k*n. 请指点一二。
| e******a
发帖数: 176 | 9 For multi machines, the best you can achieve is 2nlogk.
suppose k=8, you have 4 machines
level1, merge two lists on each machine, runtime 2*n
level2, now you reduced 8 lists into 4. If you continue the above scheme,
you can only use two machines. How do you use 4 machines? Well, for each
pair, take one list's median, binary search in the other list.
So you have list A: [A1, ..., An, A_n+1, ... A_2n], and list B [B1, ..., Bk,
B_k+1, ..., B_2n]. Now you use two machines to merge two sublists, and
concatenate the results. Again, runtime is 2*n
So you achieve in total 2n*logk. | m*******d
发帖数: 40 | 10 面试题：
http://jobguideweb.com/it-jobs/google.html
【在 c*****0 的大作中提到】
: k sorted list, with one list with n integers. Sort all the lists.
: 单机版，比较简单，maintain一个heap就行了。kn*lg(k)
: extention, 给m个机器，请充分利用，加快sort的速度。
: 我大概从几个方面来解，都被否决了。
: 1，每个slave machine， 分配一个list，然后再主机merge，（他说没有加快时间）
: 2，我想两个两个merge，（他还是不够满意）
: 3，我想利用bucket的想法，（他说数可能不是平均分布）
: 真的不知道怎么玩了，谁懂的给讲讲.谢谢!
| u******e
发帖数: 758 | 11 可不可以这样，当k>m时，两个两个merge
当k<＝m时，把每个list等分成m段，每台机器上分别对每个list的第i段进行一次k mer
ge，完成后再按i序对相邻的机器进行conjunction以正确方式插入叠盖部分。T＝O(k *
n/m * logk)+O(Conjunction)
conjunction的方法是（assume i+2的最小节点不会比i的最大节点还小）：
当i>1时，记录下merge时首元素最大的node，并将该node之前的所有node从后往前merg
e回 i-1 list的尾部。
conjunction的worst case很难看，是(k-1)*n/m.但对随机生成的均衡队列，average可
以认为是小数。且conjunction可以并发进行，所以
O(conjunction)可以忽略。
总的T=O(k*n/m*logk);
这种方法适合起始当k>>m使得通过两两merge生成的k'<=m个队列时相对均衡或给的每个
原list就相对较均衡的情况下。这样conjunction的代价很小。
如果k<=m，且分布不均匀
依然是进行分段的思路：
1 把list[0]等分成m段
2 当i>0时对第i台机子在每个list里二分找到该list在该机器的段起点（大于list[0]在
对应段起点的最小值）
3 每台机子不等长k merge，每个list的结束标志是它的值大于list[0]在该机器的段终
点。
4 把每台机器结果串起来就行。
【在 c*****0 的大作中提到】
: k sorted list, with one list with n integers. Sort all the lists.
: 单机版，比较简单，maintain一个heap就行了。kn*lg(k)
: extention, 给m个机器，请充分利用，加快sort的速度。
: 我大概从几个方面来解，都被否决了。
: 1，每个slave machine， 分配一个list，然后再主机merge，（他说没有加快时间）
: 2，我想两个两个merge，（他还是不够满意）
: 3，我想利用bucket的想法，（他说数可能不是平均分布）
: 真的不知道怎么玩了，谁懂的给讲讲.谢谢!
|
|
