专栏首页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的共同好友。

我们明白了map的作用其实就是先配对,reduce其实就是找到配对朋友的共同好友。 上面其实我们明白了MapReduce,spark其实在这个思路下,其实就是API的应用。这里只是简单贴下思路。

本文分享自微信公众号 - About云(wwwaboutyuncom),作者:pig2

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MapReduce执行过程分析【问题】

    这个是个问题贴,由about云会员提问。会员答疑。提问和回答都比较有水平,分享出来。

    用户1410343
  • 区块链开发语言之go语言学习线路指导

    问题导读 1.为什么学习go语言? 2.你认为该如何入门go语言? 3.你认为go语言需要哪些学习过程?

    用户1410343
  • spark入门(2.0.1版本):概述,下载,编译,运行环境及实例运行

    问题导读 1.spark下载方式有哪些? 2.spark可以运行在哪些系统? 3.spark支持哪些语言? 4.如何运行spark各种语言版本例子? ...

    用户1410343
  • JSON.stringify驯服循环引用的对象

    前端黑板报
  • Vugu:Go + WebAssembly的现代UI库

    Vugu 是一个 Go语言开发库,可以很容易地使用 Go 语言编写 Web 用户界面。

    mojocn
  • 业务逻辑漏洞探索之暴力破解

    最近斗哥在整理一些业务逻辑漏洞,突然发现好多问题,所以决心和大家一起探讨探讨,今天先从暴力破解开始。

    漏斗社区
  • Go1.8.4和Go1.9.1版本发布

    文 | Chris Broadfoot 你们好gophers, 最近爆出的两则安全问题,为了修复它,我们刚刚发布了Go 1.8.4和Go 1.9.1两个版本。 ...

    李海彬
  • Memcached 使用详解

    以 PHP 为例使用 Memcached。 系统类 $m=new Memcached(); $m->addServer('memcached',11211);...

    康怀帅
  • 当AI开始“踢脏球”,你还敢信任强化学习吗?

    足球机器人排成一排向球门发起射击,但守门员却并没有准备防守,而是一屁股倒在地上开始胡乱摆动起了双腿。然后,前锋跳了一段十分令人困惑的舞蹈,跺跺脚,挥挥手,啪叽一...

    脑极体
  • 体验 MySQL 8.0 JSON聚合函数

    MySQL 最近的动作很快,已经计划推出 8.0 版本,会新增很多新特性 在 5.7 中,JSON 已经被正式支持,但在 SQL 中对 JSON 的处理能力较弱...

    dys

扫码关注云+社区

领取腾讯云代金券