交互设计就业前景,seo顾问服,网上做问卷报酬不错的网站是,新闻视频网站开发什么是LRUCache
首先我们来看看什么是cache 缓存#xff08;Cache#xff09;通常用于两个速度不同的介质之间#xff0c;以提高数据访问的速度和效率。这里有几个典型的应用场景#xff1a; 处理器和内存之间#xff1a; 处理器#xff08;CPU#xff09;的运算速度远…什么是LRUCache
首先我们来看看什么是cache 缓存Cache通常用于两个速度不同的介质之间以提高数据访问的速度和效率。这里有几个典型的应用场景 处理器和内存之间 处理器CPU的运算速度远快于从内存中读取数据的速度。因此在CPU和内存之间会有多级缓存L1、L2、甚至L3缓存用来临时存储即将被CPU使用的数据和指令。这样做可以大幅减少CPU等待数据的时间提高整体计算效率。内存和硬盘之间 内存的访问速度也远快于硬盘无论是HDD还是SSD。操作系统会使用一部分内存作为硬盘缓存有时称为“磁盘缓存”或“缓冲区缓存”用于临时存储最近访问过的数据和文件。当再次请求这些数据时可以直接从内存中获得而不是从较慢的硬盘中读取。数据库系统中 数据库管理系统DBMS也会使用缓存技术来提高查询速度和数据处理效率。缓存可以存储经常访问的查询结果、数据库索引等信息从而加速后续相同或相似查询的处理速度。网络请求 在网络请求中缓存也是提高数据访问速度的重要技术。例如Web浏览器会缓存访问过的网页资源如HTML文件、图片等当再次访问这些资源时可以直接从本地缓存读取而不需要重新从网络下载。 cache的核心作用是作为一组缓冲区来降低不同介质之间的速度差异。
那么问题来了cache满了怎么办?
显然满了就需要删除掉旧的替换进去新的内容。
但是该如何替换呢也就是替换策略是什么样的呢
目前最常用的替换策略就是LRULeast Recently Used意思是最近最少使用也就是当cache满了以后用新的数据替换最近最少使用的数据。
顾名思义LRUCache就是采用LRU替换策略的cache。 LRUCache的实现
LRUCache的实现我们以一道leetcode的题目为例
传送门:leetcode链接 cache需要实现的功能主要有查找和插入。
想要实现LRUCache的功能是很简单的但是想要实现高效的LRUCache并不简单。
所谓高效我们定义为插入和查找的时间复杂度都达到O(1) LRUCache的结构核心
想要查找和插入的时间复杂度为O1很显然想到hash表 但是如何实现LRU策略呢
这里我们的方法是使用一个list容器
当一个数据被使用之后立即提到list的头部 这样list的尾的数据就是LRU的即最近最少使用的。
所以我们的结构真的是下面的样子吗
class LRUCache
{
private:unordered_mapint,int _hash;listpairint,int _list;int _capacity;
};来我们思考一下 当我们要修改一个数据的时候我们是不是要先找到才能修改 hash表中查找很简单但是list中查找需要遍历一遍时间复杂度是O(N)显然就违背了我们高效的初衷。
那怎么办呢? LRU没办法实现高效的设计吗
前人给出了天才般的设计。
class LRUCache {
private:unordered_mapint,listpairint,int::iterator _hash;//通过迭代器可以实现//链表的O(1)的查找listpairint,int _list;//链表的查找是O(N)直接使用链表不行int _capacity;
};在原来的设计中hash和list中都存了value这显然浪费了呀凭啥要存两次啊脸大吗 所以在新的设计中 我们hash表的value不存真正的value而是存list的迭代器。 这样list的查找我们就可以借助hash来完成就将list查找的时间复杂度降到了O(1) 当然这样的设计维护起来肯定是要稍微麻烦一点的一点修改就需要两个容器同时维护。 LRUCache的查找 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 有一处细节需要注意 当我们找到了数据后代表着这条数据已经使用过就需要将他提到list的头部同时hash也要对应修改
其余非常简单直接看代码即可
int get(int key)
{auto it _hash.find(key);if(it ! _hash.end()){_list.splice(_list.begin(),_list,it-second);_hash[key] _list.begin();return (it-second)-second;}elsereturn -1;
}LRUCache的插入 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 如果key已经存在那就直接更新即可更新完后提到list的头部。 如果key不存在那就直接插入即可 1. LRUCache满了尾删然后头插 2. LRUCache没满直接头插
更新list的同时要一起更新hash表
void put(int key, int value)
{auto it _hash.find(key);if(it ! _hash.end())//找到了直接更新即可{it-second-second value;_list.splice(_list.begin(),_list,it-second);}else//没找到要新插入{if(_list.size() _capacity)//把最近不使用的元素删除掉{pairint,int back _list.back();_list.pop_back();_hash.erase(back.first);}_list.push_front({key,value});_hash[key] _list.begin(); }
}完整代码
class LRUCache {
private:unordered_mapint,listpairint,int::iterator _hash;//通过迭代器可以实现//链表的O(1)的查找listpairint,int _list;//链表的查找是O(N)直接使用链表不行int _capacity;
public:LRUCache(int capacity) {_capacity capacity;}int get(int key) {auto it _hash.find(key);if(it ! _hash.end()){_list.splice(_list.begin(),_list,it-second);_hash[key] _list.begin();return (it-second)-second;}elsereturn -1;}void put(int key, int value) {auto it _hash.find(key);if(it ! _hash.end())//找到了直接更新即可{it-second-second value;_list.splice(_list.begin(),_list,it-second);}else//没找到要新插入{if(_list.size() _capacity)//把最近不使用的元素删除掉{pairint,int back _list.back();_list.pop_back();_hash.erase(back.first);}_list.push_front({key,value});_hash[key] _list.begin(); }}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj new LRUCache(capacity);* int param_1 obj-get(key);* obj-put(key,value);*/
