操作系统-1-存储管理之LFU页面置换算法(leetcode460)
我只是一个码农 人气:2LFU缓存
题目：请你为 最不经常使用（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 }
加载全部内容