鸡西房地产:操作系统-1-存储治理之LFU页面置换算法(leetcode460)

admin/2020-04-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 }

 

,

进入sunbet官网手机

欢迎进入进入sunbet官网手机!Sunbet 申博提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet客户端下载、Sunbet代理合作等业务。

TAG:
阅读:
广告 330*360
广告 330*360
Sunbet_进入申博sunbet官网
微信二维码扫一扫
关注微信公众号
新闻自媒体 Copyright © 2002-2019 Sunbet 版权所有
二维码
意见反馈 二维码