【算法】 LRU Cache

目录

一、什么是LRU Cache

二、LRU Cache的实现

三、 LRU算法的运用场景


一、什么是LRU Cache

LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 什么是 Cache?狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用 DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache——称为Internet临时文件夹或 网络内容缓存等。

Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

二、LRU Cache的实现

实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和 哈希表的搭配是最高效和经典的。

使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1);但我们要注意的是哈希表val值存储的并不是对应的数据值,而是指向双向链表某一个节点的迭代器,这样子在我们查找数据在链表中某一个节点位置时,就可以直接通过哈希表来定位,并不用遍历链表了:

下面我们通过一道OJ题来实现一下该算法:

题目地址:146. LRU 缓存 - 力扣(LeetCode)

解题代码: 

class LRUCache {
public:
public:
    LRUCache(int capacity) { _capacity = capacity; }
    int get(int key) {
        // 如果key对应的值存在,则listit取出,这里就可以看出hashmap的value存的是list的iterator的好处:找到key也就找到key存的值在list中的iterator,也就直接删除,再进行头插,实现O(1)的数据挪动。
        auto hashit = _hashmap.find(key);
        if (hashit != _hashmap.end()) {
            auto listit = hashit->second;
            pair<int, int> kv = *listit;

            _list.erase(listit);
            _list.push_front(kv);
            _hashmap[key] = _list.begin();
            return kv.second;
        } else {
            return -1;
        }
    }
    void put(int key, int value) {
        // 1.如果没有数据则进行插入数据
        // 2.如果有数据则进行数据更新
        auto hashit = _hashmap.find(key);
        if (hashit == _hashmap.end()) {

            // 插入数据时,如果数据已经达到上限,则删除链表头的数据和hashmap中的数据,两个删除操作都是O(1)
            if (_list.size() >= _capacity) {
                _hashmap.erase(_list.back().first);
                _list.pop_back();
            }

            _list.push_front(make_pair(key, value));
            _hashmap[key] = _list.begin();
        } else {
            // 再次put,将数据挪动list前面
            auto listit = hashit->second;
            pair<int, int> kv = *listit;
            kv.second = value;

            _list.erase(listit);
            _list.push_front(kv);
            _hashmap[key] = _list.begin();
        }
    }

private:
    list<pair<int, int>> _list; // 将最近用过的往链表的投上移动,保持LRU
    size_t _capacity; // 容量大小,超过容量则换出,保持LRU
    unordered_map<int, list<pair<int, int>>::iterator> _hashmap;
    // 使用unordered_map,让搜索效率达到O(1)
    // 需要注意:这里最巧的设计就是将unordered_map的value
    // type放成list<pair<int,int
    // >>::iterator,因为这样,当get一个已有的值以后,就可以直接找到key在list中对应的iterator,然后将这个值移动到链表的头部,保持LRU。
};

三、 LRU算法的运用场景

LRU算法也可以用于一些实际的应用中,如你要做一个浏览器,或类似于淘宝客户端的应用的就要用到这个原理。大家都知道浏览器在浏览网页的时候会把下载的图片临时保存在本机的一个文件夹里,下次再访问时就会直接从本机临时文件夹里读取。但保存图片的临时文件夹是有一定容量限制的,如果你浏览的网页太多,就会一些你最不常使用的图像删除掉,只保留最近最久使用的一些图片。这时就可以用到LRU算法 了,这时上面算法里的这个特殊的栈就不是保存页面的序号了,而是每个图片的序号或大小;所以上面这个栈的元素都用Object类来表示,这样的话这个栈就可以保存的对像了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/475544.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue2源码学习01配置rollup打包环境

1.下载rollup相关依赖 npm i rollup rollup-plugin-babel babel/core babel/preset-env --save-dev 2.新建rollup.config.js配置打包选项 //rollup可以导出一个对象&#xff0c;作为打包的配置文件 import babel from rollup-plugin-babel export default {input: ./src/ind…

CI/CD脚本简介,YAML介绍,Editor解析

说明&#xff1a; 此篇文章纯概念&#xff0c;没有实际操作&#xff0c;实际操作请蹲下一篇&#xff01; CI/CD理解 这段代码是用于配置GitLab CI/CD&#xff08;Continuous Integration/Continuous Deployment&#xff09;的YAML语法。GitLab CI/CD是一种自动化软件&#xff0…

【MySQL】对数据库的操作以及数据库备份相关操作

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前学习计网、mysql和算法 ✈️专栏&#xff1a;MySQL学习 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac…

罗技G29游戏方向盘试玩拆解,带震动力反馈

1.正好有时间记录下 自己的爱好 一千多的罗技G29游戏方向盘试玩拆解&#xff0c;带震动力反馈&#xff0c;值这个价吗_哔哩哔哩_bilibili 一千多的罗技G29游戏方向盘试玩拆解&#xff0c;带震动力反馈&#xff0c;值这个价吗_哔哩哔哩_bilibili 2.拆解 3.2个大电机 4.主控芯…

上榜|美创入选《2024年网络与信息安全行业全景图》32个细分领域

近日&#xff0c;深圳市网络与信息安全行业协会正式发布《2024年网络与信息安全行业全景图》&#xff08;以下简称“全景图”&#xff09;&#xff0c;定位展现我国网络与信息安全行业整体生态及细分领域代表性厂商。 美创科技凭借硬核实力&#xff0c;成功入选数据安全、安全服…

外卖项目:使用AOP切面,完成公共字段自动填充(断点调试详细讲解)

文章目录 一、问题描述二、实现思路三、实现步骤四、断点实操五、代码演示 一、问题描述 我们已经完成了后台系统的员工管理功能和菜品分类功能的开发&#xff0c;在新增员工或者新增菜品分类时需要设置创建时间、创建人、修改时间、修改人等字段&#xff0c;在编辑员工或者编…

西井科技与安通控股签署战略合作协议 共创大物流全新生态

2024年3月21日&#xff0c;西井科技与安通控股在“上海硅巷”新象限空间正式签署战略合作框架协议。双方基于此前在集装箱物流的成功实践与资源优势&#xff0c;积极拓展在AI数字化产品、新能源自动驾驶解决方案和多场景应用&#xff0c;以及绿色物流链等领域的深度探索、强强联…

Pudgy Penguins交易量一路攀升 多次创下历史新高

日前&#xff0c;一个名为胖企鹅&#xff08;Pudgy Penguins&#xff09; NFT 项目交易量持续攀升&#xff0c;一度在3月9日成为NFT市场的“销冠”。事实上&#xff0c;从2023年下半年开始&#xff0c;Pudgy Penguins的地板价就在不断上升&#xff0c;进入2024年更是多次创下历…

练习题+题解:链表+dp

目录 1.链表指定区间反转题目描述输入格式:输出格式:输入样例:输出样例:题目分析代码实现 2.hxj和他的甜品盲盒I输入格式:输入样例:输出样例:样例解释 输入样例:输出样例:样例解释 题目分析Java代码实现 3.First 50 Prime Numbers输入格式输出格式输入样例输出样例题目解析代码…

MySQL之索引与事务

一 索引的概念 一种帮助系统查找信息的数据 数据库索引 是一个排序的列表&#xff0c;存储着索引值和这个值所对应的物理地址无须对整个表进行扫描&#xff0c;通过物理地 址就可以找到所需数据是表中一列或者若干列值排序的方法 需要额外的磁盘空间 索引的作用 1 数据库…

【干货】Java开发者快速上手.NET指南

前言 前几天有小伙伴在技术群里发了一个微软官方出的&#xff1a;适用于Java开发人员的.NET快速入门免费电子书&#xff0c;今天大姚来分享一下Java开发者想要快速上手.NET有哪些教程和优质资料。 微软适用于Java开发人员的.NET快速入门指南 下载阅读地址&#xff1a;适用于 …

惟客数据CTO 钱勇:数据资产运营创新和实践

​企业如何做好数据资产运营&#xff0c;有效挖掘和利用数据资产&#xff1f; 近日&#xff0c;在由华东江苏大数据交易中心主办的“第四届数字经济科技大会”上&#xff0c;WakeData惟客数据CTO、星光数智CEO 钱勇 给出了自己的观点。 在演讲环节&#xff0c;钱勇以《数据资…

用tp6写的简单的eml的登录和curd

项目地址&#xff1a; 企业管理eml: 这是一个简单的eml (gitee.com) 1.登录和主页显示 1.1 登录功能逻辑图 1.2 控制器 app/controller/index.php php think make:validate LoginValidate <?php namespace app\controller;use app\BaseController; use app\model\User; …

IDEA设置全局配置

1、 IDEA设置全局配置 在IDEA中&#xff0c;选择 File -> Close Project 关闭项目。然后选择Customize -> All settings 进行全局配置&#xff0c;即所有项目公共的配置。 配置文件编码 配置控制台编码 配置maven 配置文件模板 配置文件模板作者和时间信息如下&#xff…

德勤:《亚太地区半导体行业展望》

2024年2月22日&#xff0c;德勤联合全球半导体联盟&#xff08;GSA&#xff09;对亚洲半导体产业链相关企业展开调研&#xff0c;邀请数位亚太地区主要半导体企业领导人&#xff0c;共同探讨半导体企业在当前环境下应如何通过数字技术曲线的领先优势保持业务竞争力和盈利能力&a…

“我的海外代购,卖起了香灰手串”

【潮汐商业评论/文】 “这个琉璃手串&#xff0c;去年在雍和宫请的&#xff0c;招财的&#xff1b;这个朱砂挂件&#xff0c;当时直播说可以补八字缺火&#xff0c;果断下单的&#xff1b;这个博主讲星座很准&#xff1b;这篇帖子八字说得很详细&#xff1b;我前两天买了‘财神…

qt5-入门-标签页部件QTabWidget-1

参考&#xff1a; C GUI Programming with Qt 4, Second Edition 本地环境&#xff1a; win10专业版&#xff0c;64位&#xff0c;Qt5.12 目录 效果实现Qt Designer操作代码addStretch()解释 效果 首页有三个按钮和最近文件列表。 拖动窗口&#xff0c;按钮和文件列表仍然处…

CentOS7安装mysql-5.7.44单机和主从复制

官网下载地址&#xff1a; https://downloads.mysql.com/archives/community/ 1、单机安装 安装依赖 yum -y install libaio 解压安装 tar -zxvf mysql-5.7.44-linux-glibc2.12-x86_64.tar.gzmv mysql-5.7.44-linux-glibc2.12-x86_64 /usr/local/mysqlcd /usr/local/mysql…

【Spring 篇】走进Java NIO的奇妙世界:解锁高效IO操作的魔法

欢迎来到Java NIO的神奇之旅&#xff01;在这个充满活力的世界里&#xff0c;我们将一起揭示Java NIO&#xff08;New I/O&#xff09;的奥秘&#xff0c;探索其在高效IO操作中的神奇魔法。无需担心&#xff0c;即使你是Java的小白&#xff0c;也能轻松领略这个强大而灵活的IO框…

【pycharm】作为Array查看出现数据无法显示问题(已解决)

【pycharm】作为Array查看出现数据无法显示问题&#xff08;已解决&#xff09; 当我们在调试代码的时候&#xff0c;需要对某个变量进行查看&#xff0c;就如同在matlab中&#xff0c;我们可以直接在工作区对某个变量进行双击查看矩阵变量的具体数值 在这里我遇到一个问题&am…