操作系统-1-存储管理之LFU页面置换算法(leetcode460)

2020 年 4 月 11 日
筆記

LFU缓存

题目：请你为最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
　　　　get(key) – 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
　　　　put(key, value) – 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。

　　　　　　　　　　　在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最近最少使用的键。
　　　「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

示例：　　
　　　LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

　　   cache.put(1, 1);
　　   cache.put(2, 2);
　　   cache.get(1);       // 返回 1
　　   cache.put(3, 3);    // 去除 key 2
　　   cache.get(2);       // 返回 -1 (未找到key 2)　　
　　   cache.get(3);       // 返回 3
　　   cache.put(4, 4);    // 去除 key 1
　　   cache.get(1);       // 返回 -1 (未找到 key 1)
　　   cache.get(3);       // 返回 3
　　   cache.get(4);       // 返回 4

代码：

 1 class LFUCache {   2   3     public LFUCache(int capacity) {   4   5     }   6   7     public int get(int key) {   8   9     }  10  11     public void put(int key, int value) {  12  13     }  14 }  15  16 /**  17  * Your LFUCache object will be instantiated and called as such:  18  * LFUCache obj = new LFUCache(capacity);  19  * int param_1 = obj.get(key);  20  * obj.put(key,value);  21  */

LFU页面置换算法(最不经常使用算法)

　　原理：

　　　　选择到当前时间为止被访问次数最少的页面被置换；
　　　　每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；
　　　　发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；

　　　　如图：图中的页面为三页，依次向存储中加入432143543215这些数字。

　　　　　　　而存储空间只能存储三个页面，所以会按照上述规则不断淘汰已经存储在页面中的数字。

解题思路(logN的思路)：

　　　知道了LFU的置换规则后，由于此题需要存储的是key和value,所以

　　　　　　首先，需要建一个类node，存放四样东西，key,value,times(访问计数器)，id(进入存储空间的自然顺序)

　　　　　　其次，选择一种合适的数据结构来解决存储优先级问题，此处我们采用内部是小顶堆的PriorityQueue优先级队列用来

　　　　　　　　　实现times最小的元素在队头,如果times相等，则比较先后入队的自然顺序id。

　　　　　　　　　但是我们会在让新元素入队之前可能会删除队列中指定元素，当然可以去遍历队列，但是这样太慢了

　　　　　　　　　我们可以再用一种HashMap的数据集合用来存储节点，以便快速通过node的key来得到整个node。

　　　　　　最后，便是处理逻辑关系，写题目要求的get,put方法了

解题代码详解(logN)：

  1 public class node implements Comparable<node>{    2     private int Key;//键    3     private int Value;//值    4     private int Times;//访问计数器    5     private int Id;//自然入队顺序标记，若访问计数器值相同，则先淘汰id小的那个    6     node() {}    7     node(int key, int value, int id) {    8         this.Key = key;    9         this.Value = value;   10         this.Id = id;   11         this.Times = 1;   12     }   13     public int getKey() {   14         return Key;   15     }   16   17     public void setKey(int Key) {   18         this.Key = Key;   19     }   20   21     public int getValue() {   22         return Value;   23     }   24   25     public void setValue(int Value) {   26         this.Value = Value;   27     }   28   29     public int getTimes() {   30         return Times;   31     }   32   33     public void setTimes(int Times) {   34         this.Times = Times;   35     }   36     public int getId() {   37         return Id;   38     }   39   40     public void setId(int id) {   41         this.Id = id;   42     }   43   44     @Override   45     public int compareTo(node o) {   46         //实现times最小的元素在队头,如果times相等，则比较先后入队顺序   47         int Timessub = Times - o.Times;   48         return Timessub == 0 ? this.Id - o.Id: Timessub;   49     }   50 }   51   52 class LFUCache {   53     PriorityQueue<node> KeyValueTimes = new PriorityQueue();//用于实现优先级顺序   54     Map<Integer, node> nodeset;//用于O(1)取出某个具体的node   55     public int Capacity = 0;//我的cache中最大容量   56     public int nownum = 0;//cache的实时元素个数   57     public int id = 0;//每个node的入队自然顺序标记   58   59     public LFUCache(int capacity) {   60         this.Capacity = capacity;//设置cache容量   61         nodeset = new HashMap<Integer, node>(capacity);//用于O(1)取出某个具体的node，容量依然设置为capacity   62     }   63   64     public int get(int key) {   65         if(this.Capacity == 0)//判断容量是否为空，为空则直接返回-1   66             return -1;   67         node nownode = nodeset.get(key);//通过HashMap，快速通过key键快速得到node   68         if (nownode == null) {//如果key这个键没在队列中，则返回-1   69             return -1;   70         }else{   71             KeyValueTimes.remove(nownode);//移除队列中当前的这个node   72             nownode.setTimes(nownode.getTimes()+1);//更新当前这个node的访问次数   73             nownode.setId(id++);//更新自然入队顺序   74             KeyValueTimes.offer(nownode);//再把它放回去   75         }   76         return nownode.getValue();   77     }   78   79     public void put(int key, int value) {   80         if(this.Capacity == 0)//判断容量是否为空,为空则不进行put   81             return;   82         node thisnode = new node(key,value,id++);   83         node oldnode = nodeset.get(key);   84         if(oldnode == null){//队列里不存在这个key   85             if(nownum < this.Capacity){//没装满   86                 KeyValueTimes.offer(thisnode);//在队列里添加新node   87                 nodeset.put(key,thisnode);//在HashMap里添加新node   88                 nownum++;//更新当前cache的元素个数   89             }   90             else{//装满了，需要LRU,最近最先被移除   91                 nodeset.remove(KeyValueTimes.poll().getKey());//移除队列里的队头，移除HashMap对应的那个node   92                 KeyValueTimes.offer(thisnode);//在队列里添加新node   93                 nodeset.put(key,thisnode);//在HashMap里添加新node   94             }   95         }   96         else{//队列里存在这个key   97             thisnode.setTimes(oldnode.getTimes()+1);//将原来键为key的访问次数复制给新的node   98             KeyValueTimes.remove(oldnode);//移除队列里键为key的node，移除HashMap对应的那个node   99             nodeset.remove(oldnode.getKey());  100             KeyValueTimes.offer(thisnode);//在队列里添加新node,这里新的node的value值可能会不一样，所以更新了value  101             nodeset.put(key,thisnode);//在队列里添加新node,这里新的node的value值可能会不一样，所以更新了value  102         }  103     }  104 }