一道百度试题，大家来试试

chenzhanyiczy

Good article ! Worth to attention.

Edengundam

原帖由 koolcoy 于 2007-7-5 20:47 发表
我的算法:
扫描输入, 并且对于任意一个用户x, 计算下面两个集合:
1. 用户x的好友的id集合
2. 把x加为好友的id集合.
有了上面这两个集合, 对于任意要判断y是否是x的二维好友就简单了:
如果: (x的好友的id集 ...

bingo

和我想的一样

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB

因为每次搜索时候, 对于A,B两个用户只需两次数组索引, 取得两个数组.

对于两个有序数组(假设两数组元素数相近, 这里近似考虑为平均好友数), 时间开销为2*n. 时间复杂度O(n).
******
但是因为保存父好友可能存在一种极端情况, 导致某个数组元素(n)相对另一个数组(m)非常大. (n >> m)
这种情况下可以考虑使用复杂度为m*log(n)的算法.
用m的每个元素去n中进行binary search.
******这个特例的搜索优化是同学想到的...

最后, 可以考虑对于内存极小情况下512M的分析.
因为, 内聚性增强, 因此每次最坏开销为读取两个分散在磁盘上的数据块.


不知道还有没有更好的数据结构...哈哈

[ 本帖最后由 Edengundam 于 2007-7-5 21:13 编辑 ]

福瑞哈哥

原帖由 Edengundam 于 2007-7-5 21:12 发表



bingo

和我想的一样

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB

因为每 ...

做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不见得有多少优势了。

确实会快一些，不过每次都要维护这两个有序数组也挺麻烦的。

koolcoy

原帖由 Edengundam 于 2007-7-5 21:12 发表



bingo

和我想的一样

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB

因为每 ...

赞那个特殊情况的搜索优化

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:24 发表


做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不 ...

怎么能够只比较两端就可以了呢?

福瑞哈哥

原帖由 koolcoy 于 2007-7-5 21:28 发表

怎么能够只比较两端就可以了呢?

如果只是要找他们是否有关系，只比较两端就可以了。

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:32 发表


如果只是要找他们是否有关系，只比较两端就可以了。

不行吧, 例如两个数组(1, 3, 5), (2, 3, 6), 只比较两端行吗?

Edengundam

原帖由 福瑞哈哥 于 2007-7-5 21:24 发表


做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。但是如果要找出具体路径这种方法就不见得有多少优势了。

确实会快一些，不过每次都要维护这两个有序数组也挺麻烦的。

首先, 我们澄清, 搜索命中好友的概率只有万分之2.5
对于你的思路1W次平均的搜索总开销:
2.5 * ((1 + 2500) * 2500/2) + 9997.5 * 2500 = 32809375
对于后者开销:
2.5 * ((1 + 100) * 100 /2) + 9997.5 * 100 = 1012375

相差32倍, 并且使用这样的算法, 搜索全路径时间开销也是2*N. 这里只需要100次.

另外判断2个数组是否包含相同元素, 2*N. 因为存在一个数组1, 3, 5, ..., 49另一个数组2, 4, 6, ..., 50的情况.


题目只设计搜索优化, 对于数据变动问题, 我们可以暂时不用考虑, 另外我分析少了一条:
在使用这种技术时候, 初始化索引结构的时间开销比你的方法至少多1倍以上(4GB+内存需要寻址)
但是, 这个初始化过程很简单...只是对当前用户的朋友列表做一次迭代就可以了.

Edengundam

原帖由 koolcoy 于 2007-7-5 21:26 发表

赞那个特殊情况的搜索优化

嘿嘿, 我那个同学今年又要参加baidu的算法大赛了, 上次就是来北京总部的...他特别牛.....一直搞算法的

给了你个鲜花, 哈哈...

福瑞哈哥

原帖由 koolcoy 于 2007-7-5 21:35 发表

不行吧, 例如两个数组(1, 3, 5), (2, 3, 6), 只比较两端行吗?

你理解的是正确的，比较两端缩小范围后再比较。这也正是反向索引后能优化的地方。