LRU Cache

这篇具有很好参考价值的文章主要介绍了LRU Cache。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 什么是LRU Cache

LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法
什么是Cache?
狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
而Cache的容量有限,那如果cache满了怎么办?
当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。
那应该选取那一部分的内容和新内容进行替换呢?这就涉及到cache的替换算法,而LRU Cache就是cache替换算法中的一种!
LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

2. LRU Cache的实现

那要实现一个LRU Cache其实并不难,方法和思路有很多;但是想要实现一个高效(所有操作都是O(1) )的LRU Cache是有难度的

实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和哈希表的搭配是最高效和经典的。
使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

那具体到底应该应该怎么做呢?

下面我们借助LeetCode上的一道OJ来给大家进行一个详细的讲解。

3. LRU Cache的OJ

题目链接: link

我们来看一下题目:
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
大家可以自己先看一下题目,我们看到题目中要求函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

那我们来分析一下要如何实现

题目分析

题目要求我们实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
这个 LRUCache 类的要求是这样的:

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

那我们要如何实现呢?

其实分析完题目我们很容易能想到用哈希表,那当然C++里面我们就用unordered_map去搞,那这样的话get函数(其实就是查找嘛)就能达到O(1);然后put呢,put也是要查找嘛,找到就更新,找不到就插入。那这样就也是O(1)。
但是呢我们真正还要考虑还有——如果插入操作导致关键字数量超过 capacity ,我们此时就要进行LRU替换,则应该 逐出 最久未使用的关键字。
那我们要如何实现LRU的替换呢?满的话应该逐出谁啊?如何找到最久未被使用的那个呢?

🆗,那上面也提到了,使用双向链表和哈希表的搭配是最高效和经典的:

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
我们再搞一个list(list底层就是带头双向循环链表),让它里面也存储数据(相当于数据存储两份),然后我们可以默认认为尾部的那个元素就是最近最少用(最久未被使用)的(按头部实现也可)
然后如果有新插入的元素或者被访问(get一个已有的值)的元素我就把它移到链表头部。
这样我们需要替换的时候,那么链表尾部的那个就是最久未被使用的那个。

但是呢?

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
如果我们就这样设计的话,还存在一个问题。
就是更新的时候其实复杂度是O(N)
为什么呢?
更新的情况就是调用put先在哈希表里面查找到key是已存在的,那然后我们要修改,哈希表里面我找到这个就可以直接修改。
但是,在list里面我们是不是也要修改啊,因为我们替换的时候找最久未被使用的那个值就是要从list里面找呢。
但是要修改list的话我们知不知道当前要修改的这个元素是list里面的哪一个元素?
是不知道的,所以还得遍历list去找。找到之后更新一下,然后把它移到头部去,更新顺序。
那这里遍历查找的话不就是O(N)了嘛。

那这个问题我们如何解决一下呢?

如何做到在哈希表里面找到这个key之后,就直接能获取到他在list中的位置,而不需要去遍历查找呢?

那这里有一个非常巧的设计是这样来解决的:

还是list和unordered_map搭配。
list里面呢还是存key-value的键值对pair。然后哈希表里面key还是要存的,但是不再像上面写的那样直接存key对应的数据value,而是存这个key对应的元素在list里面的对应的迭代器。(那这样真正的数据就只存在list里面)
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
那这样的话如果更新的话,首先我们在哈希表里面找到key,然后通过它里面存的该元素在list中的迭代器,就可以直接修改list里面存放的数据。
然后再把它放到链表头部(两种方法,后面会提到)。
当然list<pair<int,int>>::iterator这个类型比较长,我们也可以typedef一下
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

那下面我们来尝试写一下代码:

AC代码

那首先我们应该还要再增加一个成员变量:

即cache的容量capactity,因为有时候我们还需要判断cache满不满。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

然后我们来逐一实现一下它的3个成员函数:

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

首先是它的构造函数LRUCache:

那这个很简单,就是初始化一下capacity就行了。
剩下两个成员变量是自定义类型,有默认构造。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

那然后是get函数:

get呢也很简单,就是通过key判断在不在嘛。
如果在的话,就返回key对应的值;如果不在,返回-1。
那我们就可以直接调用unordered_map的find函数,根据find的返回结果判断,如果找到了,我们要返回什么呢?
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
🆗,首先这里的ret是啥啊,这里find返回的是迭代器,找到的话返回的就是key对应的这个元素的迭代器。
那我们要返回这个key对应的那个有效的值,那真正的数据是存在list里面的。
我们通过谁可以找到list里面存储的这个key对应的元素呢?
🆗,现在unordered_map里面的value存的是list里面这个key对应元素的迭代器(有点绕了这里😂)。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
所以ret->second就是list里面这个元素的迭代器,但是我们想要拿到的是这个元素的key对应的值,即ret->second->second,这里要取两次second。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

🆗,那这样就完了嘛?

还没有。
如果get的时候成功找到了这个数据,那相当于访问了它,那cache里面存储数据的顺序是不是就要调整了。是不是要把这个刚被访问的元素放到链表头部啊。

那如何在list里面调整这个顺序呢?我们上面提到有两种方式:

首先第一种方法我们可以先把这个元素删除掉,然后在头插到头部。
但是这样的话记得还要更新一下unordered_map里面存的对应的那个迭代器,因为删完之后这个迭代器就失效了。之前的文章我们模拟实现过list,我们知道list的迭代器其实就是对结点指针的封装嘛,这个结点删除的话它这个结点指针指向的空间就释放了。
所以这种方法好像有点麻烦。
那我就可以考虑用另外一种——直接调用list的splice 接口转移结点。
那splice 这个函数其实我们之前也有提到过
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
它可以把一个链表的一部分转移到另一个链表(当然也可以是同一个链表直接进行转移)
所以我们就可以直接调用splice将这个结点转移到list的头部。
LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表

那最后就剩下put:

那put的话呢无非就两种操作
如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。
当然插入的时候需要判断:
如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字,然后插入新值。
另外不论是插入还是更新,都应该把插入或更新的值放到链表头部。

那我们来写一下代码:

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
🆗,那到这里就完事了。

我们来提交一下:

LRU Cache,C++入门到起飞,高阶数据结构(C++),LRU cache,c++,数据结构,哈希表,链表
没有问题!

完整代码:

class LRUCache {
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {}
    
    int get(int key) {
        auto ret=_hashmap.find(key);
        if(ret!=_hashmap.end())
        {
            LtIter it=ret->second;
            //将it对应的结点转移到链表头部
            _LRUList.splice(_LRUList.begin(),_LRUList,it);
            return it->second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto ret=_hashmap.find(key);
        //如果找到,更新值
        if(ret!=_hashmap.end())
        {
            LtIter it=ret->second;
            it->second=value;

            //将it对应的结点转移到链表头部
            _LRUList.splice(_LRUList.begin(),_LRUList,it);
        }
        else//找不到,插入
        {
            //如果满了需要先删除最久未使用的值
            if(_capacity==_hashmap.size())
            {
                pair<int,int> back=_LRUList.back();
                _hashmap.erase(back.first);
                _LRUList.pop_back();
            }
            //插入
            _LRUList.push_front(make_pair(key,value));
            _hashmap[key]=_LRUList.begin();
        }
    }
private:
    typedef list<pair<int,int>>::iterator LtIter;

    //hash做到查找更新/插入是O(1)
    unordered_map<int, LtIter> _hashmap;

    //LRU 默认链表尾部的是最久未被使用的
    list<pair<int, int>> _LRUList;

    size_t _capacity;
};

那我们这篇文章就到这里…文章来源地址https://www.toymoban.com/news/detail-804275.html

到了这里,关于LRU Cache的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

    前面的Redis从入门到精通的基础篇和进阶篇都是在使用层面和概念层面,本章节,我们了解一下redis的底层数据结构,上几个章节,我们讲了SDS,字典 。本章节我们聊一下ZipList。 压缩列表(ZipList)就是redis为了节约内存而设计开发的数据结构,并且作为列表键和哈希键的底层

    2024年02月08日
    浏览(87)
  • Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解

    上个篇章回顾,我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解》,我们从源码层了解字典是一种以键值对(key-value)形式存储数据的数据结构。在 Redis 中,字典使用哈希表来实现。哈希表是一种以常数时间复杂度 O(1) 进行插入、删

    2024年02月09日
    浏览(40)
  • 146. LRU Cache最近最少使用 (LRU) 缓存 Least Recently Used (LRU) cache.

    Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. O

    2024年02月10日
    浏览(55)
  • LRU Cache

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是 一种Cache替换算法 。 什么是Cache? 狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调

    2024年01月19日
    浏览(45)
  • LRU数据结构

    LRU缓存是非常经典的数据结构设计,本文重点在于设计出get、put方法时间复杂度都为O(1)的LRU缓存 LRU缓存特征是当超出容量时会将最近最少使用的元素逐出 第一次的失败尝试——记录有效区间 记录有效区间的方法是通过计数器counter为每一个最近使用的元素记录最新计数,在

    2024年02月15日
    浏览(40)
  • 数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

    关于LRU缓存 LRU - Lease Recently Used 最近使用 如果内存优先,只缓存最近使用的,删除 ‘沉睡’ 数据 核心 api: get set 分析 使用哈希表来实现, O(1) 必须是有序的,常用放在前面,沉睡放在后面, 即:有序,可排序 这样 {} 不符合要求;Map是可以排序的,按照设置顺序 不用 Map 如何

    2024年02月06日
    浏览(53)
  • 【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

    2024年02月03日
    浏览(42)
  • LRU 该用什么数据结构

    LRU(最近最少使用),是一种缓存置换算法。缓存是用来存储常用的数据,加速常用数据访问的数据结构。有软件实现,比如数据库的缓存;也有硬件实现,比如我们上一讲学的 TLB。 缓存设计中有一个重要的环节:当缓存满了,新的缓存条目要写入时,哪个旧条目被置换出

    2024年02月06日
    浏览(38)
  • cache教程1.LRU 缓存淘汰策略

    这一节实现LRU算法,要理解明白其使用的数据结构。 Cache的缓存全部存储在内存中,内存是有限的,因此不可能无限制地添加数据。当占用内存超过了给定的内存大小时候,就需要从缓存中移除一条或多条数据了。我们肯定希望尽可能移除“没用”的数据,那如何判定数据“

    2024年02月04日
    浏览(45)
  • python装饰器原理 | 常用装饰器使用(@cache, @lru_cache)

    🚀 关于python的装饰器原理介绍可看这里,讲的挺简洁易懂:python装饰器原理 ⭐ 弄懂装饰器原理后,来学学常用装饰器。 也就是一种装饰在被执行的函数上,将其执行的结果缓存起来,当下次请求的时候,如果请求该函数的传参未变则直接返回缓存起来的结果而不再执行函

    2023年04月25日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包