您现在正在浏览：首页 > Linux > Linux编程 >

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

时间:2008-01-16 11:14:23 来源: 作者:

考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，
好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。

用户以ID形式表示，现给出好友列表数据的文本形式如下：
1  3,5,7,67,78,3332
2  567,890
31  1,66
14    567
78  10000
…
每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。

要求：
请设计合适的索引数据结构，来完成以下查询：
给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

详细说明自己的解题思路，说明自己实现的一些关键点。
并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。

限制：
用户数量不超过1000万，平均50个好友。

福瑞哈哥回复于：2007-07-05 17:08:08

每个用户是排序数组，用户id就是数组索引。
用户好友用排序数组，初始长度50，以后根据情况realloc扩充。
查找就简单了，定位用户A，遍历A的好友，af1,af2,...,afn，
再查找afx的好友看有没有B。完成。
内存也就使用几百M。
内存可能不止这么多，麻烦。

[ 本帖最后由福瑞哈哥于 2007-7-5 17:36 编辑 ]

feiyang21687 回复于：2007-07-05 17:13:05

这样算法的时间复杂度O(n^2)，太慢了。

福瑞哈哥回复于：2007-07-05 17:17:38

引用：原帖由 feiyang21687 于 2007-7-5 17:13 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7011800&ptid=958272]
这样算法的时间复杂度O(n^2)，太慢了。

如果能放在内存中，如果你能做到比这还快，还干嘛去百度做题啊？
如果不嫌罗嗦，就使用双向指针吧。每个用户把视自己为朋友的用户也列出来。不过我是不会这么做的。

啊，双向指针也并不快。

[ 本帖最后由福瑞哈哥于 2007-7-5 17:30 编辑 ]

ivhb 回复于：2007-07-05 17:24:42

引用：原帖由 feiyang21687 于 2007-7-5 17:13 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7011800&ptid=958272]
这样算法的时间复杂度O(n^2)，太慢了。

用qsort+bsearch，怎么得出的那个复杂度？

converse 回复于：2007-07-05 17:27:10

福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.

福瑞哈哥回复于：2007-07-05 17:27:22

引用：原帖由 ivhb 于 2007-7-5 17:24 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7011869&ptid=958272]

用qsort+bsearch，怎么得出的那个复杂度？

同意，好友是顺序遍历是N，间接好友查找就不需要N了。
我觉得设计有一点是不能把非重要或者非常用功能当作优化重点。

福瑞哈哥回复于：2007-07-05 17:32:23

引用：原帖由 converse 于 2007-7-5 17:27 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7011885&ptid=958272]
福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.

没错，不过不是O(N^2)。

jigloo 回复于：2007-07-05 17:45:21

http://www.wespoke.com/archives/001077.html

spibit 回复于：2007-07-05 17:55:57

[table=95%][tr][td][font=FixedSys]typedef struct _user
{
  int userid;

  // 好友数目
  int count;

  // 好友列表数组，最后一个为0表示结束。
  int *friends;
}user_t;

// user_t指针的数组，假设数据已经全部读进来了，users数组最后一个为0，表示结束。
user_t *users[];

// 这个函数，获取users数组里面 userid匹配的 user，
// 已经排序好的，折中搜索？复杂度ln(n)，实现略。
user_t  * users_get_user(user_t **users, int userid);

// 是好友吗？看在不在好友列表里面了，
// 已经排序好的，折中搜索？复杂度ln(n)，实现略。
int user_is_friend(user_t * user, int userid);

// B是A好友的好友？
int yes = 0;
int * friendsA = users_get_user(users, A)->friends;
user_t  * friendsAA;
while (0 != friendsA)
{
  friendsAA = users_get_user(users, *friendsA);
  if (0 == user_is_friend(friendsAA, B))
  {
    yes = 1;
    break;
  }
  friendsA ++;
}[/font][/td][/tr][/table]

[ 本帖最后由 spibit 于 2007-7-5 18:07 编辑 ]

福瑞哈哥回复于：2007-07-05 18:00:22

引用：原帖由 spibit 于 2007-7-5 17:55 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012103&ptid=958272]
typedef struct _user
{
  int userid;

  // 好友数目
  int count;

  // 好友列表数组，最后一个为0表示结束。
  int *friends;
}user_t;

// user_t指针的数组，假设数据已经全部读进来了，use ...

我支持你。          因为这也是我的想法。 :)

BILLJEFF 回复于：2007-07-05 18:45:44

建立图，邻接链表，然后DFS，对查询结果进行缓存，存储最近N次查询（因为目的是为了查询）。

chenzhanyiczy 回复于：2007-07-05 19:09:09

Actually, I think there should be able to use Linker table plus Binary . Sth like this :

struct binary
{
  struct binary *lbinary;
  struct binary *rbinary;
  int val;
}

struct linkt
{
  int val;
  struct linkt *nlink;
}

struct a
{
  struct linkt *p_link;
  struct binary *p_binary;
}

Dunno right !!??

Edengundam 回复于：2007-07-05 19:11:43

引用：原帖由福瑞哈哥于 2007-7-5 18:00 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012126&ptid=958272]

我支持你。因为这也是我的想法。 :)

这个想法最直接. 其实给出的复杂度是总用户的复杂度, 既然使用了数组下标索引, 也就没有什么时间复杂度的问题.

这题关键是数据结构占用的内存数量. 以及每次查找A, B关系的时间开销.

这种直接的方法:

空间开销: 10,000,000 * 50 * 4 / 1,000,000 是2GB的内存占用.
对于一个二维好友来说, 其搜索命中概率为 50 * 50 / 10, 000, 000 大约是万分之2.5的概率, 千分之0.25.
也就是说, 这种算法, 几乎每次都进行2500次检测. 也就是平均好友数量的二次方倍.

如果考虑实际环境内存为512M
那么需要对索引数据结构进行分块. 而对于这种常规的方法, 可能导致大量的swap交换. 一维好友产生的结果分布很散.

综上: 如何将数据的内聚性提升, 将可以缓解小内存时swap交换的概率(或者将部分索引存储到磁盘上, 总之目的是降低兑换的频率).
对于内存2GB情况, 因为搜索命中率较低, 因此降低这种N^2, 可以提高系统响应.

Edengundam 回复于：2007-07-05 19:35:44

引用：原帖由 chenzhanyiczy 于 2007-7-5 19:09 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012389&ptid=958272]
Actually, I think there should be able to use Linker table plus Binary . Sth like this :

struct binary
{
  struct binary *lbinary;
  struct binary *rbinary;
  int val;
}

struct linkt
...

你能给出用binary的思路吗..??

查找的时间相对平均一维好友数应该是O(n)吧...:)
可能咱俩思路一样

chenzhanyiczy 回复于：2007-07-05 19:56:24

Maybe U & me both imagine are similar.

The Binary will store all member of each member of A user.

The Linnk will store all member of A user.

福瑞哈哥回复于：2007-07-05 20:14:49

引用：原帖由 Edengundam 于 2007-7-5 19:11 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012396&ptid=958272]

这个想法最直接. 其实给出的复杂度是总用户的复杂度, 既然使用了数组下标索引, 也就没有什么时间复杂度的问题.

这题关键是数据结构占用的内存数量. 以及每次查找A, B关系的时间开销.

这种直接的方法 ...

对，内存大概要2G，这是麻烦的地方。不过你知道搜索引擎公司都是怎么做的吗？如果一台机器放不下，那就用两台，把数据一分为二。或者一台机器两个进程，内存现在一般都是2G的，如果多进程可以把内存加到更多比如16G。

Edengundam 回复于：2007-07-05 20:26:24

引用：原帖由福瑞哈哥于 2007-7-5 20:14 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012582&ptid=958272]

对，内存大概要2G，这是麻烦的地方。不过你知道搜索引擎公司都是怎么做的吗？如果一台机器放不下，那就用两台，把数据一分为二。或者一台机器两个进程，内存现在一般都是2G的，如果多进程可以把内存加到更 ...

我意思是应该提高查找二维好友速度...空间换时间

福瑞哈哥回复于：2007-07-05 20:30:02

引用：原帖由 Edengundam 于 2007-7-5 20:26 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012617&ptid=958272]

我意思是应该提高查找二维好友速度...空间换时间

关注，愿闻其详。

koolcoy 回复于：2007-07-05 20:47:43

我的算法:
扫描输入, 并且对于任意一个用户x, 计算下面两个集合:
1. 用户x的好友的id集合
2. 把x加为好友的id集合.
有了上面这两个集合, 对于任意要判断y是否是x的二维好友就简单了:
如果: (x的好友的id集合) 交 (把y加为好友的id集合) != 空集, 则y是x的二维好友.

注意: 因为上面算法的特点, 我们可以把每个用户的那两个集合保存到磁盘或数据库, 以提高效率, 这样即使内存很紧的计算机也不会很慢.

[ 本帖最后由 koolcoy 于 2007-7-5 20:52 编辑 ]

chenzhanyiczy 回复于：2007-07-05 20:52:54

Good article ! Worth to attention.

Edengundam 回复于：2007-07-05 21:12:19

引用：原帖由 koolcoy 于 2007-7-5 20:47 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012687&ptid=958272]
我的算法:
扫描输入, 并且对于任意一个用户x, 计算下面两个集合:
1. 用户x的好友的id集合
2. 把x加为好友的id集合.
有了上面这两个集合, 对于任意要判断y是否是x的二维好友就简单了:
如果: (x的好友的id集 ...

bingo

和我想的一样:em02:

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为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的分析.
因为, 内聚性增强, 因此每次最坏开销为读取两个分散在磁盘上的数据块. :em15:

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

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

福瑞哈哥回复于：2007-07-05 21:24:51

引用：原帖由 Edengundam 于 2007-7-5 21:12 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012745&ptid=958272]

bingo

和我想的一样:em02:

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

因为每 ...

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

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

koolcoy 回复于：2007-07-05 21:26:08

引用：原帖由 Edengundam 于 2007-7-5 21:12 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012745&ptid=958272]

bingo

和我想的一样:em02:

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

因为每 ...

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

koolcoy 回复于：2007-07-05 21:28:58

引用：原帖由福瑞哈哥于 2007-7-5 21:24 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012792&ptid=958272]

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

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

福瑞哈哥回复于：2007-07-05 21:32:43

引用：原帖由 koolcoy 于 2007-7-5 21:28 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012815&ptid=958272]

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

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

koolcoy 回复于：2007-07-05 21:35:07

引用：原帖由福瑞哈哥于 2007-7-5 21:32 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012831&ptid=958272]

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

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

Edengundam 回复于：2007-07-05 21:35:56

引用：原帖由福瑞哈哥于 2007-7-5 21:24 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012792&ptid=958272]

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

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

首先, 我们澄清, 搜索命中好友的概率只有万分之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 回复于：2007-07-05 21:37:54

引用：原帖由 koolcoy 于 2007-7-5 21:26 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012800&ptid=958272]

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

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

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

福瑞哈哥回复于：2007-07-05 21:40:38

引用：原帖由 koolcoy 于 2007-7-5 21:35 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012842&ptid=958272]

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

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

koolcoy 回复于：2007-07-05 21:43:29

引用：原帖由 Edengundam 于 2007-7-5 21:37 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012858&ptid=958272]

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

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

我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.

Edengundam 回复于：2007-07-05 21:45:30

引用：原帖由福瑞哈哥于 2007-7-5 21:40 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012867&ptid=958272]

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

比较两端缩小范围, 可以优化一下, 就是看看A的子友好最后一个ID和B的父好友的第一个ID的大小关系, 如果是小于等于就直接出结果.
其它情况就可以不考虑了, 算法的复杂度大于意义了, 很可能性能下降. 如果真的需要, 可以考虑对数据进行数据统计再着手进行.

:em03:

我现在期待的是还有没有更好的点子......:em15: 实在想不出什么了...在想我也无法冲破这些时间界了:em06: 估计高手还有高招
当然分析一下在2GB内存情况, 对于第一种思路和第二种思路, 性能的优劣可能相当的有挑战, 对于这种情况下, 第二种思路就要精心设计一下缓存策略了:mrgreen:

福瑞哈哥回复于：2007-07-05 21:46:41

引用：原帖由 Edengundam 于 2007-7-5 21:35 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012847&ptid=958272]

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

建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

Edengundam 回复于：2007-07-05 21:48:59

引用：原帖由 koolcoy 于 2007-7-5 21:43 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012885&ptid=958272]

我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.

我那个同学挺猛, 一年到头一直比赛......今年还去了东京参加比赛...不过貌似总是和奖金失之交臂...

算法这东西我觉得是兴趣吧, 我算法就特别烂...:em16:
我觉得算法好还是有优势, 一些大公司还是有不少对算法要求很高的工作职位.

koolcoy 回复于：2007-07-05 21:49:35

引用：原帖由福瑞哈哥于 2007-7-5 21:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012903&ptid=958272]

建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

比较集合就两种吧, 复杂度分别为O(m+n)和O(m*ln(n)), 先估算一下哪种快, 然后就用那种方法.

Edengundam 回复于：2007-07-05 22:03:12

引用：原帖由福瑞哈哥于 2007-7-5 21:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012903&ptid=958272]

建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

[table=95%][tr][td][font=FixedSys][color=#000000][color=#0000ff]typedef[/color] [color=#0000ff]struct[/color] FriendList [color=#0000cc]{[/color]
[color=#0000ff]int[/color] fc[color=#0000cc];[/color]
[color=#0000ff]int[/color] fl[color=#0000cc][[/color]50[color=#0000cc]][/color][color=#0000cc];[/color]
[color=#0000cc]}[/color] FriendList[color=#0000cc];[/color]

[color=#0000ff]int[/color] com[color=#0000cc]([/color]FriendList [color=#0000cc]*[/color]a[color=#0000cc],[/color] FriendList [color=#0000cc]*[/color]b[color=#0000cc])[/color]
[color=#0000cc]{[/color]
    [color=#0000ff]int[/color] ac [color=#0000cc]=[/color] a[color=#0000cc]-[/color][color=#0000cc]>[/color]fc[color=#0000cc];[/color]
    [color=#0000ff]int[/color] bc [color=#0000cc]=[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fc[color=#0000cc];[/color]
    [color=#0000ff]if[/color] [color=#0000cc]([/color]ac [color=#0000cc]=[/color][color=#0000cc]=[/color] 0 [color=#0000cc]|[/color][color=#0000cc]|[/color] bc [color=#0000cc]=[/color][color=#0000cc]=[/color] 0[color=#0000cc])[/color]
        [color=#0000ff]return[/color] [color=#0000cc]-[/color]1[color=#0000cc];[/color]

    [color=#0000ff]if[/color] [color=#0000cc]([/color]a[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]ac [color=#0000cc]-[/color] 1[color=#0000cc]][/color] [color=#0000cc]<[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]0[color=#0000cc]][/color][color=#0000cc])[/color]
        [color=#0000ff]return[/color] [color=#0000cc]-[/color]1[color=#0000cc];[/color]

    [color=#0000ff]if[/color] [color=#0000cc]([/color]a[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]ac [color=#0000cc]-[/color] 1[color=#0000cc]][/color] [color=#0000cc]==[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]0[color=#0000cc]][/color][color=#0000cc])[/color]
        [color=#0000ff]return[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]0[color=#0000cc]][/color][color=#0000cc];[/color]

    [color=#0000ff]while[/color] [color=#0000cc]([/color]ac [color=#0000cc]>[/color][color=#0000cc]=[/color] 0 [color=#0000cc]&[/color][color=#0000cc]&[/color] bc [color=#0000cc]>[/color][color=#0000cc]=[/color] 0[color=#0000cc])[/color]
        [color=#0000ff]if[/color] [color=#0000cc]([/color]a[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]ac[color=#0000cc]][/color] [color=#0000cc]>[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]bc[color=#0000cc]][/color][color=#0000cc])[/color]
            ac[color=#0000cc]-[/color][color=#0000cc]-[/color][color=#0000cc];[/color]
        [color=#0000ff]else[/color] [color=#0000ff]if[/color] [color=#0000cc]([/color]a[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]ac[color=#0000cc]][/color] [color=#0000cc]>[/color] b[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]bc[color=#0000cc]][/color][color=#0000cc])[/color]
            bc[color=#0000cc]-[/color][color=#0000cc]-[/color][color=#0000cc];[/color]
        [color=#0000ff]else[/color]
            [color=#0000ff]return[/color] a[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc][[/color]ac[color=#0000cc]][/color][color=#0000cc];[/color]

    [color=#0000ff]return[/color] [color=#0000cc]-[/color]1[color=#0000cc];[/color]
[color=#0000cc]}[/color]
[/color][/font][/td][/tr][/table]

如果需要返回多个结果, 再传进来结构体就行了..很简单的思路

哈哈, 刚才少写了个return.....

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

福瑞哈哥回复于：2007-07-05 22:08:40

引用：原帖由 Edengundam 于 2007-7-5 22:03 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7012988&ptid=958272]

typedef struct FriendList {
int fc;
int fl[50];
} FriendList;

int com(FriendList *a, FriendList *b)
{
    int ac = a->fc;
    int bc = b->fc;
    if (ac == 0 || bc == 0)
       ...

学习。有序集合的交集。

robin10 回复于：2007-07-05 22:57:46

if (a->fl[ac - 1] = b->fl[0])
return b->fl[0];
:em10:
Edengundam 大哥你少写了一个=吧。。。。

Edengundam 回复于：2007-07-05 23:06:34

引用：原帖由 robin10 于 2007-7-5 22:57 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7013216&ptid=958272]
if (a->fl[ac - 1] = b->fl[0])
return b->fl[0];
:em10:
Edengundam 大哥你少写了一个=吧。。。。

:em16: :em16: :em16:
最近果然脑袋不行了...丢三落四....开始还少写个return ...:em06:

谢谢提醒.

O(m + n) 和 O (m * log(n))的情况大概是n/m > 8 的时候二分搜索就会更快了.

就是求解m + n > m * log(n)不等式...然后我转换求m + n == m * log(n) 表达式的解, 两边求导, 找驻点什么的...高数忘光了...然后大概得到了n = m^2/(m - 1) ....数学高手帮帮算算...:em15:

xi_qh 回复于：2007-07-05 23:47:15

long i,j;
#define N 10000000
long id[N];
while(i=0;i<N;i++)
id[N]=i;
/*
read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........
*/

/*
开始判断某个id是否二级好友
count=0;
while(j=id;j!=id[j];j=id[j])
count++;
if(count==2)

*/

xi_qh 回复于：2007-07-05 23:50:16

long i,j;
#define N 10000000
long id[N];
while(i=0;i<N;i++)
       id[N]=i;
/*
read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........
*/

/*
开始判断某个id是否二级好友
count=0;
while(j=id;j!=id[j];j=id[j])
        count++;
if(count==2)
        找到一个二级好友
*/

空间复杂度是N，时间复杂度是初始化O(N)+要搜索的好友数*2

robin10 回复于：2007-07-06 01:18:56

read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........

不是很明白。。。:em06:

robin10 回复于：2007-07-06 01:41:36

对比上面提到的两种算法，如果考虑最坏情况的话，是不是有这样的关系呢。。。？
对于第二种情况：假使A的好友有500，而加B的好友有1000W，那么查找B是不是A的2维好友的话，是不是要对比 500*（1000W-1）次呢？
而对于第一种情况，最坏的似乎是在500个好友里面，对500个ID（假使A的500个好友里面每一个都有500个好友。。）的一次折半查找。。。。。具体不太清楚那一个时间多一点。。没有具体想。。。

robin10 回复于：2007-07-06 01:45:19

而题目说。平均好友只有50。。。这样第一次会不会好点。。。

Edengundam 回复于：2007-07-06 07:41:51

引用：原帖由 robin10 于 2007-7-6 01:41 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7013500&ptid=958272]
对比上面提到的两种算法，如果考虑最坏情况的话，是不是有这样的关系呢。。。？
对于第二种情况：假使A的好友有500，而加B的好友有1000W，那么查找B是不是A的2维好友的话，是不是要对比 500*（1000W-1）次呢？ ...

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

这个极端我需要的次数拖同学算法的福为:
500 * log(10M) < 4900

即使没有优化我需要的复杂度也只有10M + 500.

PS: 第一种才是500 * 10M

之前分析少了关键一步...每次都必须用一次binary search处理A, B是一维好友的情况. 第一种, 第二种情况开销都大约是6次(log50).
相比A,B二维关系, 貌似影响是可忽略的, 而且复杂度开销也是个线性的. 两个结论还是: N^2和min(m+n, m*log(n)).
:mrgreen:

[ 本帖最后由 Edengundam 于 2007-7-6 08:02 编辑 ]

titansword2000 回复于：2007-07-06 08:33:01

我认为福瑞哈哥谈到下面的这种方法可能是最合适的(无论从时间还是从空间角度)：
取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不见得有多少优势了。

但就象koolcoy所说的那样，不能只比较两端。另外，算法在得到那个反向有序集合后还可以继续进行优化，因为它也是一个有序数组。

xi_qh 回复于：2007-07-06 09:01:00

不好意思，漏掉一段
/*
read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........
然后再设置A好友的好友，比如如果好友3的好友是 10，100，那么id[9]=2,id[99]=2.......
*/

xi_qh 回复于：2007-07-06 09:13:24

对上面的补充
假设有三个用户1，10，100，其中10是1的好友，100是10的好友
要找1的二级好友
那么首先id[10]=1，然后id[100]=10,
然后开始查找。因为找100的好友就是两步，首先看100的内容和其索引号是否相符，不等，就查找以其内容为索引的那个位置。
代码也就是
/*
开始判断某个id是否二级好友
count=0;
while(j=id;j!=id[j];j=id[j])
count++;
if(count==2)
找到一个二级好友
*/

Edengundam 回复于：2007-07-06 09:24:26

xi_qh 你的数据结构是一维数组?
你能介绍下你的数据结构如何存储嘛??
因为你只给了一行的例子, 所以看不太明白:em06:

难道要用快速并集的策略??但是如何证明, 相互数据不会影响计算count数??

xi_qh 回复于：2007-07-06 09:46:55

的确是一维数组，就是用快速并集，在《C算法》里面开篇就讲到了。
储存方式就是一个用户的好友，其对应的数组的内容都存储其id
比如用户id是1，其好友是2，3，4，那么id[2]=1,id[2]=1,id[4]=1,本身id[1]=1
如果用户2的好友是5，6 那么id[5]=2,id[6]=2
现在开始查找如果是用户7 ，因为id[7]=7,count=0,所以不是
用户6：id[6]=2,继续id[2]=1,继续id[1]=1,此时id和id[]内容相等，中止。count=2，找到一个。
关于相互影响的问题，再设置的时候，可以加一个判断，如果本身数组的内容已经是要找的id用户，此处是1，那就不要设置.

A.com 回复于：2007-07-06 10:07:02

由于B是给定的，所以只需要查找包含B为好友的的用户U(x)，然后在A的好友列表中对比U(x)，如果存在，则B为A的二维好友。这种方法的复杂度是固定的，1000w次简单查询（遍历数据库一次）和一次简单对比。缺点是速度慢，优点是内存开销几乎=0，可以在后台慢慢来整理这些数据。

PS：由于A->X->B的好友关系可能是单向的，所以反向好友的算法都有可能存在疏漏，无法采用:em06:

zhangzezhi 回复于：2007-07-06 10:20:45

ding

Edengundam 回复于：2007-07-06 10:21:37

引用：原帖由 A.com 于 2007-7-6 10:07 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7014322&ptid=958272]

PS：由于A->X->B的好友关系可能是单向的，所以反向好友的算法都有可能存在疏漏，无法采用

这个你是指哪个算法??

反向的建立是简单, 因为输入数据有序了, 所以建立数据结构不会疏漏. 如下没写完的分配, 大意就是初始化过程和数据结构.

[table=95%][tr][td][font=FixedSys][color=#000000][color=#0000cc]#[/color][color=#ff0000]define[/color] USER_NO 10000000
[color=#0000cc]#[/color][color=#ff0000]define[/color] AVERAGE_NO 50

[color=#0000ff]typedef[/color] [color=#0000ff]struct[/color] FriendList [color=#0000cc]{[/color]
[color=#0000ff]int[/color]    [color=#ff0000]list[/color][color=#0000cc][[/color]AVERAGE_NO[color=#0000cc]][/color][color=#0000cc];[/color]
[color=#0000cc]}[/color] FriendList[color=#0000cc];[/color]

[color=#0000ff]typedef[/color] [color=#0000ff]struct[/color] [color=#0000ff]Friend[/color] [color=#0000cc]{[/color]
[color=#0000ff]int[/color]    fc[color=#0000cc];[/color]
FriendList    [color=#0000cc]*[/color]fl[color=#0000cc];[/color]
[color=#0000cc]}[/color] [color=#0000ff]Friend[/color][color=#0000cc];[/color]

[color=#0000ff]typedef[/color] [color=#0000ff]struct[/color] MapFriend [color=#0000cc]{[/color]
[color=#0000ff]Friend[/color] [color=#0000cc]*[/color]cf[color=#0000cc];[/color]
[color=#0000ff]Friend[/color] [color=#0000cc]*[/color]pf[color=#0000cc];[/color]
[color=#0000cc]}[/color] MapFriend[color=#0000cc];[/color]

MapFriend mapFriend[color=#0000cc][[/color]USER_NO[color=#0000cc]][/color][color=#0000cc];[/color]

[color=#0000ff]void[/color] buildMapFriend[color=#0000cc]([/color][color=#0000ff]int[/color] id[color=#0000cc],[/color] [color=#0000ff]int[/color] fcount[color=#0000cc],[/color] [color=#0000ff]int[/color] [color=#0000cc]*[/color]flist[color=#0000cc])[/color]
[color=#0000cc]{[/color]
    [color=#0000ff]Friend[/color] [color=#0000cc]*[/color]tmp
    mapFriend[color=#0000cc][[/color]id[color=#0000cc]][/color][color=#0000cc].[/color]cf[color=#0000cc]-[/color][color=#0000cc]>[/color]fc [color=#0000cc]=[/color] fcount[color=#0000cc];[/color]
    mapFriend[color=#0000cc][[/color]id[color=#0000cc]][/color][color=#0000cc].[/color]cf[color=#0000cc]-[/color][color=#0000cc]>[/color]fl [color=#0000cc]=[/color] flist[color=#0000cc];[/color]
    [color=#0000ff]while[/color] [color=#0000cc]([/color]fcount[color=#0000cc]-[/color][color=#0000cc]-[/color][color=#0000cc])[/color]
    [color=#0000cc]{[/color]
        tmp [color=#0000cc]=[/color] mapFriend[color=#0000cc][[/color]flist[color=#0000cc][[/color]fcount[color=#0000cc]][/color][color=#0000cc]][/color][color=#0000cc].[/color]pf[color=#0000cc];[/color]
        [color=#0000ff]if[/color] [color=#0000cc]([/color]tmp[color=#0000cc]-[/color][color=#0000cc]>[/color]pf [color=#0000cc]=[/color][color=#0000cc]=[/color] [color=#ff0000]NULL[/color][color=#0000cc])[/color]
        [color=#0000cc]{[/color]
            tmp[color=#0000cc]-[/color][color=#0000cc]>[/color]pf [color=#0000cc]=[/color] [color=#0000cc]([/color][color=#0000ff]Friend[/color] [color=#0000cc]*[/color][color=#0000cc])[/color] malloc0[color=#0000cc]([/color][color=#0000ff]sizeof[/color][color=#0000cc]([/color][color=#0000ff]Friend[/color][color=#0000cc])[/color][color=#0000cc])[/color][color=#0000cc];[/color]
            tmp[color=#0000cc]-[/color][color=#0000cc]>[/color]pf[color=#0000cc]-[/color][color=#0000cc]>[/color]fl [color=#0000cc]=[/color] [color=#0000cc]([/color]FriendList [color=#0000cc]*[/color][color=#0000cc])[/color] malloc0[color=#0000cc]([/color][color=#0000ff]sizeof[/color][color=#0000cc]([/color]FriendList[color=#0000cc])[/color][color=#0000cc])[/color][color=#0000cc];[/color]
        [color=#0000cc]}[/color]
        tmp[color=#0000cc]-[/color][color=#0000cc]>[/color]pf[color=#0000cc]-[/color][color=#0000cc]>[/color]fl[color=#0000cc]-[/color][color=#0000cc]>[/color][color=#ff0000]list[/color][color=#0000cc][[/color]tmp[color=#0000cc]-[/color][color=#0000cc]>[/color]pf[color=#0000cc]-[/color][color=#0000cc]>[/color]fc[color=#0000cc]+[/color][color=#0000cc]+[/color][color=#0000cc]][/color] [color=#0000cc]=[/color] id[color=#0000cc];[/color]
        // if fc >= 50, we need to alloc another FriendList to Friend...^^
[/color]
    [color=#0000cc]}[/color]
[color=#0000cc]}[/color][/font][/td][/tr][/table]

[ 本帖最后由 Edengundam 于 2007-7-6 10:26 编辑 ]

Edengundam 回复于：2007-07-06 10:31:08

引用：原帖由 xi_qh 于 2007-7-6 09:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7014164&ptid=958272]
的确是一维数组，就是用快速并集，在《C算法》里面开篇就讲到了。
储存方式就是一个用户的好友，其对应的数组的内容都存储其id
比如用户id是1，其好友是2，3，4，那么id[2]=1,id[2]=1,id[4]=1,本身id[1]=1
如 ...

比如下面这个列表:
1          3,5,7,9
2          1,3,5,9
3          4,5,8,9
5          1,2,39
9          1,3

数据结构是一次把所有信息存储上??
初始化过程                   数组索引-->
     |
     |
    /
数组索引                          [1]    [2]     [3]   [4]    [5]    [6]  [7]   [8]   [9]
初始化值                   1      2       3      4      5      6     7      8     9
读入id=1用户信息          1      2        1     4       1      6    1       8     1
读入id=2用户信息          ?      2         ?     4       ?      6    ?       8     ?

这个数据结构是怎么变化的...不太理解你最后一句话的意思.
是每次查询时候, 都需要进行一次初始化嘛???

A.com 回复于：2007-07-06 10:36:24

另一种方法就是多任务并行处理了，在得到A的好友列表A(x)后同时在这些用户的好友列表里面找已知的B。这系统开销虽然看起来会比较大，但由于平均好友只有50个，实际上这办法比遍历1000w条数据的总开销要少得多。

xi_qh 回复于：2007-07-06 10:42:15

的确这是个问题，在查询某个用户的好友时，需要初始化，但是只需初始化某一个id的好友和好友的好友

Edengundam 回复于：2007-07-06 10:48:34

引用：原帖由 xi_qh 于 2007-7-6 10:42 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7014595&ptid=958272]
的确这是个问题，在查询某个用户的好友时，需要初始化，但是只需初始化某一个id的好友和好友的好友

这样内存占用小, 但是对数组初始化(10,000,000)相对50来说开销就不划算了.
另外, 一个用户id平均需要7个数字字符(假设是ASCII编码的文件, 每个字符占用1字节)分隔符是一个t
平均好友列表50 * (7+1): 7表示用户id: 1表示逗号和最后的换行. 平均每行的长度: 8 * 51 = 408字节.
408 * 10M = 4GB
这样下来, 对于磁盘性能貌似是很大的挑战. :wink:

softsongs 回复于：2007-07-06 13:18:04

做个标记，改天给个解决方案，今天是没时间看了。

neoedmund 回复于：2007-07-06 15:27:38

最简单的应用啊

prettywolf 回复于：2007-07-06 23:50:22

百度准备搞即时通讯了.

robin10 回复于：2007-07-07 01:19:49

引用：原帖由 Edengundam 于 2007-7-6 10:48 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7014631&ptid=958272]

这样内存占用小, 但是对数组初始化(10,000,000)相对50来说开销就不划算了.
另外, 一个用户id平均需要7个数字字符(假设是ASCII编码的文件, 每个字符占用1字节)分隔符是一个t
平均好友列表50 * (7+1): ...

不清楚我是不是理解得不太清楚，但是我同意 Eden 的说法。。。
存储的数据的空间开销是不是很大呢。。。？希望可以祥解：）

jamesr 回复于：2007-07-07 09:33:51

不需要遍历1000W个吧！这么大的数据在建立是一定有HASH索引的，按普通的思路，平均只要读50＊50次数据就行了。

福瑞哈哥回复于：2007-07-07 10:49:45

普通思路只需要50*5就可以了，一级好友遍历，二级好友bsearch。简单就好。

弥敦路九号回复于：2007-07-07 22:24:19

即然是基于索引的搜索，题目中要给明对索引成本(构建索引时间，空间)的要求，和查询成本的要求(以及对两者优先级)还有数据的变动性频度。

索引成本不计：从任何一种方法逐个获取2维好友列表B+树(归档)形成索引文件.此法对查询性能最好，一个对出发点A的B树查找加上一个对其二维好友B的B树查找。
重索引次查询：B树构建入口（出发用户），对每个用户的发友建立B树，此树上的每个用户链接到入口形成通过入口找到一维度好友，通过链接找到一维好友做为出发点的入口再找二维好友。这样，总体就是一个入口的B树查找加上N个其一维度好友为入口的B树查找。
居中：在上法基础上对每个用户建立“视其为好友的用户”的B树，这样最后就是求两个B树是否有交集性能要比上法好，但需要多个建立B树的成本。

converse 回复于：2007-07-07 23:27:58

没有完全看完，但是感觉koolcoy 应该是里面最好的。

考虑到百度是一家互联网公司面对的是海量的数据，如果实际操作中有这样的查询需求应该还会做一个cache缓存的数据。

bosshoss_cn 回复于：2007-07-08 13:44:38

只是求二维好友，不是N维好友？
不懂，请教下

bosshoss_cn 回复于：2007-07-08 13:49:32

ID，1维好友，二维好友
最大空间：50*50*10M=25G
:em06:

原文链接：http://bbs.chinaunix.net/viewthread.php?tid=958272
转载请注明作者名及原文出处