算法之LRU和LFU算法

57 阅读 0 评论 38 点赞

我是靠谱客的博主尊敬河马，最近开发中收集的这篇文章主要介绍算法之LRU和LFU算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

评价一个缓存算法好坏的标准主要有两个，一是命中率要高，二是算法要容易实现。当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。FIFO虽然实现很简单，但是命中率很低，实际上也很少使用这种算法。

1、LRU

最近最少使用，淘汰最近不使用的页面
LRU表示最近最久未使用算法，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。即LRU算法是与每个页面最后使用的时间有关的。
1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

以下为利用双向链表和HashMap实现LRU的代码,算法时间复杂度为O（1）（备注：其实也可以直接使用LinkedHashMap实现LRU）

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;
public class LRUCache<K, V> {
//存储的单位元素
class CacheNode{
Object key;
Object value;
CacheNode pre;//用于构造双向链表
CacheNode next;
public CacheNode(Object key，Object value){
this.key = key;
this.value = value;
}
public CacheNode(){
}
}
private int currentCacheSize;//当前容量
private int CacheCapcity;//最大容量
private HashMap<K,CacheNode> caches;
private CacheNode first;//指向链表头结点
private CacheNode last;//指向链表尾节点
public LRUCache(int size){
currentCacheSize = 0;
this.CacheCapcity = size;
caches = new HashMap<K,CacheNode>(size);
}
//添加新的节点时，放入链表头部
public void put(K k,V v){
CacheNode node = caches.get(k);
if(node == null){
if(caches.size() >= CacheCapcity){
removeLast();
caches.remove(last.key);
}
node = new CacheNode(k,v);
caches.put(k, node);
InsetToFirst(node);
}else{
moveToFirst(node);
}
currentCacheSize = caches.size();
}
//访问某个元素
public Object
get(K k){
CacheNode node = caches.get(k);
if(node == null){
return null;
}
moveToFirst(node);
return node.value;
}
//将链表中的某个元素移到链表头部
private void moveToFirst(CacheNode node){
CacheNode prenode = node.pre;
CacheNode nextnode = node.next;
if(prenode == null && nextnode == null){
return;
}else if(nextnode == null){
InsetToFirst(node);
return;
}else if(prenode == null){
return;
}else{
prenode.next = nextnode;
nextnode.pre = prenode;
InsetToFirst(node);
}
}
//插入某个元素到链表头部
private void InsetToFirst(CacheNode node){
if(first == null || last == null){
first = node;
last = node;
}else{
node.next = first;
first.pre = node;
}
}
//删除某个尾节点元素
private void removeLast(){
if(last != null){
last = last.pre;
if(last == null){
first = null;
}else{
last.next = null;
}
}
}
//清空所有元素
public void clear(){
first = null;
last = null;
caches.clear();
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
CacheNode node = first;
while(node != null){
sb.append(String.format("%s:%s ", node.key,node.value));
node = node.next;
}
return sb.toString();
}
public static void main(String[] args) {
LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3);
lru.put(1, "a");
// 1:a
System.out.println(lru.toString());
lru.put(2, "b");
// 2:b 1:a 
System.out.println(lru.toString());
lru.put(3, "c");
// 3:c 2:b 1:a 
System.out.println(lru.toString());
lru.put(4, "d");
// 4:d 3:c 2:b

System.out.println(lru.toString());
}
}

1、LFU

最近使用次数最少，淘汰使用次数最少的页面
LFU(最不经常使用算法)算法根据数据的历史访问频率来淘汰数据，其原理是如果数据过去被访问次数越多，将来被访问的几概率相对比较高。LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。
具体算法如下：
1. 新加入数据插入到队列尾部（因为引用计数为1）；
2. 队列中的数据被访问后，引用计数增加，队列重新排序；
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除；

以下为实现LFU的代码,算法时间复杂度为O（1）,强烈推荐：
使用了两层链表，第一层链表按照历史访问频率排序，第二层链表按照访问时间排序，这样在插入节点的时候就不需要遍历操作
https://www.jianshu.com/p/437f53341f67