LRU缓存淘汰算法分析与实现

  1. 云栖社区>
  2. 博客>
  3. 正文

LRU缓存淘汰算法分析与实现

永立 2018-07-12 10:03:04 浏览2463
展开阅读全文

概述

记录一下LRU缓存淘汰算法的实现。

原理

LRU(Least recently used,最近最少使用)缓存算法根据数据最近被访问的情况来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

介绍

下图中,介绍了一个缓存空间为5的缓存队列,当访问数据的顺序是:1,2,3,4,5,6,7,6,4,0时空间中数据的变化过程。
这里写图片描述
可以发现:

  1. 当缓存空间未满时,数据一直往新的空间写;
  2. 当缓存满,并且缓存中没有需要访问的数据时,最先进入缓存的数据被淘汰掉;
  3. 当缓存满,并且缓存中有需要访问的数据时,做了一个数据交换,把访问的数据拿出来,其余数据往下压,最后把访问的数据放到顶部
    在这里,可能有疑问,就是把“数据交换”于“数据完全新增和删除”有什么区别呢?答案是性能,前者是移动指针,后者是更新整个内存空间,后者所花费的系统开销远比前者大得多。

实现

看了算法的介绍,我们想到的数据结构就是链表了。

  • 双向链表的数据结构
    /**
     * 双向链表数据结构
     */
    private class NodePair{
        NodePair frontNode;
        NodePair postNode;
        int data;
    }
  • 逆序查找链表
    /**
     * 根据数据逆序查找链表中是否有此节点,有,则把该点提出来,放到current的位置
     * 当匹配到的时候,返回true
     * @param data
     */
    public boolean searchNode(int data){
        boolean flag = false;
        NodePair tempNode = current;
        //不匹配,即没找到,则继续查找
        while(tempNode.frontNode != null || tempNode.data != data){
            tempNode = tempNode.frontNode;
        }
        //这个判读表示匹配到了
        if(tempNode.data == data){
            tempNode.frontNode.postNode = tempNode.postNode;
            tempNode.postNode.frontNode = tempNode.frontNode;
            current = tempNode;
            flag = true;
        }
        
        return flag;
    }
  • 空间满了,并且缓存中没有待访问的数据,删除最下面的节点,再新增一个节点,相当于重新赋值最下面的节点,如图
    这里写图片描述

红线表示,head将要指向倒数第二个点了,即,倒数第二个点要变成现在最底下的点了。

    /**
     * 给head节点重新赋值操作
     * 实现细节是:
     * 0.倒数第二个点(head的下一个点)的frontNode引用指向null
     * 1.给head所指节点重新赋值
     * 2.current节点的frontNode引用指向head
     * 3.把current节点指向head
     * 4.把head指向head的下一个节点(即,倒数第二个点)
     */
    public void resetHeadNode(int data){
        NodePair secondNode = head.postNode;
        
        head.postNode.frontNode = null;
        
        head.data = data;
        head.frontNode = current;
        head.postNode = null;
        
        current.postNode = head;
        
        current = head;
        
        head = secondNode;
    }
  • 缓存满了,查找缓存中是否有待访问数据,有的话,同时把有的数据放到current指针所指位置。
    /**
     * 根据数据逆序查找链表中是否有此节点,有,则把该点提出来,放到current的位置
     * 当匹配到的时候,返回true
     * @param data
     */
    public boolean searchNode(int data){
        boolean flag = false;
        NodePair tempNode = current;
        //不匹配,即没找到,则继续查找
        while(tempNode.frontNode != null || tempNode.data != data){
            tempNode = tempNode.frontNode;
        }
        //这个判读表示匹配到了
        if(tempNode.data == data){
            tempNode.frontNode.postNode = tempNode.postNode;
            tempNode.postNode.frontNode = tempNode.frontNode;
            current = tempNode;
            flag = true;
        }
        
        return flag;
    }
  • 新增节点
    /**
     * 往LRU缓存中插入数据
     * @param data
     */
    public void addNode(int data){
        //缓存未满,不需要删除,直接插入
        if(length <= size){
            NodePair tempNode = new NodePair();
            tempNode.frontNode = current;
            tempNode.postNode = null;
            tempNode.data = data;
            current = tempNode;
            length++;
        }
        //缓存满了,查找缓存中有没有数据
        else{
            if(!searchNode(data)){
                //缓存中没有,需要给head节点重新赋值
                resetHeadNode(data);
            }
        }
    }

LRU算法的缺点

如果有几个不符合“如果数据最近被访问过,那么将来被访问的几率也更高”的规律时,会破坏缓存,导致性能下降。

总结

写算法时,通过画图,写步骤,先产生一个清晰的思路,然后一步步去做实现刚才思考的步骤。

网友评论

登录后评论
0/500
评论
永立
+ 关注