

下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、题目大意是这样的:1.平均每个QQ用户有25个好友,如何计算两个用户之间是不是六度可达。2.如果一台计算机每秒可以进行1000次查询,问一天能计算出一个用户最多几度好友,如何改变设计,使度数提高。思 路:首先说一下什么叫六度空间理论,根据百度百科的定义:该理论源于一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论或小世界理论等。理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。这道题,首先我们需要先构建一个六度空间,这样只要我们输入两个QQ号,就会搜索出两个用户之间的是否存在
2、六度关系。假设我们已经建好了这样一个六度空间。不妨设输入的两个QQ号用户分别为A,B。每个人的QQ号为一个unsigned int型数据。每次都以最坏情况为例。那么获取A的25个好友并对比其中是否有B,需要1次查找和25次对比。 获取A25个好友的25个好友并对比其中是否有B,需要25次查找,和252次对比。同理A的六度好友大约有(忽略重负)252525252525=2444MB1GB的数据。需要进行250M次的查找和1G的对比,这是一个相当恐怖的数据。该如何优化了?假设A,B六度可达不妨设A-C-D-E-F-G-B为A到B的路劲。不难看出若A,B六度可达,则A的三度好友,与B的三度好友,应该
3、有重叠。即从两个方向查找:A-C-D-E1B-G-F-E2只要E1和E2中有相同的QQ号即可。根据上面的结论,可以得出E1和E2的数据分别有253=15625个数据,只需要进行625次查找和15625次对比即可得出结果。接下来就是对两组15625个数据进行对比了,由于这15625个数据都是unsigned型数据,这里可以采用Bit-map或者hash的方式可以达到o(n)时间完成对比。(由于题目对空间没有限制)肯定有人对这个量级的计算还不满意,该如何继续优化了?只有一条路空间换时间。我们可以对好友的好友建立大量索引。例如:A:A1A2A3B:B1B2B3An分别表示A的n度好友那么1度好友为:
4、AB1BA1;2度好友为:AB2BA2,A1,B1有共同项;3度好友为:A1B2有共同项,或者B1A2有共同项;4 度好友为:A2B2有共同项; 6 度好友为:A3B3有共同项; 这样在查询 A 的数据时就获得了 A 的 2 度,3 度好友信息,只需要进行后面 的对比即可。 并且完全可以将这些数据放到本地计算,大大减轻了服务器的负担。 第二问, 每秒进行 1K 次查询, 一天可以进行 24*60*60*1K82M 次查询操作。 如果不对好友的好友进行索引,那么根据前面的结论,要索引的一个用户的 六度好友需要进行 255381K 次查询。七度好友则需要大约 9M 次查询。因此最 多只能计算出 7
5、 度好友。 同上, 要想提高度数的话, 可以对好友的好友进行索引, 每多索引一度好友信息, 就可以多提高 1 度。 PS:其实这道题没有多大意义,因为根据牛津大学教授顿巴的研究,自然给 我们人类的大脑,只能让我们维系 150-200 个左右的好友。超出这个范围,就会 有好友慢慢地被淡忘。很多社会群体的平均大小是 150,这个数也被称为顿巴数 (Dunbar Number)。也就是说,一般两个好友之间最多存在 4 度关系。 最后谈一下好友关系的更新,依然以六度好友为例。 假设 A 与 B 建立了好友关系以后,整个系统的关系全都变化了,因为这个新 的关系一定会导致一些关系的短路。但是因为我们只存储 3 度分隔以内的关系, 也只关心 3 度分隔以内的关系,因此当发生了一个新的关系后,3 度内关系的变 化一定是 A 和 B 本身或者他们的 1,2 度关系的用户, 再远的用户将不受这个关系 的影响。 根据上面的假设,A 与 B 的索引信息需要进行修正: 3 度修正,分别加上对方的 2 度: A3=A3+B2; B
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 北京航空航天大学北海学院《信息数学》2023-2024学年第二学期期末试卷
- CJ/T 3037-1995生活垃圾填埋场环境监测技术标准
- 2025年无形资产协议
- 北部湾大学《中医疫病学》2023-2024学年第二学期期末试卷
- 2025至2031年中国芦荟润肤液行业投资前景及策略咨询研究报告
- 2025至2031年中国美多洛尔片行业投资前景及策略咨询研究报告
- 2025至2031年中国管式纯蒸汽发生器行业投资前景及策略咨询研究报告
- 2025至2031年中国电池铁壳行业投资前景及策略咨询研究报告
- 百色学院《室内乐合奏》2023-2024学年第二学期期末试卷
- DB13T 5043-2019 冬小麦测土配方施肥技术规程
- 外卖骑手劳务合同协议书
- T/CAMIR 002-2022企业技术创新体系建设、管理与服务要求
- DB31/T 595-2021冷库单位产品能源消耗指标
- 第五章 SPSS基本统计分析课件
- 2025年计算机Photoshop操作实务的试题及答案
- 2025时事热点政治题及参考答案(满分必刷)
- GB/T 23453-2025天然石灰石建筑板材
- 2024-2030全球WiFi 6移动热点行业调研及趋势分析报告
- 砌砖理论考试题及答案
- 中医针灸治疗脑梗塞后遗症的应用实践
- 2025年高等数学期末考试试题及答案
评论
0/150
提交评论