算法|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

智能推荐

android8.1 编译报错 Jack server问题_内核观察员的博客-程序员宝宝

编译android8.1 报错 jack-server相关的问题。jack-server 是安卓源码编译工具。在android6.0 ~ android8.1源码中使用。之后的版本废弃了。报错类型1:Communication error with Jack server (58), try ‘jack-diagnose’ or see Jack server logFailed to contact Jack server: Problem reading /home/user3/.jack-se

android 8.1 新增自定义系统服务_陈十方的博客-程序员宝宝

android8.1 新增自定义系统服务 并调用 替换SDK

[嵌入式linux]将linux板卡虚拟为USB网卡设备(Ethernet Gadget)_Lenz's law的博客-程序员宝宝

kernel menuconfig-&gt; Device Drivers -&gt;USB support -&gt; USB Gadget Support 建议最好选成M,作为内核驱动模块,便于与其他Gadget驱动共存&lt;M&gt; USB Gadget Drivers&lt;M&gt; Ethernet Gadget (with CDC Etherne...

tkinter(GUI界面设计)+python实现简单猜数字游戏_王同学在这的博客-程序员宝宝

不练不厉害,目标数字不能是固定的,必须每次游戏开始随机生成一个数字。我们可以用random()来实现,这个函数就是随机生成一个0到1之间的数。我们的游戏需要生成1到100之间。

web期末网站设计大作业:动漫网站设计——龙猫(10页) HTML+CSS+JavaScript 学生DW网页设计作业成品 web课程设计网页规划与设计 动漫漫画网页设计[email protected]码住夏天-web网页设计的博客-程序员宝宝

web期末网站设计大作业:动漫网站设计——迪斯尼公主(6页) HTML+CSS+JavaScript 学生DW网页设计作业成品 web课程设计网页规划与设计 计算机毕设网页设计源码 常见网页设计作业题材有 个人、 美食、 公司、 学校、 旅游、 电商、 宠物、 电器、 茶...

CButtonST的使用_demystify的博客-程序员宝宝

CButtonST是功能强大的按钮类,通过它可以实现多样化、美观的按钮控件。一、CButtonST类1、使用方法:通过MFC类向导(常用)或动态创建(Create) 在MFC对话框模板中添加“按钮资源”,在模板对应的对话框类中添加CButtonST成员,在类的DataExchange方法中添加DDX_Control相关,最后在OnInitDialog中添加风格设置代码;...

随便推点

前端处理文件流下载文件超级超级超级简单的方法_前端架构师陈龙威的博客-程序员宝宝

今天后端让帮忙做个导出excel的功能,ok。后端提供的数据:接口:content/scale/downloadExcel参数为:chnlCode=xxx前端处理:// 调用该方法,传入chnlCode即可实现文件流下载function downloadExcel(chnlCode) { let url = '/content/scale/downloadEx...

vscode安装code runner后运行程序出现乱码解决办法 �밴���������. . ._龙在雨中歌唱.的博客-程序员宝宝_code runner 乱码

安装好code runner后编译c++文件时发现会出乱码,查了查网上好像没啥解决办法,后来看了看code runner的说明文件解决了。首先进入Code-runner: Executor Map的界面,选择在settings.json中编辑然后需要手动输入图中6-17行的代码(图1),该代码源自官方手册(图2)我把我自己用的代码放到下面 "code-runner.executorMap": { "javascript": "node", "ph.

Fragment跳转到Activity,刚跳转就走了onActivityResult方法_门捷亮夫的博客-程序员宝宝

昨晚把项目打包测试,发现Fragment跳转到新的Activity并使用回调时,刚跳转就走了onActivityResult()方法,导致真正Activity关闭返回的时候,回调值并没有传递给Fragment,这种现象在Android5.0以上的手机没有出现,手里有个Android4.4和4.3的手机都出现这个问题。一开始也感觉莫名其妙,后来打了日志才发现这个问题,看了一些资料后发现是因为所跳转到

xmodmap_for_singhand_lsy563193的博客-程序员宝宝

keycode  68 = 2 at 2 at F2 F2 XF86Switch_VT_2keycode  69 = 3 numbersign 3 numbersign F3 F3 XF86Switch_VT_3keycode  70 = 4 dollar 4 dollar F4 F4 XF86Switch_VT_4keycode  71 = 5 percent 5 percent F

Docker学习二 Docker授权普通用户_辉度的博客-程序员宝宝_docker授权

Docker授权普通用户文章目录Docker授权普通用户前言案例授权结果前言docker往往是使用root用户,用yum 或者 apt-get install 等安装命令安装,所以在安装完成后,只有root用户可以执行。其他用户并不能执行。案例比如使用docker version查看版本:[[email protected] ~]$ docker versionClient: Docker Engine - Community Version: 19.03.9 API version:

C语言及程序设计实践项目-递归和多文件组织_weixin_34122604的博客-程序员宝宝

【项目1——递归求解】 (1)立方累加和:用递归函数求f(n)=13+23+...+n3,要求先将f(n)数学表达式表示成递归的形式,然后再编程序实现。 (2)写出求1*3*…*n的递归式,并编写出递归函数求解。 (3)编程序,用递归函数求出两个数的最大公约数。(包括编main函数,调用定义的递归函数) 参考解答 ...