w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz 计算机应用 « SAE云计算
Twitter FaceBook
Home
Sina App Engine

Displaying Category '计算机应用'

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 计算机应用

需求:
一个千万级数据量的服务,不停的插入和删除记录,每条记录需要知道自己的排名,比如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 计算机应用

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
Posted by kobe, and filed under 计算机应用

一,框架性开发

分布式程序设计或者并行程序设计,往往需要将大量的精力花在如何制定通信协议、如何进行机器管理、如何进行共享存储、如何进行数据传输等方面,而这些工作对于每一个具体的分布式计算任务都是通用的,为了减少工作量,将分布式设计中通用的部分尽量设计为底层框架,这样在以后的应用中,只需要将精力集中在单机算法的设计中就可以轻松完成整个分布式程序设计。

google的mapreduce就是一种著名的分布式程序设计框架,根据google的说明,使用该框架,程序设计者不需用分布式程序设计经验,只要像原来写单机程序一样编写,就可以享受到上千台机器运算带来的巨大便利,而这种便利背后隐藏的技术细节都是由mapreduce提供的。

和mapreduce一样,SINA DCF也致力于提供分布式计算的底层框架,使用本框架,设计者不需要关心复杂的通信协调、容灾处理、任务分发等环节,只需要将精力集中在单笔任务处理的设计上,从而加快了分布式程序设计二次开发的问题。

二,基本流程

SINA DCF基本由三个环节组成:

1,任务分发:DCF使用者(程序员)根据规定的接口设计单笔任务执行模块,然后DCF负责将执行模块分配到各台机器上。

2,数据分发:DCF使用者(程序员)根据规定的接口设计原始数据分割模块,DCF将使用者分散好的数据分配到空闲的机器上。

3,指令分发:DCF根据协议,在各个阶段负责向每台机器发送相关指令,并接收从每台机器返回的指令,包括查询状态指令、运算状况指令、存活指令、错误发送指令、状态变更指令等。

总的流程是:

原始任务经过用户定义的MapDLL模块,分散到一个个小任务,小任务在DCF的协调下,会自动寻找空闲的存活机器节点,并传输到该机器上。同时,对于单笔小任务计算的执行由用户定义的TaskDLL模块规定,由DCF分配到每一台存活机器。根据任务和数据发送状态,主机(master)开启计算开关,启动某些台机器的计算线程。master定时维护从所有存活机器返回的信息,并更新机器状态和运算状态,对于down掉的机器或者运算出错的机器,按照调度算法重新加入等候机器列表,并将该任务视为重做。某一笔任务完成后,slave机器会将结果发送到reducer(结果合并机),由reducer合并结果。所有任务都运算完成后,master会通知用户计算完成,并生成统计报告,汇报计算情况耗费时间等等。

http://www.rayfile.com/files/7545ce26-470f-11df-b4d3-0015c55db73d/

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

JavascriptDevelopmentEnvironment,简称JSDE,是一套面向特殊需求的JS开发部署环境,对于JS的开发人员,它支持扩展JS语法、分析JS工程、分析CSS工程、整合JS代码、分析JS工程、除错等功能,是一套基于linux平台的,面向RIA开发人员的开发环境。

需求来源

JSDE的需求最早来源自RIA组的JS开发实际环境,JS开发需要两套系统:开发模式和线上模式。开发模式为人为编写的代码,线上模式为经过除注释、整合、混淆后的代码。可以近似的理解为开发模式对应源代码,而线上模式对应包含、link后的目标代码。
以linux下GCC编译环境为例,需要makefile的依赖分析, gcc的预编译、编译、链接等环境,最终形成从源代码.c文件到线上部署的可执行程序的转变。不像成熟的编译语言,JS语言没有统一、商业化的线上部署的环境支持,正基于此,为了提高整个RIA的开发效率、线上部署效率,一套灵活、具体的可靠的JSDE就显得尤为重要。

 

功能

JSDE具有以下12点功能:
1,致力于为RIA打造基于linux平台的JS开发部署环境:
基于通用框架,面向特定需求
2,具有支持类如自定义函数等扩展JS语法功能:
开发人员可以自形扩展javascript的语法,以达到方便工程的目的,扩展的语法由JSDE负责进行解释和转义
3,具有检查JS语法错误功能
可以检查代码的语法正确性
4,具有去除注释功能
可以去除代码的各种注释说明,以达到代码瘦身的目的
5,具有去除冗余代码功能
可以去除代码中的冗余部分,比如多余的分号、空格等,以达到代码瘦身的目的
6,具有整合代码功能
可以通过预编译,实现解释语言的include
7,具有依赖关系分析功能
类似Makefile,分析工程中的文件、函数等依赖关系,给出结构图,方便调试
8,具有编码检查功能
可以针对实际线上环境,检查工程文件编码格式,并提出警报
9,具有include once和检查功能
实现#pragam once等宏定义,保证依赖文件关系保持拓扑性(无环)
10,具有整合CSS功能
根据CSS语法和依赖关系,整合CSS代码
11,具有发布工程的功能
按工程配置,发布工程,完成开发模式到线上模式的转换
12,具有代码混淆功能
混淆代码,实现霍夫曼编码,达到代码瘦身的目的

http://www.rayfile.com/files/691976d9-75a4-11de-82fa-0014221b798a/

13th 四 2010
Tags:
illuminati
illuminati
 
Designed by