算法|LRU淘汰算法-程序员宅基地

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定

常见类型包括LFU、LRU、ARC、FIFO、MRU。

最不经常使用算法(LFU):

这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法,最低访问数的条目首先被移除。这个方法并不经常使用,因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。

640?wx_fmt=other

最近最少使用算法(LRU):

这个缓存算法将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时,LRU将它放置到缓存的顶部。当缓存达到极限时,较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法,而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外,当一个LRU缓存算法删除某个条目后,“年龄位”将随其他条目发生改变。

640?wx_fmt=other

适应缓存替换算法(ARC):

在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

先进先出算法(FIFO):

FIFO是英文First In First Out 的缩写,是一种先进先出的数据缓存器,他与普通存储器的区别是没有外部读写地址线,这样使用起来非常简单,但缺点就是只能顺序写入数据,顺序的读出数据,其数据地址由内部读写指针自动加1完成,不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。

640?wx_fmt=other

最近最常使用算法(MRU):

这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久,越容易被访问的情况。

本篇将介绍LRU策略算法:

思路

LRU淘汰算法涉及数据的添加与删除,出于性能考虑,采用链表来进行实现,思路如下:

  • 维护一个双向链表用于存放缓存数据,越接近链表尾部的数据表示越少被使用到。

  • 放入一个数据时,如果数据已存在则将其移动到链表头部,并更新Key所对应的Value值,如果不存在,则:

    • 如果缓存容量已达到最大值,则将链表尾部节点删除掉,将新的数据放入链表头部;

    • 如果缓存容量未达到最大值,则直接将新的数据放入链表头部;

  • 查询一个数据时,遍历整个链表,如果能查询到对应的数据,则将其移动到链表头部;如果查询不到则返回null

    • 由于遍历链表的时间复杂度为O(n),我们可以使用散列表HashMap来记录每个Key所对应的Node节点,将时间复杂度降为O(1)。

640?wx_fmt=other

Talk is cheap , show you code:(散列表+双向链表)

public class LRUCache<K, V> {

    private int capacity;
    private Node head;
    private Node tail;
    private Map<K, Node> nodeMap;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.nodeMap = new HashMap<>(capacity);
    }

    /**
     * Get Key
     *
     * @param key
     * @return
     */
    public V get(K key) {
        Node existNode = nodeMap.get(key);
        if (existNode == null) {
            return null;
        }
        remove(existNode);
        addFirst(existNode);
        return existNode.value;
    }

    /**
     * Add Key-Value
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node existNode = nodeMap.get(key);
        if (existNode == null) {
            Node newNode = new Node(key, value);
            if (nodeMap.size() >= capacity) {
                removeLast();
            }
            addFirst(newNode);
        }
        else {
            // update the value
            existNode.value = value;
            remove(existNode);
            addFirst(existNode);
        }
    }

    /**
     * remove node
     *
     * @param node
     */
    private void remove(Node node) {
        Node prev = node.prev;
        Node next = node.next;

        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
        }
        nodeMap.remove(node.key);
    }

    /**
     * add first node
     *
     * @param node
     */
    private void addFirst(Node node) {
        // don't forget set node prev pointer to null !
        node.prev = null;
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        nodeMap.put(node.key, node);
    }

    /**
     * remove last
     */
    private void removeLast() {
        if (tail == null) {
            return;
        }
        // remove key from map
        nodeMap.remove(tail.key);
        // remove node from linked list
        Node prev = tail.prev;
        if (prev != null) {
            prev.next = null;
            tail = prev;
        } else {
            head = tail = null;
        }
    }

    private class Node {

        private K key;
        private V value;
        private Node prev;
        private Node next;

        private Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_27143551/article/details/103033208

智能推荐

游戏蛮牛unity权威指南全实例讲解书籍上线_蛮牛游戏-程序员宅基地

文章浏览阅读3.9k次。5.20为了你的Object,开始逆袭吧!今日开始预订,下周发货!! 限量1000本!!书籍由中国青年出版社出版!!现在预订送520蛮牛币, 下周书有现货的时候就送300蛮牛币啦!!购买书籍并赠送未发布视频课程的本书是游戏蛮牛unity3d(第一季)和Unity2D(第二季)的公开课144集视频课程内容所对应的书籍。本书的内容比视频的内容丰富一些,并且更加具体化,更加易_蛮牛游戏

openvswitch-vlan-(libvirt虚拟机) 配置实例_open vswitch + libvirt 搭建vlan网络-程序员宅基地

文章浏览阅读3k次。一: 编译安装openvwitch和libvirt 源码:1 编译安装openvswitch: (参考: http://networkstatic.net/configuring-vxlan-and-gre-tunnels-on-openvswitch/ )apt-get updateapt-get install -y git automake aut_open vswitch + libvirt 搭建vlan网络

setsockopt和getsockopt函数-程序员宅基地

文章浏览阅读256次。备注:本文非楼主原创,是楼主在网上发现的。。写的不错,存起来,以备后用功能描述:获取或者设置与某个套接字关联的选项。选项可能存在于多层协议中,它们总会出现在最上面的套接字层。当操作套接字选项时,选项位于的层和选项的名称必须给出。为了操作套接字层的选项,应该将层的值指定为SOL_SOCKET。为了操作其它层的选项,控制选项的合适协议号必须给出。例如,为了表示一个选项由TCP协议解析...

springboot卡塔尔世界杯门户网站-计算机毕设 附源码40685-程序员宅基地

文章浏览阅读101次。卡塔尔世界杯门户网站主要采用java技术,基于B/S结构,Mysql数据库,对于应用程序的开发要求具备完整功能,使用简单的特点,并建立一个数据完整安全稳定的数据库。卡塔尔世界杯门户网站的开发技术具有很高可行性,且开发人员掌握了一定的开发技术,所以系统的开发具有可行性。3.1.2操作可行性卡塔尔世界杯门户网站的登录界面简单易于操作,采用常见的界面窗口来登录界面,通过电脑进行访问操作,会员只要平时使用过电脑都能进行访问操作。此系统的开发采用java语言开发,基于B/S结构,这些开发环境使系统更加完善。本系

python3.6 django2 连接mysql-程序员宅基地

文章浏览阅读119次。1、mysql 需要装好数据库,并正常运行,建好数据库名;2、需要安装 pymysql 工具;3、需要在 init.py 添加代码import pymysqlpymysql.install_as_MySQLdb()4、settings.py 需要修改代码DATABASES = { 'default': { 'ENGINE': 'django.db.ba...

CSS3新增选择器两种方式开关效果实现(剖析实现过程)_css选择器开关-程序员宅基地

文章浏览阅读167次。网上有很多很好看的开关,其实实现的过程大同小异,只是换了一个装扮而已,所以只要掌握开关的核心实现的原理方法,明白了之后也就游刃有余了。首先我们要实现一个开关的效果的话肯定要分析下如果实现它应该从哪方面开始着手,就如同下面的开关图示一样没有点击开关的时候,开关的默认状态为左边,点击之后开关跑到了右边,然后背景的颜色也随之改变,所以我们这里就要说到第一种实现的方式,这种方式个人感觉也是比较好理..._css选择器开关

随便推点

编程语言_the default behaviour of interpolate/upsample-程序员宅基地

文章浏览阅读4.2k次,点赞2次,收藏4次。编程语言学习首先要思考学习编程语言的目的,目的是为了让计算机知道自己要干什么。只要能实现目的就行,当然花的时间成本越少越好。机器语言太难,汇编有点难(不同的芯片还不一样),所以选择高级语言。学第一门编程语言时,跟着老师或者教材认真学,例子都要敲一遍,语法也要仔细看一遍,常见的错误也要注意,最后最好能刷一遍该语言的面试编程题然后做一个项目。当掌握几门编程语言后,学其..._the default behaviour of interpolate/upsample

MongoDB笔记(一) —— 下载安装_no implicit session: logical sessions are only sup-程序员宅基地

文章浏览阅读474次。下载下载地址https://fastdl.mongodb.org/osx/mongodb-macos-x86_64-4.2.3.tgz解压$ sudo tar -zvf mongodb-macos-x86_64-4.2.3.tgz重命名为mongodb,移动到/usr/local/,添加到PATH$ export PATH=/usr/local/mongodb/bin:$PATH..._no implicit session: logical sessions are only supported on server versions

Eslint semi 结尾分号设置与否_eslint semi-程序员宅基地

文章浏览阅读2.9w次,点赞14次,收藏15次。由于java书写习惯 语句结束加分号,而前端使用了eslint,习惯性的加分号,会给错误。这里特别记录一下例如:测试字符串后增加了一个分号,可以看到是eslint semi规则设置报错找到配置文件,配置semi即可取消对分号的报错ESlint配置而我这里配置在了.eslintrc.js文件中,并没有在 package.json 中增加eslintConfig方案一:打开 .eslintrc.js找到rule节点下的 semi可以看到现在是不允许有分号:第一个参数:"off"或0-._eslint semi

com.intellij.javaee.oss.admin.jmx.JmxAdminException: com.intellij.execution._[2023-12-25 09:01:12,371] 工件 app: com.intellij.jav-程序员宅基地

文章浏览阅读1.3k次。细看这个异常信息中会包含war包的完整路径,所以解决方式很简单,在ide中看这个路径下是否有war包,如果没有,说明是你往tomcat里添加exploded的时候选错了。_[2023-12-25 09:01:12,371] 工件 app: com.intellij.javaee.oss.admin.jmx.jmxadm

java 第六次课--图形用户界面概述_f.setvisible(true)-程序员宅基地

文章浏览阅读4.6k次。Java图形用户界面概述一、Java语言平台无关性组件的实现图形用户界面是当今流行的操作系统界面。Java语言为了适应发展趋势,也具有开发图形化的用户界面的功能。Java语言自身的特点要求其图形用户界面具有平台无关性。早期的Java版本JDK1.0和JDK1.1采用 的是AWT组件。特点是简单、易于理解。AWT组件中采用了一种称为对等体(peer)的机制,每个组件都有一个对应的对等体,是用_f.setvisible(true)

Android list列表滑动显示隐藏toolbar(ListView)_android 分类列表 显示全部 隐藏-程序员宅基地

文章浏览阅读3.4k次。前言:上下滑动列表时,toolbar跟着隐藏和显示,这种效果在google系应用中比较频繁出现,比如google plus。 google plus效果: 现在以ListVIew列表实现(两种方式):一,使用ListView的方法addHeaderView(headerView);1,build.gradle: dependencies { _android 分类列表 显示全部 隐藏