缓存算法（页面置换算法）-FIFO. LFU. LRU
在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路，下面继续来探讨一下另外两种常见的Cache算法：FIFO. LFU
1.FIFO算法
FIFO（First in First out），先进先出. 其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单. 且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现.
在FIFO Cache设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉. 也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉. 在FIFO Cache中应该支持以下操作;
get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；
set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最早进入Cache的数据.
举个例子：假如Cache大小为3，访问数据序列为set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)
则Cache中的数据变化为：
(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)
那么利用什么数据结构来实现呢？
下面提供一种实现思路：
利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾. 在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的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来判断是否存在于驻留集中，直接扫一遍来查找，节约了空间 */ 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）最近最少使用算法. 它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路.
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的. 举个简单的例子：
假设缓存大小为3，数据访问序列为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已满，则淘汰最少访问的数据.
为了能够淘汰最少使用的数据，因此LFU算法最简单的一种设计思路就是：利用一个数组存储数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据. 这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n).
另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入. 删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效.
如果哪位朋友有更高效的实现方式（比如O(1)时间复杂度），不妨探讨一下，不胜感激.
3.LRU算法
LRU算法的原理以及实现在前一篇博文中已经谈到，在此不进行赘述：
参考链接：
/** * ----------------------------------------------------------------- * 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 // 命中，将加入的结点置于链表头部，表示最近一次使用 { 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.
转载请注明：http://www.cnblogs.com/crazyacking/