久久久无码一区二区三区,国产精品99久久久久久人,99精品国产99久久久久久97

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

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是唯一標記隊列元素的編號
11

}queue[10010];
12

void 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

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表示最后一個的編號,即是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

}
45

void push(node x) //count(全局變量)表示隊列中元素的個數，隊列元素從0開始編號
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未滿，加進來
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) 評論(1) 編輯收藏引用

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

hdu 2835

評論

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理