hdu 2835

2009年8月12日

题目链接:HDU 2835 Operating system  

分类:OS中cache置换算法的应用

题目分析与算法原型
         这是 今天刚做的一道杭电的OJ上的其他多校联合举办的暑期练习赛上的一道题,这是第一题,不过也是通过比较少的题目之一。题目大意就是给你一个Cache(容量已知)然后给你一系列的访问页面的序号(可重复,即同一页面可多次访问),然后让你组织一个替换算法,使得这一趟下来,让你求页面写进Cache的最小次数(其实也就是使得访问的命中率最高),学过操作系统的都了解,现实情况下比较采用的是LRU(最近最少使用页面替换算法)算法,不能使用那种理想的最优替换算法,因为我们不知道操作系统以后要访问的页面顺序,所以不可能做全局预测,然而,这道题目却只能用这种算法,因为我们已经知道所有要访问的页面的序号,所以我们可以知道当前时间开始,那个页面下次访问到的时间间隔多长都能计算出来,这个时候我们每次替换的时候就应该选择间隔最长的那个页面。

        大体实现如下:
        先创建一个优先队列(用最大堆维护,保证队头元素的关键值最大),每个页面的页面好作为堆元素的唯一编号,每个页面的下次访问时间,作为关键字。

        1.若当前的页面第一次出现,且cache容量未满,则将进入队列,访问次数加1
       2.若当前的页面第一次出现,且cache容量已经满了,此时就用它替换队列中关键值最大的那个,访问次数加1
       3.若当前的页面已经在Cache里面,则更新该队列中此页面的下次访问的时间
      
关于如何计算每个页面的下次访问时间,方法可以有多种,你可以将输入的页面按其输入的页面号从小到大一级排序,按其访问的时间二级排序,这样子同页面编号的都在一起了,可以方便计算。其实,还有更快的方法,可以不用排序,直接以o(n)的时间复杂度计算每个页面的下次访问时间,开两个数组,next[]和qian[],假设当前访问时间(既数组下标)为i的页面编号为m[i]的页面的下次的访问时间用next[i]记录(其中m[]数组记录的是所有要访问的页面),那么qian[m[i]]表示在i之前(0到i-1)的离i最近的编号也为m[i]的页面的时间(其实就是该页上次的访问时间),那么每到一个i,就更新前次m[i]页面的的下次访问时间,有next[qian[m[i]]]=i,然后再更新qian[m[i]]=i;这样子,一遍循环下来就可以算出任何位置上的所有页面的下次访问时间了。

Code:

  1
#include<stdio.h>
  2#include<string.h>
  3#define len 100005
  4
  5int c,n,b,m[len],next[len],min,count,place[len],cnt[len],qian[len];
  6bool flag[len];
  7
  8struct node
  9{
 10    int key,num;//其中num是唯一标记队列元素的编号
 11}
queue[10010];
 12
 13void down_min_heap(int n,int h)//n表示堆元素的个数,从0开始编号,从h开始往下调整
 14{
 15    int i=h,j=2*i+1;
 16    node temp=queue[i];
 17    while(j<n)
 18    {
 19        if(j<n-1&&queue[j].key<queue[j+1].key)j++;//若右孩子存在,且右孩子比较大,取右
 20        if(temp.key>queue[j].key)break;
 21        else
 22        {
 23            place[queue[j].num]=i;
 24
 25            queue[i]=queue[j];
 26            i=j;
 27            j=2*i+1;
 28        }

 29    }

 30    queue[i]=temp;
 31    place[temp.num]=i;
 32}

 33void up_min_heap(int s)    //s表示最后一个的编号,即是n-1,其中n表示堆元素的个数
 34{
 35    while (s>0&&queue[s].key>queue[(s-1)/2].key)     //从s开始往上调整
 36    
 37        place[queue[s].num]=(s-1)/2;
 38        place[queue[(s-1)/2].num]=s;
 39        node tt=queue[s];
 40        queue[s]=queue[(s-1)/2];
 41        queue[(s-1)/2]=tt;
 42        s=(s-1)/2
 43    }

 44}

 45void push(node x)  //count(全局变量)表示队列中元素的个数,队列元素从0开始编号
 46{
 47    queue[count]=x;
 48    place[x.num]=count;
 49    count++;
 50    up_min_heap(count-1);
 51}

 52node pop()
 53{
 54    node res=queue[0];
 55    queue[0]=queue[count-1];
 56    place[queue[count-1].num]=0;
 57    count--;
 58    down_min_heap(count,0);
 59    return res;
 60}

 61int main()
 62{
 63    int i;
 64    while(scanf("%d%d%d",&c,&n,&b)!=EOF)
 65    {
 66        memset(flag,false,sizeof(flag));
 67        for(i=0;i<b;i++)
 68        {
 69            qian[i]=-1;
 70            next[i]=b;
 71        }

 72        for(i=0;i<b;i++)
 73        {
 74            scanf("%d",&m[i]);
 75
 76            if(qian[m[i]]!=-1)next[qian[m[i]]]=i;
 77            qian[m[i]]=i;
 78        }

 79        if(b==0)printf("0\n");
 80        else
 81        {
 82            min=0;
 83            count=0;
 84            for(i=0;i<b;i++)
 85            {
 86                if(flag[m[i]]==false)//cache中不存在
 87                {
 88                    if(count<c)//cache未满,加进来
 89                    {    
 90                        node x;
 91                        flag[m[i]]=true;
 92                        x.key=next[i];
 93                        x.num=m[i];
 94                        push(x);
 95                        min++;
 96                    }

 97                    else if(count==c)//cache满了,需要替换
 98                    {
 99                        node tt,x=pop();
100                        flag[x.num]=false;
101                        flag[m[i]]=true;
102                        tt.key=next[i];
103                        tt.num=m[i];
104                        push(tt);
105                        min++;
106                    }

107                }

108                else 
109                {
110                    int kk=place[m[i]];
111                    queue[kk].key=next[i];
112                    up_min_heap(kk);
113                }

114            }

115            printf("%d\n",min);
116        }

117    }

118    return 1;
119}

posted on 2009-08-12 19:00 蜗牛也Coding 阅读(531) 评论(1)  编辑 收藏 引用

评论

# re: hdu 2835 2010-01-26 13:27 makejing

请问如果是使用stl的priority_queue 有什么办法可以处理元素已经在队列中然后进行替代的过程。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜