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

用户1410343

发布于 2019-12-26 14:08:14

1.8K0

发布于 2019-12-26 14:08:14

文章被收录于专栏：about云about云

问题导读 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循环这里写代码，只表示思路：

for (Integer key : map1.keySet()) {
      for (Integer key : map2.keySet()) {
        if(map1.get(value)==map2.get(value))
         print("共同好友"+value)
   }

代码优化上面只是实现了，对于两个集合，如果有的长，有的短，我们将小集合放到外层循环，这样可以效率更高。如果map2是小集合我们可以采用下面方式

for (Integer key : map2keySet()) {
for (Integer key : map1.keySet()) {
if(map1.get(value)==map2.get(value))
print("共同好友"+value)
}

大数据实现上面我们其实讲的是该如何实现，以及传统该如何实现，那么我们使用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的共同好友。