原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。
原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。
原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。
原帖由 ivhb 于 2007-7-5 17:24 发表
用qsort+bsearch，怎么得出的那个复杂度？
原帖由 converse 于 2007-7-5 17:27 发表
福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.
| 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 ++; } |
原帖由 spibit 于 2007-7-5 17:55 发表
typedef struct _user
{
int userid;
// 好友数目
int count;
// 好友列表数组，最后一个为0表示结束。
int *friends;
}user_t;
// user_t指针的数组，假设数据已经全部读进来了，use ...
原帖由 福瑞哈哥 于 2007-7-5 18:00 发表
我支持你。 因为这也是我的想法。
原帖由 chenzhanyiczy 于 2007-7-5 19: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
...
原帖由 Edengundam 于 2007-7-5 19:11 发表
这个想法最直接. 其实给出的复杂度是总用户的复杂度, 既然使用了数组下标索引, 也就没有什么时间复杂度的问题.
这题关键是数据结构占用的内存数量. 以及每次查找A, B关系的时间开销.
这种直接的方法 ...
原帖由 福瑞哈哥 于 2007-7-5 20:14 发表
对，内存大概要2G，这是麻烦的地方。不过你知道搜索引擎公司都是怎么做的吗？ 如果一台机器放不下，那就用两台，把数据一分为二。或者一台机器两个进程，内存现在一般都是2G的，如果多进程可以把内存加到更 ...
原帖由 Edengundam 于 2007-7-5 20:26 发表
我意思是应该提高查找二维好友速度...空间换时间
原帖由 koolcoy 于 2007-7-5 20:47 发表
我的算法:
扫描输入, 并且对于任意一个用户x, 计算下面两个集合:
1. 用户x的好友的id集合
2. 把x加为好友的id集合.
有了上面这两个集合, 对于任意要判断y是否是x的二维好友就简单了:
如果: (x的好友的id集 ...
原帖由 Edengundam 于 2007-7-5 21:12 发表
bingo
和我想的一样
帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB
因为每 ...
原帖由 Edengundam 于 2007-7-5 21:12 发表
bingo
和我想的一样
帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB
因为每 ...
原帖由 福瑞哈哥 于 2007-7-5 21:24 发表
做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不 ...
原帖由 koolcoy 于 2007-7-5 21:28 发表
怎么能够只比较两端就可以了呢?
原帖由 福瑞哈哥 于 2007-7-5 21:32 发表
如果只是要找他们是否有关系，只比较两端就可以了。
原帖由 福瑞哈哥 于 2007-7-5 21:24 发表
做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。但是如果要找出具体路径这种方法就不见得有多少优势了。
确实会快一些，不过每次都要维护这两个有序数组也挺麻烦的。
原帖由 koolcoy 于 2007-7-5 21:26 发表
赞那个特殊情况的搜索优化
原帖由 koolcoy 于 2007-7-5 21:35 发表
不行吧, 例如两个数组(1, 3, 5), (2, 3, 6), 只比较两端行吗?
原帖由 Edengundam 于 2007-7-5 21:37 发表
嘿嘿, 我那个同学今年又要参加baidu的算法大赛了, 上次就是来北京总部的...他特别牛.....一直搞算法的
给了你个鲜花, 哈哈...
原帖由 福瑞哈哥 于 2007-7-5 21:40 发表
你理解的是正确的，比较两端缩小范围后再比较。这也正是反向索引后能优化的地方。
实在想不出什么了...在想我也无法冲破这些时间界了
估计高手还有高招
原帖由 Edengundam 于 2007-7-5 21:35 发表
首先, 我们澄清, 搜索命中好友的概率只有万分之2.5
对于你的思路1W次平均的搜索总开销:
2.5 * ((1 + 2500) * 2500/2) + 9997.5 * 2500 = 32809375
对于后者开销:
2.5 * ((1 + 100) * 100 /2) + 9997.5 ...
原帖由 koolcoy 于 2007-7-5 21:43 发表
我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.
原帖由 福瑞哈哥 于 2007-7-5 21:46 发表
建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。
原帖由 福瑞哈哥 于 2007-7-5 21:46 发表
建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。
| 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) return -1; if (a->fl[ac - 1] < b->fl[0]) return -1; if (a->fl[ac - 1] == b->fl[0]) return b->fl[0]; while (ac >= 0 && bc >= 0) if (a->fl[ac] > b->fl[bc]) ac--; else if (a->fl[ac] > b->fl[bc]) bc--; else return a->fl[ac]; return -1; } |
原帖由 Edengundam 于 2007-7-5 22:03 发表
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-7-5 22:57 发表
if (a->fl[ac - 1] = b->fl[0])
return b->fl[0];
Edengundam 大哥你少写了一个=吧。。。。
原帖由 robin10 于 2007-7-6 01:41 发表
对比上面提到的两种算法，如果考虑最坏情况的话，是不是有这样的关系呢。。。？
对于第二种情况：假使A的好友有500，而加B的好友有1000W，那么查找B是不是A的2维好友的话，是不是要对比 500*（1000W-1）次呢？ ...
原帖由 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...^^ } } |
原帖由 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
如 ...
原帖由 xi_qh 于 2007-7-6 10:42 发表
的确这是个问题，在查询某个用户的好友时，需要初始化，但是只需初始化某一个id的好友和好友的好友
原帖由 Edengundam 于 2007-7-6 10:48 发表
这样内存占用小, 但是对数组初始化(10,000,000)相对50来说开销就不划算了.
另外, 一个用户id平均需要7个数字字符(假设是ASCII编码的文件, 每个字符占用1字节)分隔符是一个\t
平均好友列表50 * (7+1): ...
| 欢迎光临 Chinaunix (http://bbs.chinaunix.net/) | Powered by Discuz! X3.2 |
