亲宝软件园·资讯

展开

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

我只是一个码农 人气:2

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 }

 

加载全部内容

相关教程
猜你喜欢
用户评论