算法之LRU和LFU算法

77 阅读 0 评论 51 点赞

我是靠谱客的博主完美哈密瓜，最近开发中收集的这篇文章主要介绍算法之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