页面置换算法 - FIFO、LFU、LRU
?
?
緩存算法（頁面置換算法）-FIFO. LFU. LRU
在前一篇文章中通過leetcode的一道題目了解了LRU算法的具體設計思路，下面繼續(xù)來探討一下另外兩種常見的Cache算法：FIFO. LFU
1.FIFO算法
FIFO（First in First out），先進先出. 其實在操作系統(tǒng)的設計理念中很多地方都利用到了先進先出的思想，比如作業(yè)調(diào)度（先來先服務），為什么這個原則在很多地方都會用到呢？因為這個原則簡單. 且符合人們的慣性思維，具備公平性，并且實現(xiàn)起來簡單，直接使用數(shù)據(jù)結(jié)構(gòu)中的隊列即可實現(xiàn).
在FIFO Cache設計中，核心原則就是：如果一個數(shù)據(jù)最先進入緩存中，則應該最早淘汰掉. 也就是說，當緩存滿的時候，應當把最先進入緩存的數(shù)據(jù)給淘汰掉. 在FIFO Cache中應該支持以下操作;
get(key)：如果Cache中存在該key，則返回對應的value值，否則，返回-1；
set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則將該key插入到到Cache中，若Cache已滿，則淘汰最早進入Cache的數(shù)據(jù).
舉個例子：假如Cache大小為3，訪問數(shù)據(jù)序列為set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)
則Cache中的數(shù)據(jù)變化為：
(1,1) set(1,1)
(1,1) (2,2) set(2,2)
(1,1) (2,2) (3,3) set(3,3)
(2,2) (3,3) (4,4) set(4,4)
(2,2) (3,3) (4,4) get(2)
(3,3) (4,4) (5,5) set(5,5)
那么利用什么數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)呢？
下面提供一種實現(xiàn)思路：
利用一個雙向鏈表保存數(shù)據(jù)，當來了新的數(shù)據(jù)之后便添加到鏈表末尾，如果Cache存滿數(shù)據(jù)，則把鏈表頭部數(shù)據(jù)刪除，然后把新的數(shù)據(jù)添加到鏈表末尾. 在訪問數(shù)據(jù)的時候，如果在Cache中存在該數(shù)據(jù)的話，則返回對應的value值；否則返回-1. 如果想提高訪問效率，可以利用hashmap來保存每個key在鏈表中對應的位置.
#include <bits/stdc++.h>using namespace std;
// FIFO 先進先出原則
class Solution
{
public:
? ?Solution(int si)
? ?{
? ? ? ?_size=si;
? ? ? ?top_idx=0; // 隊列top的下標
? ? ? ?cache.clear();
? ? ? ?exist.clear();
? ?}
? ?int check_page(int k)
? ?{
? ? ? ?if(exist.count(k)>=1) //hit the target
? ? ? ? ? ?return k;
? ? ? ?// not exist on cache
? ? ? ?if(cache.size()<_size)
? ? ? ?{
? ? ? ? ? ?cache.push_back(k);
? ? ? ? ? ?exist.insert(k);
? ? ? ?}
? ? ? ?else // replace
? ? ? ?{
? ? ? ? ? ?exist.erase(cache[top_idx]);
? ? ? ? ? ?exist.insert(k);
? ? ? ? ? ?cache[top_idx]=k;
? ? ? ? ? ?++top_idx;
? ? ? ? ? ?top_idx%=_size;
? ? ? ?}
? ? ? ?return -1;
? ?}
private:
? ?int _size,top_idx;
? ?vector<int> cache;// 模擬隊列
? ?set<int> exist;
};
/**<
改進：
1.如果頁面駐留集（cache）的大小很小的話，沒必要使用set來判斷是否存在于駐留集中，直接掃一遍來查找，節(jié)約了空間
*/
int main()
{
? ?freopen("H:\\Code_Fantasy\\in.txt","r",stdin);
? ?int n,page_number;
? ?while(cin>>n)
? ?{
? ? ? ?int miss=0;
? ? ? ?Solution solution(3); // set the cache size
? ? ? ?for(int i=0;i<n;++i)
? ? ? ?{
? ? ? ? ? ?cin>>page_number;
? ? ? ? ? ?if(solution.check_page(page_number)==-1)
? ? ? ? ? ? ? ?++miss;
? ? ? ?}
? ? ? ?cout<<"Total missing page: "<<miss<<endl;
? ? ? ?cout<<"The shooting rate is: "<<1.0-(1.*miss/n)<<endl;
? ? ? ?cout<<"=====================================End."<<endl;
? ?}
? ?return 0;
}
/*
12
1 2 3 4 1 2 5 1 2 3 4 5
17
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
*/
2.LFU算法
LFU（Least Frequently Used）最近最少使用算法. 它是基于“如果一個數(shù)據(jù)在最近一段時間內(nèi)使用次數(shù)很少，那么在將來一段時間內(nèi)被使用的可能性也很小”的思路.
注意LFU和LRU算法的不同之處，LRU的淘汰規(guī)則是基于訪問時間，而LFU是基于訪問次數(shù)的. 舉個簡單的例子：
假設緩存大小為3，數(shù)據(jù)訪問序列為set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，
則在set(4,4)時對于LFU算法應該淘汰(3,3)，而LRU應該淘汰(1,1).
那么LFU Cache應該支持的操作為：
get(key)：如果Cache中存在該key，則返回對應的value值，否則，返回-1；
set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則將該key插入到到Cache中，若Cache已滿，則淘汰最少訪問的數(shù)據(jù).
為了能夠淘汰最少使用的數(shù)據(jù)，因此LFU算法最簡單的一種設計思路就是：利用一個數(shù)組存儲數(shù)據(jù)項，用hashmap存儲每個數(shù)據(jù)項在數(shù)組中對應的位置，然后為每個數(shù)據(jù)項設計一個訪問頻次，當數(shù)據(jù)項被命中時，訪問頻次自增，在淘汰的時候淘汰訪問頻次最少的數(shù)據(jù). 這樣一來的話，在插入數(shù)據(jù)和訪問數(shù)據(jù)的時候都能達到O(1)的時間復雜度，在淘汰數(shù)據(jù)的時候，通過選擇算法得到應該淘汰的數(shù)據(jù)項在數(shù)組中的索引，并將該索引位置的內(nèi)容替換為新來的數(shù)據(jù)內(nèi)容即可，這樣的話，淘汰數(shù)據(jù)的操作時間復雜度為O(n).
另外還有一種實現(xiàn)思路就是利用小頂堆+hashmap，小頂堆插入. 刪除操作都能達到O(logn)時間復雜度，因此效率相比第一種實現(xiàn)方法更加高效.
如果哪位朋友有更高效的實現(xiàn)方式（比如O(1)時間復雜度），不妨探討一下，不勝感激.
3.LRU算法
LRU算法的原理以及實現(xiàn)在前一篇博文中已經(jīng)談到，在此不進行贅述：
http://www.cnblogs.com/dolphin0520/p/3741519.html
參考鏈接：http://blog.csdn.net/hexinuaa/article/details/6630384
http://blog.csdn.net/beiyetengqing/article/details/7855933
http://blog.csdn.net/alexander_xfl/article/details/12993565
http://outofmemory.cn/wr/?u=http%3A%2F%2Fblog.csdn.net%2Fyunhua_lee%2Farticle%2Fdetails%2F7648549
?
/*** -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* ? ? ? Author: crazyacking
* ? ? ? Date ?: 2016-03-15-20.01
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
struct Node
{
? ?int key,value;
? ?Node(int k,int v):key(k),value(v){}
};
class LRUCache
{
private:
? ?int max_size;
? ?list<Node> cacheList;
? ?unordered_map<int,list<Node>::iterator> mp;
public:
? ?LRUCache(int capacity) {max_size=capacity;}
? ?int get(int key)
? ?{
? ? ? ?if(mp.find(key)==mp.end()) // 未命中
? ? ? ? ? ?return -1;
? ? ? ?else
? ? ? ?{
? ? ? ? ? ?auto list_it=mp[key];
? ? ? ? ? ?Node node(key,list_it->value);
? ? ? ? ? ?cacheList.erase(list_it);
? ? ? ? ? ?cacheList.push_front(node);
? ? ? ? ? ?mp[key]=cacheList.begin();
? ? ? ? ? ?return node.value;
? ? ? ?}
? ?}
? ?void set(int key, int value)
? ?{
? ? ? ?auto it=mp.find(key);
? ? ? ?if(it==mp.end()) // 未命中
? ? ? ?{
? ? ? ? ? ?if(cacheList.size()>=max_size) // 駐留集已滿
? ? ? ? ? ?{
? ? ? ? ? ? ? ?mp.erase(cacheList.back().key);
? ? ? ? ? ? ? ?cacheList.pop_back();
? ? ? ? ? ?}
? ? ? ? ? ?Node node(key,value);
? ? ? ? ? ?cacheList.push_front(node);
? ? ? ? ? ?mp[key]=cacheList.begin();
? ? ? ?}
? ? ? ?else // 命中，將加入的結(jié)點置于鏈表頭部，表示最近一次使用
? ? ? ?{
? ? ? ? ? ?cacheList.erase(mp[key]);
? ? ? ? ? ?Node node(key,value);
? ? ? ? ? ?cacheList.push_front(node);
? ? ? ? ? ?mp[key]=cacheList.begin();
? ? ? ?}
? ?}
};
int main()
{
? ?LRUCache cache(3);
? ?cache.set(1,1);
? ?cache.set(2,2);
? ?cache.set(3,3);
? ?cache.set(4,4);
? ?cout<<cache.get(4)<<endl;
? ?cout<<cache.get(3)<<endl;
? ?cout<<cache.get(2)<<endl;
? ?cout<<cache.get(1)<<endl;
? ?cache.set(5,5);
? ?cout<<cache.get(1)<<endl;
? ?cout<<cache.get(2)<<endl;
? ?cout<<cache.get(3)<<endl;
? ?cout<<cache.get(4)<<endl;
? ?cout<<cache.get(5)<<endl;
? ?return 0;
}
/*
*/
--------------------------------------------------------- End.
轉(zhuǎn)載請注明：http://www.cnblogs.com/crazyacking/
總結(jié)
以上是生活随笔為你收集整理的页面置换算法 - FIFO、LFU、LRU的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： RTC系统【转】
- 下一篇： ViewPager详解(一)——View