算法系列讲解之：社交网络之共同好友模型讲解

问题导读

1.寻找共同好友，该如何转换为程序逻辑？
2.寻找共同好友的思路是什么？
3.如何通过MapReduce实现寻找共同好友？


我们知道社交网络经常会看到共同好友，共同好友目前资料也非常的多，也有代码实现，可以依然很多老铁不知道它是怎么实现的，或则说比较模糊。这里给大家介绍下找共同好友的算法。

社交共同好友图

为什么感觉难度大：我们看下图：




上面图示展示了好友之间的关系，那么我们的共同好友，该如何找到。面对如此复杂的图谱，我们只要认真分析，其实可以捋顺其中关系。

逻辑推理、解析
既然是共同好友，那么肯定是两个人，才算共同好友。也就是说我们面对如此复杂的图谱，我们只要以两个人为研究对象，然后找到两个人的共同好友，其它依次类推，找到更多的两个人的共同好友。

那么这个共同好友，我们该如何实现。

将业务需求转换为程序

两个人的共同好友，我们需要转换为我们的程序，这也是我们程序员的价值，也是我们跟非编程人员的价值区别。那么两个人我们可以转换为两个用户，这两个用户，我们可以通过用户id来表示。相信这个大家都能理解。

两个人我们使用两个用户id，那么这两个用户其实是有非常多好友的。既然有非常多的好友，那么这些好友其实也是用户，所以好友也可以使用用户id来表示。
那么我们可以这样表示了

逻辑图：

下面我们看到两个用户，互为好友，他们分别都有自己的好友。对于下面逻辑图，我们自己就可以找到好友。但是如果想通过程序该如何实现。



程序图
这里我们把他转换为实现图，或则程序图


我们将上面的逻辑关系，转换为底层的关系。

程序图转换为程序
上面图已经有了，可是我们该如何转换为程序结构，所以这里我们需要进一步转换为程序。该如何通过程序找到他们的共同好友。

我们人工可以找到他们的共同好友，那么程序该如何找到这些数据的共同好友。

数据在程序中，是需要装起来的。那么该如何装下这些数据，这时候我们就需要想到数据结构了。这时候就涉及到了我们的专业知识，都有哪些数据结构。比如有数组，list，map，树等，其实我们就用比较简单的数据结构即可。我们使用map。这时候就有key和value。

key其实就是我们的用户UserID1,那么他的朋友即为value list，也就是后面一系列的：UserID2，UserID3，UserID。。，UserIDN
用户UserID2，同样也是UserID1，UserID3，UserID。。，UserIDN等

这样我们剩下的该如何做了那？操作两个map，假设UserID1对应的为map1，UserID2对应map2找到他们的共同好友。该如何找到共同好友？
遍历两个map呀.我们通过两个for循环

这里写代码，只表示思路：

[mw_shl_code=java,true] for (Integer key : map1.keySet()) {
       for (Integer key : map2.keySet()) {
         if(map1.get(value)==map2.get(value))
          print("共同好友"+value)
    }[/mw_shl_code]

代码优化
上面只是实现了，对于两个集合，如果有的长，有的短，我们将小集合放到外层循环，这样可以效率更高。
如果map2是小集合我们可以采用下面方式
[mw_shl_code=java,true] for (Integer key : map2keySet()) {
for (Integer key : map1.keySet()) {
if(map1.get(value)==map2.get(value))
print("共同好友"+value)
}[/mw_shl_code]

大数据实现
上面我们其实讲的是该如何实现，以及传统该如何实现，那么我们使用MapReduce或则spark该如何实现？
这个其实在《数据算法  Hadoop Spark大数据处理技巧》中是有的，这里给大家贴出来，然后对这里面比较难以理解的做个说明。


对于map函数，其实是在分割的数据中，通过map找到用户的朋友列表，这里它把用户视为key，用户朋友视为value，但是这个value是为list的。

而且这里面比较难以理解的，其实也是重点，那就是在找到用户id视为key，用户列表视为value后，在输出到reduce时候，将key和value重新组合为key，然后将value视为value。本质其实如下
key value重新定义key2,value重新定义value2，也就是上面的（key2,value2）。那么reduce这时候接受到的数据格式为：
（key value，value）

那么为何这样做，我这里做一个简单的说明，而且下面遇到的时候，在给大家讲解。



我们看到下面每一个map重新定义后的（key value，value）输出内容，我们或许可能恍然大悟，key定义为两个userid其实是为了方便找到共同好友。也就是key包含了userid和它的value，也就是包含了自己和他的其中一个朋友，是为了方便找到他们的共同好友。但是我们看到其实map的作用只是组合了本人和它的好友。何谈共同好友？这是我们在reduce里面会更加明显的让我们看到共同好友。

如果说map只是简单的组合了自己的好友。我们继续往下看reduce。




我们看下面reduce讲userid为100和200之间找到共同好友。对于任何一个map来讲，它的作用其实就是找到自己的一个朋友，和他的朋友列表。对于另外一个朋友，其实也是一样，找到他的朋友和他的朋友列表。
这样比较绕口，这里我们看下面具体例子。比如还是100和200为例子。
原始数据是这样的
100和他的朋友，200和他的朋友。
进入map后，处理为：
100和200，然后100的朋友列表
另外被分割的数据，被map同样也处理格式为
100和200，然后200的朋友列表

这样在reduce的时候，就可以通过我们传统的思路比较，找到100和200的共同好友。







我们明白了map的作用其实就是先配对，reduce其实就是找到配对朋友的共同好友。

上面其实我们明白了MapReduce，spark其实在这个思路下，其实就是API的应用。这里只是简单贴下思路。


当然如果明白了思路，其实我们也可以通过Flink来实现。如果你也对大数据及相关算法感兴趣，可以加微信w3aboutyun。

最新经典文章，欢迎关注公众号

------------------end-------------------------

以上内容是为了培养VIP群喜欢读书老铁的习惯，如果你也喜欢读书，欢迎加入about云读书会。

经典问题