问答

当前位置
  • 首页
  • 问答
  • number of islands面试中要求用union find在mapReduce上做,讨论边界条件

number of islands面试中要求用union find在mapReduce上做,讨论边界条件

  • Ta: 刘助教

用union find做的number of islands. 在followup的问题中,面试官要求讨论当矩阵太大一个机器放不下,需要多个机器process的情形。要求写出部分code,讨论边界处的算法(不需要真的用mapreduce写,只需要讨论边界)。

比如:
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
当矩阵被拆成很多块放到很多机器上分别计算number of islands以后,需要讨论union find如何判断最终岛屿数量。

感谢。

3 个回复

2017-03-22 马同学

就是做分治,先把矩阵切割,切割后分别在不同的机器上做原来的问题,最后合并,合并的时候处理原来分割处的点即可。


2019-03-21 p同学

我覺得這樣的回答是不切實際的。所有的問題都說分治就好了、重點是 merge 該怎麼merge. 應該要再清楚明瞭一些


2019-09-10 Jean

分治就是简单的split或者partition,可以按照行分,列分或者block分。将分好对块叫做一个block。
merge的时候,用两个block构建一个新的union find, count计数先加起来。然后对相邻边界进行union操作。 假设两个边界点为edge1, edge2,
if(isAdjacent(edge1, edge2)) {
int root1 = find(edge1);
int root2 = find(edge2);
if(root1 != root2) {
fathers[root1] = root2;
cnt--;
}
}
如果fathers矩阵过大,则在reduce(merge)之前,对每一个map server的union find instance中的fathers矩阵,去掉非边界的,只保留边界值,这样可以有效减少内存消耗,在union的时候也不容易导致fathers array过大。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1