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的想法,(他说数可能不是平均分布) : 真的不知道怎么玩了,谁懂的给讲讲.谢谢!
|
|