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

A.com

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

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

zhangzezhi

ding

Edengundam

原帖由 A.com 于 2007-7-6 10:07 发表

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

这个你是指哪个算法??

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

#define USER_NO 10000000 #define AVERAGE_NO 50 typedef struct FriendList { int    list[AVERAGE_NO]; } FriendList; typedef struct Friend { int    fc; FriendList    *fl; } Friend; typedef struct MapFriend { Friend *cf; Friend *pf; } MapFriend; MapFriend mapFriend[USER_NO]; void buildMapFriend(int id, int fcount, int *flist) {     Friend *tmp     mapFriend[id].cf->fc = fcount;     mapFriend[id].cf->fl = flist;     while (fcount--)     {         tmp = mapFriend[flist[fcount]].pf;         if (tmp->pf == NULL)         {             tmp->pf = (Friend *) malloc0(sizeof(Friend));             tmp->pf->fl = (FriendList *) malloc0(sizeof(FriendList));         }         tmp->pf->fl->list[tmp->pf->fc++] = id;         // if fc >= 50, we need to alloc another FriendList to Friend...^^     } }

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

Edengundam

原帖由 xi_qh 于 2007-7-6 09:46 发表
的确是一维数组，就是用快速并集，在《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

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

xi_qh

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

Edengundam

原帖由 xi_qh 于 2007-7-6 10:42 发表
的确这是个问题，在查询某个用户的好友时，需要初始化，但是只需初始化某一个id的好友和好友的好友

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

softsongs

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

neoedmund

最简单的应用啊

prettywolf

百度准备搞即时通讯了.