无忧技术网
无忧技术网 - RSS订阅 

六度空间理论---腾讯2012年4月笔试题


作者:[佚名] - 发布:2015-1-27 11:43:56 - 来源:无忧技术网

  题目大意是这样的:

  1.平均每个QQ用户有25个好友,如何计算两个用户之间是不是六度可达。

  2.如果一台计算机每秒可以进行1000次查询,问一天能计算出一个用户最多几度好友,如何改变设计,使度数提高。

  思 路:

  首先说一下什么叫六度空间理论,根据百度百科的定义:

  该理论源于一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论或小世界理论等。

  理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。

  这道题,首先我们需要先构建一个六度空间,这样只要我们输入两个QQ号,就会搜索出两个用户之间的是否存在六度关系。假设我们已经建好了这样一个六度空间。

  不妨设输入的两个QQ号用户分别为A,B。每个人的QQ号为一个unsigned int型数据。每次都以最坏情况为例。

  那么获取A的25个好友并对比其中是否有B,需要1次查找和25次对比。

  获取A25个好友的25个好友并对比其中是否有B,需要25次查找,和25^2次对比。

  同理A的六度好友大约有(忽略重负)25×25×25×25×25×25=244140625≈244×4MB≈1GB的数据。需要进行250M次的查找和1G的对比,这是一个相当恐怖的数据。

  
该如何优化了?

  假设A,B六度可达不妨设A->C->D->E->F->G->B为A到B的路劲。不难看出若A,B六度可达,则A的三度好友,与B的三度好友,应该有重叠。即从两个方向查找:
A->C->D->E1
B->G->F->E2

  只要E1和E2中有相同的QQ号即可。根据上面的结论,可以得出E1和E2的数据分别有25^3=15625个数据,只需要进行625次查找和15625次对比即可得出结果。

  接下来就是对两组15625个数据进行对比了,由于这15625个数据都是unsigned型数据,这里可以采用Bit-map或者hash的方式可以达到o(n)时间完成对比。(由于题目对空间没有限制)肯定有人对这个量级的计算还不满意,该如何继续优化了?只有一条路空间换时间。我们可以对好友的好友建立大量索引。
例如:A:{A1}{A2}{A3}
B:{B1}{B2}{B3}
An分别表示A的n度好友那么
1度好友为:A∈B1<=>B∈A1;
2度好友为:A∈B2<=>B∈A2,A1,B1有共同项;
3度好友为:{A1}{B2}有共同项,或者{B1}{A2}有共同项;
4度好友为:{A2}{B2}有共同项;
6度好友为:{A3}{B3}有共同项;

  这样在查询A的数据时就获得了A的2度,3度好友信息,只需要进行后面的对比即可。并且完全可以将这些数据放到本地计算,大大减轻了服务器的负担。

  第二问,每秒进行1K次查询,一天可以进行24*60*60*1K≈82M次查询操作。如果不对好友的好友进行索引,那么根据前面的结论,要索引的一个用户的六度好友需要进行25^5≈381K次查询。七度好友则需要大约9M次查询。因此最多只能计算出7度好友。同上,要想提高度数的话,可以对好友的好友进行索引,每多索引一度好友信息,就可以多提高1度。

  PS:其实这道题没有多大意义,因为根据牛津大学教授顿巴的研究,自然给我们人类的大脑,只能让我们维系150-200个左右的好友。超出这个范围,就会有好友慢慢地被淡忘。很多社会群体的平均大小是150,这个数也被称为顿巴数(Dunbar Number)。也就是说,一般两个好友之间最多存在4度关系。

  最后谈一下好友关系的更新,依然以六度好友为例。假设A与B建立了好友关系以后,整个系统的关系全都变化了,因为这个新的关系一定会导致一些关系的短路。但是因为我们只存储3度分隔以内的关系,也只关心3度分隔以内的关系,因此当发生了一个新的关系后,3度内关系的变化一定是A和B本身或者他们的1,2度关系的用户,再远的用户将不受这个关系的影响。根据上面的假设,A与B的索引信息需要进行修正:
3度修正,分别加上对方的2度:
{A3}={A3+B2};
{B3}={B3+A2};
2度修正:
{A2}={A2+B1};
{B2}={B2+A1};
1度修正:
{A1}={A1+B};
{B1}={B1+A};
操作次数为2*(25^2+25+1)=1302次。

责任编辑:liqwei
打印本页】【关闭本页】【返回列表
·上一篇:b-、b+树
·下一篇:10大流行编程语言和它们的创造者
 文章评分
  • current rating
-5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5
 相关文章
·[互联网]腾讯和搜狗的云输入法展示 (2010-10-26)
·[互联网]腾讯悄然推出在线拼音输入法(图) (2010-05-08)
·[软件信息]QQ词典 1.0 beta – 腾讯也推出的小巧桌面词典软件 (2010-05-07)
 广告推荐
 相关评论
 站点最新文章 更多>> 
·[经典影音]火星救援
·[程序综合]词性标注集(北大版)
·[Java/JSP]泛型
·[协议规范]5类IP地址如何划分?
·[至理名言]曾国藩:利可共而不可独,谋可寡…
·[至理名言]知乎上的48条神回复,针针见血,…
·[程序综合]汉字 Unicode 编码范围
·[应用服务器]开源分布式文件系统FastDFS和Mog…
·[财经知识]什么叫NDA协议
·[财经知识]2015最新个人所得税税率表及计算方法
 广告推荐
 站点浏览最多 更多>> 
·[协议规范]http断点续传原理:http头 Range、…
·[NoSQL]Mongo数据库简介
·[JS/CSS/HTML]HTML 空格的表示符号 nbsp / en…
·[协议规范]什么是SPF记录?如何设置、检测SP…
·[PHP]精选国外免费PHP空间推荐
·[程序综合]常用IP地址查询接口
·[协议规范]图解 HTTPS 通信过程
·[程序综合]什么是 DNS Prefetch ?
·[程序综合]获取客户端IP地址的三个HTTP请求…
·[PHP]国产常见PHP开源框架比较