久久久久久狠狠丁香,一本色道久久88精品综合,久久久久久一区国产精品

hdu 2835

2009年8月12日

題目鏈接：HDU 2835 Operating system

分類：OS中cache置換算法的應(yīng)用

題目分析與算法原型
         這是今天剛做的一道杭電的OJ上的其他多校聯(lián)合舉辦的暑期練習(xí)賽上的一道題，這是第一題，不過也是通過比較少的題目之一。題目大意就是給你一個(gè)Cache（容量已知）然后給你一系列的訪問頁面的序號(hào)（可重復(fù)，即同一頁面可多次訪問），然后讓你組織一個(gè)替換算法，使得這一趟下來，讓你求頁面寫進(jìn)Cache的最小次數(shù)（其實(shí)也就是使得訪問的命中率最高），學(xué)過操作系統(tǒng)的都了解，現(xiàn)實(shí)情況下比較采用的是LRU（最近最少使用頁面替換算法）算法，不能使用那種理想的最優(yōu)替換算法，因?yàn)槲覀儾恢啦僮飨到y(tǒng)以后要訪問的頁面順序，所以不可能做全局預(yù)測(cè)，然而，這道題目卻只能用這種算法，因?yàn)槲覀円呀?jīng)知道所有要訪問的頁面的序號(hào)，所以我們可以知道當(dāng)前時(shí)間開始，那個(gè)頁面下次訪問到的時(shí)間間隔多長(zhǎng)都能計(jì)算出來，這個(gè)時(shí)候我們每次替換的時(shí)候就應(yīng)該選擇間隔最長(zhǎng)的那個(gè)頁面。

        大體實(shí)現(xiàn)如下：
        先創(chuàng)建一個(gè)優(yōu)先隊(duì)列（用最大堆維護(hù)，保證隊(duì)頭元素的關(guān)鍵值最大），每個(gè)頁面的頁面好作為堆元素的唯一編號(hào)，每個(gè)頁面的下次訪問時(shí)間，作為關(guān)鍵字。

        1.若當(dāng)前的頁面第一次出現(xiàn)，且cache容量未滿，則將進(jìn)入隊(duì)列，訪問次數(shù)加1
       2.若當(dāng)前的頁面第一次出現(xiàn)，且cache容量已經(jīng)滿了，此時(shí)就用它替換隊(duì)列中關(guān)鍵值最大的那個(gè)，訪問次數(shù)加1
       3.若當(dāng)前的頁面已經(jīng)在Cache里面，則更新該隊(duì)列中此頁面的下次訪問的時(shí)間

關(guān)于如何計(jì)算每個(gè)頁面的下次訪問時(shí)間，方法可以有多種，你可以將輸入的頁面按其輸入的頁面號(hào)從小到大一級(jí)排序，按其訪問的時(shí)間二級(jí)排序，這樣子同頁面編號(hào)的都在一起了，可以方便計(jì)算。其實(shí)，還有更快的方法，可以不用排序，直接以o(n)的時(shí)間復(fù)雜度計(jì)算每個(gè)頁面的下次訪問時(shí)間，開兩個(gè)數(shù)組，next[]和qian[]，假設(shè)當(dāng)前訪問時(shí)間（既數(shù)組下標(biāo)）為i的頁面編號(hào)為m[i]的頁面的下次的訪問時(shí)間用next[i]記錄（其中m[]數(shù)組記錄的是所有要訪問的頁面），那么qian[m[i]]表示在i之前（0到i-1）的離i最近的編號(hào)也為m[i]的頁面的時(shí)間（其實(shí)就是該頁上次的訪問時(shí)間），那么每到一個(gè)i，就更新前次m[i]頁面的的下次訪問時(shí)間，有next[qian[m[i]]]=i,然后再更新qian[m[i]]=i;這樣子，一遍循環(huán)下來就可以算出任何位置上的所有頁面的下次訪問時(shí)間了。

Code：

1

#include<stdio.h>
2

#include<string.h>
3

#define len 100005
4

int c,n,b,m[len],next[len],min,count,place[len],cnt[len],qian[len];
6

bool flag[len];
7

struct node
9

{
10

int key,num;//其中num是唯一標(biāo)記隊(duì)列元素的編號(hào)
11

}queue[10010];
12

void down_min_heap(int n,int h)//n表示堆元素的個(gè)數(shù)，從0開始編號(hào),從h開始往下調(diào)整
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

queue[i]=queue[j];
26

i=j;
27

j=2*i+1;
28

}
29

}
30

queue[i]=temp;
31

place[temp.num]=i;
32

}
33

void up_min_heap(int s) //s表示最后一個(gè)的編號(hào),即是n-1,其中n表示堆元素的個(gè)數(shù)
34

{
35

while (s>0&&queue[s].key>queue[(s-1)/2].key) //從s開始往上調(diào)整
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

}
45

void push(node x) //count(全局變量)表示隊(duì)列中元素的個(gè)數(shù)，隊(duì)列元素從0開始編號(hào)
46

{
47

queue[count]=x;
48

place[x.num]=count;
49

count++;
50

up_min_heap(count-1);
51

}
52

node 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

}
61

int 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

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未滿，加進(jìn)來
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 閱讀(554) 評(píng)論(1) 編輯收藏引用

評(píng)論

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

請(qǐng)問如果是使用stl的priority_queue 有什么辦法可以處理元素已經(jīng)在隊(duì)列中然后進(jìn)行替代的過程。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

hdu 2835

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜