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,两将军问题
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 计算机理论

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 计算机理论

    前段时间给N年前的一些代码code review,其中涉及到了一个人机博弈的程序。人机博弈中有一个很重要的结构,就是优先队列,其作用的是能够随机的insert一些数据,并保证随时能获得最小(大)的点,其实该结构在大部分的图算法中(包括寻路问题)也很常用。我原来的代码使用heap实现的,不过最近看了一篇paper,是描述《帝国时代》游戏中寻路算法的数据结构的,很是新颖,其用线性表+缓存的结构就可以达到相当快的速度,于是想拿它来试试,看看它和堆哪个快。结果很失望,还是堆快,而且快的不是一星半点,当然也许在特定领域会有不同的表现。
    为了完善该paper的思想,我决定对这个结构进行改进,看看能不能接近或者超过堆。先看看堆的优先队列是如何实现的,我这里使用STL里面的结构:
class PriorityQueueHeap
{
private:
  vector<int> vec;
public:
  int ExtractMin();
  void Insert(const int value);
  void Display(){}
  bool IsEmpty(){return vec.empty();}
};
void PriorityQueueHeap::Insert(const int value)
{
vec.push_back(value);
push_heap(vec.begin(),vec.end(),greater<int>());
}
int PriorityQueueHeap::ExtractMin()
{
pop_heap(vec.begin(),vec.end(),greater<int>());
int min=vec.back();
vec.pop_back();
return min;
}
    接下来,我开始对线性表的结构进行改进,首先将固定缓存进行扩展,变成了动态缓存,在做了这个改进后,发现性能有显著提高,大约相当于STL Heap版的60%,这当然是不令人满意的;而后,利用桶排序的思想分割线性表并结合动态缓存修改算法,经过一系列精心的优化(比如减少函数调用次数,利用内联等等)后,惊人的效果出现了,测试表示改进后的时间比STL要快了将近30%,测试程序如下:
srand((unsigned)time(NULL));
for(int k=0;k<1;k++){
 KobePriorityQueue pq1; (PriorityQueueHeap pq1;)
     for(int i=0;i<=100000000;i++){
     int value=rand()%16777216;
     pq1.Insert(value);
     if(!pq1.IsEmpty()&&rand()%8==1)
        pq1.ExtractMin();
     }//end for i
}//end for k
    KobePriorityQueue是经过我改进后的结构,PriorityQueueHeap是STL最小堆实现,测试程序会不停的插入节点,并随机取最小点,随机数1/8的来源是因为大多数寻路问题(棋盘问题)新增节点和删除节点的比是8。测试结果如下(linux 4核,4G内存):

Scale Loop STL HeapPQ(average sec) KobePQ(average sec) KobePQ(best sec) percentage comparison
1000 10000 1.222 2.79 1.221 -0.08%
10000 1000 1.298 1.406 1.261 2.93%
100000 100 1.433 1.192 1.159 23.64%
1000000 10 1.535 1.214 1.214 26.44%
10000000 1 1.652 1.293 1.265 30.6%

    可见,在缺省参数下,十万级以上KobePriorityQueue比STL版本要快了25%,在10万级以下应用,通过调整参数也可以获得和STL相当的效率。当然这里的弱点就是在某些应用时,需要调节算法参数,使得其不像STL那样稳定通用(毕竟堆的操作效率基本都是logN,使得其时间消耗很稳定快速)。另,根据CLRS,有一种叫FIB heap的结构在插入时可以比最小堆更快,平摊获得O(1)的效率,根据其wiki链接,也下了一份其实现做比较,但结果很令人遗憾,其方法的速度比heap和KobePQ要慢了好几个数量级,当然不排重是代码编写的问题。
    总之,和C++和Java都采用的以堆实现的优先队列算法比较,KobePriorityQueue基本表现得略胜一筹,在某些特定要求速度的领域,可以代替STL Heap。当然在要求稳定性的领域,还是用STL更安全些。

前段时间给N年前的一些代码code review,其中涉及到了一个人机博弈的程序。人机博弈中有一个很重要的结构,就是优先队列,其作用的是能够随机的insert一些数据,并保证随时能获得最小(大)的点,其实该结构在大部分的图算法中(包括寻路问题)也很常用。我原来的代码使用heap实现的,不过最近看了一篇paper,是描述《帝国时代》游戏中寻路算法的数据结构的,很是新颖,其用线性表+缓存的结构就可以达到相当快的速度,于是想拿它来试试,看看它和堆哪个快。结果很失望,还是堆快,而且快的不是一星半点,当然也许在特定领域会有不同的表现。
    为了完善该paper的思想,我决定对这个结构进行改进,看看能不能接近或者超过堆。先看看堆的优先队列是如何实现的,我这里使用STL里面的结构:
class PriorityQueueHeap
{
private:
  vector<int> vec;
public:
  int ExtractMin();
  void Insert(const int value);
  void Display(){}
  bool IsEmpty(){return vec.empty();}
};
void PriorityQueueHeap::Insert(const int value)
{
vec.push_back(value);
push_heap(vec.begin(),vec.end(),greater<int>());
}
int PriorityQueueHeap::ExtractMin()
{
pop_heap(vec.begin(),vec.end(),greater<int>());
int min=vec.back();
vec.pop_back();
return min;
}
    接下来,我开始对线性表的结构进行改进,首先将固定缓存进行扩展,变成了动态缓存,在做了这个改进后,发现性能有显著提高,大约相当于STL Heap版的60%,这当然是不令人满意的;而后,利用桶排序的思想分割线性表并结合动态缓存修改算法,经过一系列精心的优化(比如减少函数调用次数,利用内联等等)后,惊人的效果出现了,测试表示改进后的时间比STL要快了将近30%,测试程序如下:
srand((unsigned)time(NULL));
for(int k=0;k<1;k++){
 KobePriorityQueue pq1; (PriorityQueueHeap pq1;)
     for(int i=0;i<=100000000;i++){
     int value=rand()%16777216;
     pq1.Insert(value);
     if(!pq1.IsEmpty()&&rand()%8==1)
        pq1.ExtractMin();
     }//end for i
}//end for k
    KobePriorityQueue是经过我改进后的结构,PriorityQueueHeap是STL最小堆实现,测试程序会不停的插入节点,并随机取最小点,随机数1/8的来源是因为大多数寻路问题(棋盘问题)新增节点和删除节点的比是8。测试结果如下(linux 4核,4G内存):

Scale Loop STL HeapPQ(average sec) KobePQ(average sec) KobePQ(best sec) percentage comparison
1000 10000 1.222 2.79 1.221 -0.08%
10000 1000 1.298 1.406 1.261 2.93%
100000 100 1.433 1.192 1.159 23.64%
1000000 10 1.535 1.214 1.214 26.44%
10000000 1 1.652 1.293 1.265 30.6%

    可见,在缺省参数下,十万级以上KobePriorityQueue比STL版本要快了25%,在10万级以下应用,通过调整参数也可以获得和STL相当的效率。当然这里的弱点就是在某些应用时,需要调节算法参数,使得其不像STL那样稳定通用(毕竟堆的操作效率基本都是logN,使得其时间消耗很稳定快速)。另,根据CLRS,有一种叫FIB heap的结构在插入时可以比最小堆更快,平摊获得O(1)的效率,根据其wiki链接,也下了一份其实现做比较,但结果很令人遗憾,其方法的速度比heap和KobePQ要慢了好几个数量级,当然不排重是代码编写的问题。
    总之,和C++和Java都采用的以堆实现的优先队列算法比较,KobePriorityQueue基本表现得略胜一筹,在某些特定要求速度的领域,可以代替STL Heap。当然在要求稳定性的领域,还是用STL更安全些。

13th 四 2010
Posted by kobe, and filed under 计算机理论
前一天,有个搜狗实验室的给我发信,问我的论文《Pagerank二维线性收敛方法》里默认的pagerank矩阵最大特征值为1的推论怎么来的,我回复了他,信件内容:
 
只要证明其不存在大于1的特征值即可
因为(M为n维行列式,V为n维PR向量)
M*V=V => 必存在特征值为1的特征向量
现在(&为特征值)
M*V=&*V
因为M为归一化后的行列式
所以
M*V=[ M1
      M2      *  V , M1的各项期望为1 , 设VM为V各项值的最大项
      M3     
      ...
      Mn]
假设&大于1, 则&*V中必有一项大于VM
但是M1-Mn的期望为1,也就是说他们和V的乘积都不大于Vm
[如(1/3,1/3,1/3) * (4,5,6)T <= 6]
这与假设矛盾 =》 不存在大于1的特征值
13th 四 2010
Tags:
Posted by kobe, and filed under 计算机理论

//edited by kobe
//计算器main

package caculater;
import java.io.*;
public class Caculater
{
private static Parser parser=new Parser();//Parser为分析器
public static void main(String[] args) throws IOException
  {
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  String s;
  while( (s=br.readLine()).length()!=0 )
    {
    System.out.println(parser.GetResult(s));
    }
  }
}

package caculater;
public class Token 
//类似词法分析部分,不过由于计算器的输入较简单所以这部分也简单
{
public static final int PLUS=1;
public static final int MINUS=2;
public static final int MUTI=3;
public static final int DIV=4;
public static final int NUM=5;
public static final int LP=6;
public static final int RP=7;
public static final int END=0;  
  public int GetToken(String s,int pos)
  {
  if(pos>=s.length()||pos<0)
     return 0;
  switch(s.charAt(pos))
         {
         case ’+':
              return PLUS;
         case ’-':
              return MINUS;
         case ’*':
              return MUTI;
         case ’/':
              return DIV;
         case ’1′:
         case ’2′:
         case ’3′:
         case ’4′:
         case ’5′:
         case ’6′:
         case ’7′:
         case ’8′:
         case ’9′:
         case ’0′:
         case ’.':
               return NUM;
         case ’(‘:
               return LP;
         case ’)':
               return RP;
         }
  return 0;
  }
}

package caculater;
//
public class Parser {
private String string;
private int currentpos=0;
private Token token=new Token();
  public double GetResult(String s)
  {
  string=s.trim();
  if(string.length()==0)
    {
    System.out.println(“输入为空,请重新输入…”);
    return 0;
    }
  currentpos=0;
  return ExprAdd(false);
  }
  public double ExprAdd(boolean underminus)
  {
  double left=ExprMuti(false,underminus);
  int mark=token.GetToken(string,currentpos);
  switch(mark)
         {
         case Token.PLUS:
               currentpos++;
               return left+ExprMuti(true,false);
         case Token.MINUS:
               return left+ExprMuti(true,true);
         default:
               return left;
         }
  }
  public double ExprMuti(boolean fromplus,boolean underminus)
  {
  double left=ExprBasic(true,false);
  int mark=token.GetToken(string,currentpos);
  switch(mark)
         {
         case Token.PLUS:
              if(fromplus)
                 {
                  currentpos++;
                  return left + ExprAdd(false);
                 }
              break;
        case Token.MINUS:
             if(fromplus)
                return left + ExprAdd(true);
             break;
         case Token.MUTI:
               currentpos++;
               return left*ExprBasic(true,false);
         case Token.DIV:
               double rl=ExprBasic(true,true);
               if(rl==0)
                  {
                  System.out.println(“Error:被除数为零”);
                  return 0;
                  }
               return left*rl;
         default:
               return left;
         }
  return left;
  }
  public double ExprBasic(boolean frommuti,boolean underdiv)
  {
  double left=ExprPrim();
  int mark=token.GetToken(string,currentpos);
  switch(mark)
         {
         case Token.MUTI:
               if(frommuti)
                 {
                 currentpos++;
                 if(underdiv)
                    return left*( 1/ExprBasic(true,false) );
                 return left * ExprBasic(true,false);
                 }
               break;
         case Token.DIV:
               if(frommuti)
                  {
                  double rl;
                     rl=ExprBasic(true,false);
                  if (rl == 0)
                     {
                      System.out.println(“Error:被除数为零”);
                      return 0;
                     }
                  return left*rl;
                  }
               break;
         default:
               return left;
         }
  return left;
  }
  public double ExprPrim()
  {
  int mark=token.GetToken(string,currentpos);
  switch(mark)
         {
         case Token.NUM:
               int endpos=currentpos+1;
               while(endpos<string.length()&&token.GetToken(string,endpos)==Token.NUM)
                     endpos++;
              double v=Double.parseDouble(string.substring(currentpos,endpos));
               currentpos=endpos;
               return v;
         case Token.MINUS:
               currentpos++;
               return -ExprPrim();
         case Token.LP:
               currentpos++;
               double vv=ExprAdd(false);
               if(token.GetToken(string,currentpos)!=Token.RP)
                  System.out.println(“Error:少括号”);
               currentpos++;
               return vv;
         case Token.DIV:
              currentpos++;
              double vvv=ExprPrim();
              if(vvv==0)
                 {
                 System.out.println(“Error:被除数为零”);
                 return 0;
                 }
              return 1/vvv;          
         default:
              System.out.println(“Error:输入错误”);
              break;
         }
  return 0;
  }
}

13th 四 2010
Tags:
illuminati
illuminati
 
Designed by