页面置换算法之LRU算法
2019-04-16 本文已影响0人
指尖上的榴莲
一.页面置换算法
三种常见的页面置换算法:FIFO、LFU、LRU
参考：
缓存算法（页面置换算法）-FIFO、LFU、LRU
二.LRU算法
1.什么是LRU算法
LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
2.例子
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1
3.设计思路
如果让我们设计一个LRU Cache的数据结构，它应该支持两个操作：
- set(key, value):若缓存中存在key，则替换其value，否则将(key,value)插入缓存中，如果插入时缓存已满，则必须把最近最久未使用的元素从缓存中删除。
- get(key):若缓存中存在key，则返回对应的value，否则返回-1。
那么应该采用什么数据结构来实现LRU算法呢？
3.1设计1
一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个最大时间戳，其设计要点如下：
- set(key, value):如果key在数组中存在，则先重置对应的value值，然后更新key的时间戳为当前cache中的最大时间戳+1；若果key在数组中不存在，若缓存满，在整个缓存中查找时间戳最小的key，其存储位置作为新key的存储位置，设置key的时间戳为最大时间戳+1；若缓存未满，存储位置为第一个空闲位置，设置key的时间戳为最大时间戳+1。
- get(key):如果key在数组中存在，更新key的时间戳为当前cache中最大时间戳+1，并返回对应的value值；如果不存在，则返回-1。
3.2设计2
另一种是采用hashmap+双向链表的数据结构，其设计要点如下：
- set(key, value):如果key在hashmap中存在，则先重置对应的value值，然后将key所在的节点移动到双向链表的表头；若果key在hashmap中不存在，则新建一个节点，并将节点放到链表的头部。若cache已满，将双向链表最后一个节点删除即可。
- get(key):如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。
4.实现
对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get操作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get操作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get操作的时间复杂度只需O(1)，下面给出设计2的具体实现。
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private Map<Integer, CacheNode> cache;
private int size;
private int capacity;
private CacheNode head, tail;
public LRUCache(int capacity){
cache = new HashMap<Integer, CacheNode>();
this.size = 0;
this.capacity = capacity;
head = new CacheNode();
head.pre = null;
tail = new CacheNode();
tail.next = null;
head.next = tail;
tail.pre = head;
}
public void set(int key, int value){
CacheNode node = cache.get(key);
if (node == null){
CacheNode newNode = new CacheNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++size;
if (size > capacity){
CacheNode tail = this.popTail();
cache.remove(tail.key);
--size;
}
} else {
node.value = value;
this.moveToHead(node);
}
System.out.println(String.format("set(%d, %d): ", key, value) + this.toString() );
}
public int get(int key){
CacheNode node = cache.get(key);
if (node == null){
return -1;
}
this.moveToHead(node);
System.out.println(String.format("get(%d): ", key) + this.toString());
return node.value;
}
/**
* 只在头节点之后创建新节点
* @param node
*/
private void addNode(CacheNode node){
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private CacheNode popTail(){
CacheNode node = tail.pre;
this.removeNode(node);
return node;
}
private void removeNode(CacheNode node){
CacheNode preNode = node.pre;
CacheNode nextNode = node.next;
preNode.next = nextNode;
nextNode.pre = preNode;
}
private void moveToHead(CacheNode node){
this.removeNode(node);
this.addNode(node);
}
@Override
public String toString() {
StringBuffer buffer = new StringBuffer();
CacheNode node = head.next;
while (node.next != null){
buffer.append(String.format("(%d,%d) ", node.key, node.value));
node = node.next;
}
return buffer.toString();
}
class CacheNode{
CacheNode pre;
CacheNode next;
Integer key;
Integer value;
}
public static void main(String[] args) {
LRUCache lru = new LRUCache(3);
lru.set(4, 4);
lru.set(3, 3);
lru.get(4);
lru.set(2, 2);
lru.get(3);
lru.set(1, 1);
lru.set(4, 4);
lru.set(2, 2);
}
}
运行结果为：
set(4, 4): (4,4)
set(3, 3): (3,3) (4,4)
get(4): (4,4) (3,3)
set(2, 2): (2,2) (4,4) (3,3)
get(3): (3,3) (2,2) (4,4)
set(1, 1): (1,1) (3,3) (2,2)
set(4, 4): (4,4) (1,1) (3,3)
set(2, 2): (2,2) (4,4) (1,1)
