Archive for ‘Algorithm’ Category

2015/02/17

如何把一个已排序的数组(或者单链表)转化成一个BST ? 最简单最容易想到的方法是每次取中间的节点作为 root,把数组/链表分成左右子树,然后递归。

1,443 views
2014/10/28

深度优先搜索一般用递归的方法实现,但是怎么写好一个递归程序对于我来说挺难的。 每隔一段时间写又会犯各种错误,思绪来得快也走得快,有必要记录一下。 首先用一个问题来引出 DFS:给定一个字符串,要求用空格来分割,生成它的所有可能的分割方法。 比如给定 “abc”, 那么可能的分割是 “a” “b” “c” 或者 “ab” “c” 或者 “a” “bc” 这些题目都是给一个字符串,生成符合题意要求的分割后的结果。 既然解法类似,那么代码肯定也是类似了,只是会多加一些判断条件。 我们先回到一开始的问题:如何生成所有可能的分割?

4,364 views
2013/02/22

跳表(skiplist) 是一个非常有趣的、简单的数据结构, 应用也非常广泛, 著名的NoSQL内存数据库Redis, 就用到了skiplist作为排序集合的基础数据结构。 跳表最大的特点就是插入、删除操作的性能均为O(logn) 。 关于它的原理网上有一大堆,如果不了解的话,可以先看看文章末尾的【参考资料】, 或者动手google一下。 正好这里也有一篇我觉得写的不错的文章, 可以猛击此处 。

Tags: ,. 29,947 views
2012/01/18

要求:模拟一个缓存管理器。给出的测试文件中包含50万个页面请求,每一行用(X,Y)表示,其中X=1表示对页面号为Y的页面写操作,X=0表示对页面号为Y的页面读操作。例如  0,6558     1,3024  等。 规定:磁盘上的页面大小等于Buffer的一个块大小,为4KB;磁盘上的数据库文件data.dbf包含5000个页面,缓冲区有1024个Buffer。设计一个缓存管理器,并统计页面请求的命中和不命中次数。 先说下我的思路,如图,问题牵涉到下面三个部分的协同工作,其中省略了磁盘的读写部分。 解释一下图中的各个部分: 1、Buffer的每一个块4KB,等于磁盘中的数据文件一页的大小,不同的是文件data.dbf有5000页,约193MB,Buffer只有1024块,因此不可能把文件全部加载到缓存中,所以需要有一种合适置换策略,尽量让访问最多的页面驻留在Buffer中,这样可以减少去磁盘读取的次数。 2、Buffer中的每一块都有一个相应的控制结构BCB,BCB详细的记录Buffer中块号(Frame ID)和这一块在文件中所对应的页面号(Page ID)。 3、先说Hash Table,然后再说Table。所有的BCB都散列在Hash Table中,对于每一个页面请求,先使用hash函数将请求的页面号(Page ID)定位到对应的bucket内,在bucket内是一串BCB组成的链表,逐个比较BCB结构内的页面号,如果有与所请求的页面相等的,则说明该页面在Buffer中,直接返回;如果没有搜索到,则说明该页面不再Buffer内,需要去data.dbf文件中将该页面读入,并且在Buffer中选择一个最久没有使用的块,将它的位置让给新的页面。 4、Table就是保存Buffer中每个块所对应的Page ID以及最近一次访问的时间,根据Table的内容,我们可以找出一个最久没有使用的块。 很显然的,如何有效的管理Table,使得我们可以高效的找出一个被替换出Buffer的牺牲页,是至关重要的。 如何来找呢? 老师给的实验参考上说要用LRU算法,因此我最先想到的是以引用时间为关键字,建立一个小根堆,一旦某一个页面被访问,立即更新它的引用时间,这样堆顶元素就是最久没有使用的块了。于是我写好了堆的算法,但是发现了一个致命的弱点:由于页面请求是随机的,因此无法根据请求的页面ID在堆中快速的找到相应的Page ID是在第几个位置(因为堆中元素是在不断调整的),除非逐个搜索,但是这样就变成线性查找了,失去了本来用堆的目的,因此放弃。用链表法?显然查找最小的时间的复杂度也是O(n)。 然后尝试使用FIFO,但是牵涉到是队列的调整(因为某个页面已经在队列中,这时它又被访问了,它的位置并不一定在队头,那么需要将它从队列中取出放到队尾,取出后其他元素也要前移,所以它的复杂度并不比线性查找要好。 之后,想到的是将Table与Buffer一一对应,即Table[1]记录Buffer[1]储存的是哪一个Page,已经访问的时间,但要寻找最小的时间时,遍历整个Table找到最小,时间复杂度是O(n),这个看似比较费时的操作在现在一般配置的机器上似乎并不慢,于是选择的是这种方法。 当我写好了以后,在CFAN的群里面和几位大牛讨论的时候还提到了一种NRU法,即最近未使用法,不过牵涉到对整个Table周期性的更新引用时间,我目前还没想好具体的做法,也许等写完这篇Blog后可以仔细的思考。 同样,程序的代码放在我的GitHub上,这里是运行结果: Dave GG说,可以不使用引用时间。 的确,因为现在的计算机执行指令的速度超乎想象,在2次更新引用时间之间,即使是gettimeofday()函数取得微秒级的时间,也有可能是一样的,但是有没有什么更好的方法呢?用计数器似乎还有一个溢出的问题。 纸上得来终觉浅,绝知此事要躬行。确实是这样的,每一次写这样的程序都会有很多收获,也有更多疑惑,会发现很多跟书上讲的不一致的东西。不知道真正的数据库里是用的什么替换算法?是怎么实现的?操作系统里真正又是用的什么置换算法?又是怎么实现的?

9,332 views
2010/02/10

前两天一直在做这一道题,题目其实很简单,求n的阶乘,即从1× 2× 3……× n。但是这个要求的数特别大,当n=100000时,结果恐怕有上万位,所以,一种解决方法是用数组存储各个数位,例如用数组 array[] 储123456789,那么array[0]=1,array[1]=2 …..array[8]=9。至于计算过程,我们可以想象一下自己做乘法,例如,算12× 34 ,先算12×4,再将结果移位并×3。好了,整个解题的基本原理就是这样了。 初次尝试 为了节约储存的空间,我第一次是用char型数组存储各位的,但在计算的过程中,不可避免的要遇到把字符转换为数字的过程,在每次一次算中,特别是数据非常大时,每一次计算要有成千上万次的字符转数字过程,所以最后的结果是时间超时,并不是我当初未雨绸缪的“内存超限”,当然,其中有一步没有优化,总之失败。 第二次尝试 这次,去网上搜了一些成功的案例以及在论坛提问,于是决定用int数组存储数字的各位,例如,结果是 123456789,那么 int[0]=1,int[1]=2…..int[8]=9。再用一个int型 pos记录结果有多少位,这样可以节约for()循环的时间,最后AC了。 按照 davelv 的思路优化 主要的思想是用一个int存很多个数据,而之前我是一个int只存一个数。 如果最后结果是 12345678909876543210000 D大是 r[0]=543210000 r[1]=678909876 r[2]=12345 我原来理解是 从r[0]~~r[23]各存一位,那么每次的取模(MOD)就应该是1 000 000 000了,而不是10。一个int 4字节,最大2^32-1 ,结果 =4 294 967 294,一共9位。 这样优化的确大大的提高了执行效率,减少了内存占用,上图,下面一行为优化后的。 可见,优化的力量是非常强大的! 好了,就写到这儿 贴出   我的代码 和   davelv的代码(你不介意吧 ^_^) 后记:就在我写这篇博文的时候,神奇的D牛还在优化代码,据说他的代码已经可以在200毫秒左右执行完了!膜拜之~等待明天他的解题报告!

Tags: . 14,608 views

D大叫我要勤更新,好吧,再贴一个HDU的ACM题,这道很简单,相当简单,小牛以上的都请路过 原题:http://acm.hdu.edu.cn/showproblem.php?pid=1012 其实就是用它给出的一个公式计算e的近似值,好了,贴代码,顺便透露一下,下一篇日志,我将写一下上次热烈讨论的HDU 1042 ,尽请期待~ 01 /* ******************* 02 *Author: Wang Runzhen  03 *Date:   2010.2.9 04 ******************** */ 05 #include<stdio.h> 06 int main(void) 07 { 08     int i,j,k=1; 09     double e=0.0; 10     printf(“n e\n– ———–\n“); 11  12     for(i=0;i<10;i++){ 13         for(j=1;j<=i;j++) 14         { 15             k*=j; 16    […]

Tags: . 4,839 views
2009/08/24

Description
An army of ants walk on a horizontal pole of length l cm, each with a constant speed of…

Tags: ,. 5,517 views

昨晚心血来潮,竟然跑到POJ上做了一道题,之前我只做过NO.1001,靠,别笑我………..

做了1852的Ant(蚂…

Tags: ,. 4,298 views
2009/08/20

今天猛然间看到 pivot可以这样优化:取开始(beg)、中间(mid)、结束(end)的中间值

用我讨厌的数学公式表达…

Tags: ,,. 3,430 views
2009/08/19

前两天,KC同学问了我关于快速排序的问题,可惜我忘得差不多了,没帮上什么忙,惭愧惭愧。于是就潜心的复习…

Tags: ,,,. 5,427 views
2009/08/14

排序算法演示

Tags: ,. 3,839 views

二叉树 代码

Tags: ,. 8,006 views

这是上实验课的时候做的,代码里一个多项式的结构体定义用了两个链表,真的的很烦,不过这不能怪我, 我是严格按照我国著名大学、著名教授——清华大学严蔚敏老师的《数据结构》里定义的数据结构照抄的 我个人觉得这种写法很烦,完全没有必要,把简单的一个数据结构复杂化了. 发了一些牢骚,下面贴代码. 001 #include<stdio.h> 002 #include<malloc.h> 003 typedef struct Node 004 { 005     int xs; 006  007     int zs; 008     struct Node *next; 009 }; 010 typedef struct LinkList 011 { 012    struct Node *front,*rear; 013  014 }; 015 //Initial 016 void InitList(struct LinkList *p) 017 { 018    p->front=(struct Node*)malloc(sizeof(struct Node)); 019    p->front->next=NULL; 020    p->rear=p->front; 021 } 022 //Push […]

Tags: ,,. 2,723 views

最近比较忙,琐事非常多,今天终于抽出时间完成了AOV网,贴出来与大家分享~~ 001 /* 002 * Author: Wang Runzhen 003 * Date  : 2009年8月14日 004 */ 005  006 #include<iostream> 007 #include<fstream> 008 using namespace std; 009 const int MAX=7; 010  011 //Creat a Directed  Acycline Graph 012 struct Graph 013 { 014     char vex[MAX]; 015  016     int relate[MAX][MAX]; 017 }; 018  019 void CreatGraph(Graph *g) 020 { 021     int i,j; 022     ifstream in(“AOV.txt”); 023     for(i=0;i<MAX;i++) […]

Tags: ,,,. 4,861 views

欢迎各位与我交流讨论~~    /*     *Author : Wang Runzhen     *Date   : 2009年8月14日    */ 001 #include<iostream> 002 #include<fstream> 003  004 using namespace std; 005 const int MAX=20; 006 “>///////////////////////////////////////////////////////////////////////////////////// 007 struct Graph 008 { 009     char vertex[MAX];//save user’s data 010     int relate[MAX][MAX]; 011     int vnum; 012 }; 013 //初始化图 014 Graph * CreatGraph() 015 { 016     Graph *g=new Graph; […]

Tags: ,. 3,127 views