w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz SAE云计算
Twitter FaceBook
Home
Sina App Engine
Posted by kobe, and filed under 计算机应用
今天同事问我一事,就是关于这个路子的用户关系查找是怎么实现的,首先说明几点:
1,经过我实验,结果不是100%准确,有些明明存在的6,7步的关系找不出来,报“没有找到相关记录”;即使出了结果,优先级有时误差很大
2,结果不是事先算好的,否则不应该有时计算时间多达10多秒
3,离线做了优化,否则不会有这句话“可能是由于新用户或者我们的数据还不完全”
这个问题的实质可以转化为有向图(关注和粉丝为双向)的任意两个几点之间的最优路径(准确的说是最优的一些路径)问题,可能的实现方案有:
1,floyd算法:
该算法就是标准的图求任意两点之间最短路径的算法,基本原理是利用动态规划解释一下公式,A到C的最短距离一定是
min(A到B的最短距离+B到C的最短距离,A到C的最短距离)
但weibook采用这种办法的可能性是0,有以下几个原因,首先该算法是完全准确的算法,不会出现在数据存在的情况下找不出来关系的问题。另外该算法需要离线海量运算,因为复杂度为O(N^3),假设用户级别为1000万,那么就是1000万的三次方,天文计算了。另外还有一点,该算法的最终结果保存挺费空间的,因为需要N*N的节点都保存自己的路径,也是个海量的数据,所以肯定不可行。
2,迪杰斯卡尔算法
著名的单源最短路径算法,其实也不太可能,主要原因还是计算量大,而且用该算法无法模拟出weibook的效果,即不仅是最短(优)的路径,而是若干个最短(优)的路径。因为该算法是以贪婪的方式每次伸出最短枝,一旦触及到目的地,算法即终止,只能选出唯一一个路径(最优的那个)。所以也不太可能。
3,
Easy提出一个从源和目的两边同时发散出几级好友,然后取交集的做法。该算法的实现相对简单,但问题还在于运算量,如果级数有限制还好说,比如4级,如果没限制就麻烦了,因为是指数增长,运算量太大。而weibook的结果有的就是7级的关系,这样的取交集计算量有点太大了。该方法另一个不可能的原因和迪杰斯卡尔有点类似,就是只能选出同一级的多个最优算法,而不能选出不同级的多个最优算法。因为算法的终止条件就是找到了目的即终止。比如:
找A和B的关系,A的一级粉丝有200个,A的二级粉丝有40000个,B的一级粉丝有100个,二级粉丝有10000个;而双方的二级粉丝有交集。其实就是A=>C=>D=>F=>B
A到B是4级的关系,那么用该算法,如果取最优的N个关系,只能选出同为4级的一些关系,而无法获取到5级、6级的关系。这明显与weibook的效果不一样。如果该算法继续算5级、6级的关系,可以想象,我们无法设计出该算法的终止条件。
4,A*算法
其实该算法还是很适合解决这类问题的,但问题是我们无法仅仅通过粉丝名,预判其关系度。如果我们能通过粉丝名,预判出关系度,那么就可以设计评估函数,然后使A*了,但很遗憾,不能。
5,带剪枝的启发式搜索
我们看weibook的实现,基本有以下特点:
1,有这么一个思路,通过某种逻辑找最优路径,在寻找的过程中,捎带的把一些比较优的路径(如果有的话)也输出。
2,应该有剪枝,如果没有剪枝,则结果肯定是100%准确了,而且我们发现weibook找的这些人,基本都是较活跃的用户,所以可以肯定寻路中会舍弃一些节点。
所以我猜可能是这么实现的:
首先,点和点之间有权值,权值根据用户间的回复、评论等情况做校正,权值越低,表示用户关系越紧密(一定要转换为最短路径问题,因为最长路径问题是NP);从源用户开始,以类似宽度优先的方式做查找,只不过宽度优先的queue换成了优先队列,优先级按照当前路径的权值和从低到高排序。不是所有寻路分支都会进优先队列,过低的权值的节点会舍弃。通过这种方式找到最优路径后,把中间找到的其他路径一并按权值和做排序,最终输出。
=>(2)B =>(2)E =>(1) X
A =>(30)C
=>(1)D =>(10) X
上面表示A有3个粉丝(B、C、D),关系权值分别是2、3、1(权值越低关系越好),B有粉丝E,E有粉丝X;D有粉丝X;我们要找A到X的最优关系。假设我们的剪枝门阀是20,于是C节点在第一层就被剪掉了,于是B和D进入优先队列,按照从低到高为D,B;下层搜索先从D开始,D有一个粉丝直接就到X了,于是找到了一个路径(权值为1+10=11)。但根据优先队列,这时B会冒在优先队列的第一个了(2<11),所以继续从B开始搜索,于是到E到X,这时路径权值为2+2+1=5,此时优先队列没有更优的待选分支,且已经找到X,于是吧找到的两个路径一起输出。一个是最优路径A=>B=>E=>X,另一个是次优路径,A=>D=>X
30th 九 2010
Tags:
Posted by kobe, and filed under 计算机理论
开场白:
什么是分布式
分布式的目的
一,协议
理论:
1,两将军问题
2,多将军问题
实战:
A,TCP协议可靠吗?
B,如何设计两点之间的通信协议
C,如何设计多点之间的通信协议
二,分区
理论:
1,动态分区
2,静态分区
分区带来的问题
三,事务
理论:
1,分布式事务的不可能性
2,两阶段提交
3,三阶段提交
实战:
A,两台数据库各负责一部分用户,实现用户间的转账,怎么做?
B,10个Web前端升级代码,如何保证版本完全一致?
四,复制
理论:
1,主动复制
2,被动复制
复制带来的问题
五,一致性
理论:
1,拜占庭将军问题
2,选主
3,最终一致性
4,向量时钟
5,PAXOS
实战:
A,利用本地锁实现多机选主
B,利用PAXOS实现选主
六,其他
1,快照
2,计算网
12th 九 2010
Tags:
Posted by kobe, and filed under 计算机应用

需求:
一个千万级数据量的服务,不停的插入和删除记录,每条记录需要知道自己的排名,比如SNS中的抢车位,如何让每个uid能够知道自己在所有人中的车总价排名?

致命伤(cache无用论)
有1000万个用户,试想排名第500万的用户突然发飙了,把他的车全卖了,那么他之后的500万个用户的排名都提高了,也就是cache全部瞬间失效了。。。pity,此时加再多的cache只能是浮云

解决方法:
1,划分子空间,不提供全部用户的排名,只提供用户在其好友中的车总价的排名(其实这样更有意义,不过这是产品层面),这样即时一个用户车价变化,影响的也只是其好友的cache,别人不做影响
2,牺牲实时性,算不过来就离线算呗,这个太容易想到了,比如车总价的排名是每12个小时更新一次的

BT的需求:
假如,只是假如,我们就需要uid在所有用户中的实时准确排名怎么办??(产品不想牺牲实时性的UE),这时解决问题只能靠更好的算法模型

扩展的红黑树:
这个结构在一般数据结构书不提,在CLRS是以扩展话题为讨论的,在TAOCP中是以课后题出现,但在CLRS的视频中可是重点介绍,讲了一节课呢,所以推荐看这个视频11.Dynamic.Statistics。拷贝书上的介绍nonsense,所以只是简单的介绍一下:扩展红黑树ERBT中,每个节点不仅有color,link,key信息,还包括了一个很重要的信息=>该节点所有子节点的数目(包括其自身在内),这样每个节点的排名可以在找到它的那一霎那得到,因为(初始rank(root)=0):
rank(lnode)=rank(pnode)
rank(rnode)=children_count(lnode)+1
而作为补偿,同样需要在更改操作时,维护子节点的数目
查找和维护的时间复杂度都是log(n)

解决方案:
还是车总价的排名显示问题,我们在内存中维护这样一颗ERBT,key就是车的总价位,当有用户的车总价发生变化时,我们就删除这个节点并插入一个新节点。当需要显示用户的车总价排名时,先从uid得到车总价的数值(比如从mysql中),然后拿这个数值到ERBT中做查找,当找到这个值的时候,排名自然得到。

对于千万级数据,log(n)基本在20-30,而使mc的话,每秒请求可以到2万这个级别,我们假设hash的拉链平均长度为3,也就是使用ERBT的速度理论上是直接hash的1/10,也就是能够支撑2000r/s的请求,这样的能力对于一般的SNS应用也是够了。当然如果要求更高性能还需要做更多的优化。

故障恢复:
首先这个服务就支持分布式,因为每台机器可以独立的跑ERBT,另外即时down机了,恢复也很容易,只要从mysql中导入数据一遍则自动生成,我们也可以把ERBT定时按照hash的形式dump出一份,以备意外时访问

13th 四 2010
Tags:
Posted by kobe, and filed under 计算机理论

Thinking in Algorithm Application

-C++ description

by kobe

引言:

.适合听众
.目的初衷
.选材标准
.参考文献

开场白:

.算法能解决什么问题?

一,查找
二分查找:
1,接口设计
涉及话题:
1,数据定长是否必须?
2,数据有序是否必须?
C++实现:
std::equal_range
预备知识:
1,什么是二分查找
相关阅读:
1,http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html

哈希:
1,线性探测、高次探测
2,拉链=>对象分配
涉及话题:
1,为什么推荐用素数为底取模?
2,为什么bloom filter冲突概率低?
3,一台服务器上同时跑2个计算排行榜的cron,一个周期是20分钟,一个周期是30分钟,有什么问题?
C++实现:
boost::hash
预备知识:
相关阅读:
1,《算法导论 第2版》,11.3
2,http://en.wikipedia.org/wiki/Bloom_filter

二,排序
排序:
1,局部排序
2,最大N个元素
3,原地排序
4,集合操作(交、并)
涉及话题:
1,快速排序有什么方式减少栈消耗?
2,有序性带来什么好处?
3,播客如何显示热门视频排行榜?
C++实现:
1,std::sort
2,std::nth_element
3,C++建堆
4,C++实现优先队列
预备知识:
1,快速排序的原理
相关阅读:
1,《算法导论 第2版》,9.2
2,《算法导论 第3版》,27.1
3,《计算机程序设计艺术 卷3 中文版》,5.2.2

三,随机
随机算法:
1,随机排列
2,随机组合
涉及话题:
1,内存中的已知长度的用户数据,随机抽奖怎么实现?
2,mysql中的博客数据,随便逛逛怎么实现?
3,未知长度的用户数据,随机抽奖怎么实现?
4,假如设计一个系统,支持CCTV NBA直播结束的短信抽奖,如何设计是最轻量级的实现?
C++实现:
1,std::random_shuffle
2,std::next_permutation
预备知识:
相关阅读:
1,《计算机程序设计艺术 卷2 中文版》,3.4
2,《计算机程序设计艺术 卷4 英文版》,7.2.1.2
3,http://www.sgi.com/tech/stl/next_permutation.html

四,字符串
字符串查找:
1,简化版kmp
2,多字符串匹配
涉及话题:
1,strstr等的效率如何?
2,做博文的多关键词过滤,怎么实现最快?
C++实现:
1,std::string的好处
预备知识:
1,KMP的基本原理
相关阅读:
1,http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

字符串匹配:
1,元素有序要求
2,元素无序要求
涉及话题:
1,两个字符串,如何判断相似度?
2,两个索引表,如何判断相似度?
C++实现:
1,std::vector的好处及拷贝
预备知识:
相关阅读:
1,《算法导论 第2版》,15.4

五,树
搜索树:
1,遍历方式
2,逆波兰
3,扩展节点信息
涉及话题:
1,最优雅的遍历树的方式是什么?
2,一个用树实现的索引表,怎么同步到硬盘上?
3,老虎机游戏中,每个游戏者都想实时知道自己的金币排名,怎么实现?
C++实现:
1,std::map
2,删除陷阱
3,序列化
预备知识:
1,基本二叉树
2,二叉树遍历
相关阅读:
1,《计算机程序设计艺术 卷1 中文版》,2.3.1
2,《现代编译原理-C语言描述》,13.1
3,《编译原理 第2版 中文版》,5.4.1
3,《算法导论 第2版》,14.2
4,http://www.boost.org/doc/libs/1_39_0/libs/serialization/doc/index.html

六,图
图:
1,遍历
2,图的含义
涉及话题:
1,SNS中,每个用户都可以对好友发feed,如何找出关键用户?
2,Google图片搜索中的图片排重的实现原理?
C++实现:
1,boost::graph
预备知识:
1,图的遍历
相关阅读:
1,PageRank for Product Image Search
2,Deeper Inside PageRank
3,The Anatomy of a Large-Scale Hypertextual Web Search Engine
4,The Second Eigenvalue of the Google Matrix

七,内存分配
内存池:
1,适用范围
2,定长对象内存池
3,非定长对象内存池
涉及话题:
1,C++中的对象内存池和C的对象内存池,实现有什么重要区别?
2,boost中的object_pool有什么重要缺陷,怎么比它更快?
C++实现:
1,boost::pool
预备知识:
相关阅读:
1,《计算机程序设计艺术 卷1 中文版》,2.5
2,http://www.boost.org/doc/libs/1_38_0/libs/pool/doc/concepts.html
3,《深入理解linux内核》,6.2.1

八,常见技巧
1,局部
2,延迟
3,抽样
4,迭代
5,平摊
涉及话题:
1,黑石国际五子棋AI冠军如何保证在规定时间内出招?
2,满屏NPC时,星际争霸如何保证两个圣堂武士合体寻路流畅?
3,kai心网抢车位游戏数据显示的策略变化的好处?
4,用户数据存放在两个库里,如何最快的实现库合并?
5,linux内核如何实现O(1)时间进程调度?
预备知识:
相关阅读:
1,《人工智能游戏编程箴言 中文版》,3.4
2,《More Effective C++ 中文版》,条款17
3,《算法导论 第2版》,17.3
4,《linux内核设计与实现 中文版》,4.2.3

九,开放话题
1,新浪版C++真的比C快吗?
2,我们能否写出比STL还快的算法?
3,我们用担心C++慢吗?
4,研究算法有用吗?

十,经验
1,80:20
2,有所得必有所失
3,选择适当的语言、适当的实现、适当的算法
4,一定要使用标准库,尽量避免使用非标准库
5,不尊重用户是一种罪,而欺骗用户是一种美

edited by kobe, 2009.5.13

13th 四 2010
Tags:
Posted by kobe, and filed under 计算机应用

int SelfSort(vector<int>& vec)
{
int loop_number=0;
for(int i=vec.size()-1;i>=1;)
    {
     loop_number++;
     if(vec[i]<i)
        swap(vec[i],vec[vec[i]]);
     else
        i–;
    }
return loop_number;
}

int main(int argc,char* agrv[])
{
srand(time(NULL));
vector<int> vec;
for(int i=0;i<1000;i++)
     vec.push_back(i);
random_shuffle(vec.begin(),vec.end(),p_myrandom);
cout<<SelfSort(vec)<<endl;
return 0;
}

13th 四 2010
illuminati
illuminati
 
Designed by