页面置换算 - FIFO、LFU、LRU

本文主要是介绍页面置换算 - FIFO、LFU、LRU，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

缓存算法（页面置换算法）-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)时间复杂度），不妨探讨一下，不胜感激。