LRU(最近最久未使用)数据缓存机制的实现
面试常问
1.为什么会需要数据的缓存?(分页存储机制)
(1)缺页中断:我们知道在操作系统中,数据存储是使用分页存储的机制,一个进程可以对应一个页表,页表中有很多页,也就是当一个进程对应很多页时,执行进程时并不是所有页都装入内存中(当然要考虑内存开销和io阻塞),会将部分装入内存。
(2)当需要的那页不存在内存中时,这时将发生缺页中断,需要把那页从外存中调入内存中;
ps:
(1) 页表寻址: 页在逻辑上连续在物理上不连续; 页分为页号(从 0 开始编号)与页内偏移地址,有两个寄存器:页表基地址寄存器和页表长度寄存器。
(2) 块表: 页的大小相同,内存中的块与页大小相同
2.怎么进行页面的置换呢?(页面调度-置换算法)
调页算法:
先进先出,最佳页面置换算法(OPT);
最近最久未使用(NRU);
最近最少使 用置换算法(LRU);
先进先出算法(FIFO)会导致 Baley 问题;
抖动,页面在内存与外存中的频繁调页;
3.这体现了程序局部性原理,时间局部性、空间局部性;
4.LRU的设计与实现:
我们先看需要完成的功能:具体可以看leetcode T.146
LRU缓存设计
(1)设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
(2)获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。
(3)写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
这里最关键的要求就是:是否可以在 O(1) 时间复杂度内完成这两种操作?
我们来一步分析下:
1)
a. 用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据的时间戳自增,并将新数据时间戳置为 0 插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项时间戳置为 0。当数组空间已经满时,将时间戳最大的数据项淘汰;
b. 时间复杂度分析:由于使用的数组,增删查都是顺序,数据的查找,删除和插入总体来说是o(n)情况下的。而且数据量大的情况下很慢。
空间复杂度分析:使用了一个数组,为一个随被处理数据量n的大小而改变的常量o(n)而且数组容量的扩容也是个很大的问题
2)
a.利用一个链表来实现,每次新插入数据的时候将新数据插入到链表头部;每次缓存命中,则将数据移动到链表头部;那么当链表满时,就将链表尾部的数据丢弃;
b. 时间复杂度分析:由于使用的链表,增删的话就优化成了o(1),但是链表的查找还是线性的,也就是o(n)
空间复杂度分析:用到一个链表,随被处理数据量n的大小而改变o(n),同时链表能有效利用不连续的内存空间,存放的数据数量增加
3)
a.于是我们对方法(2)再进一步优化,需要将查找做到o(1),很自然的想到了hash_map:利用链表和 hashmap。当需要插入新的数据项 的时候,如果新数据命中,则把该节点放到链表头部,如果不存在,则将新数据放在链表头部。若缓存满了,则将链表尾部的节点删除。
b.时间复杂度分析:增删查都是o(1)
空间复杂度分析: 用到了一个双端链表,一个unordered_map,随被处理数据量n的大小而改变,所以 应该是 2*o(n);
设计LRU的数据结构和复杂度分析完成了,我们就具体设计一下:
/*(1)主要实现就是通过一个双端队列和hashmap;
(2)首先是想把数据(key - value)存放在一个数组中,想到是用vector容器还是队列,由于需要插入和删除 数据,vector的话就需要数据的移动,但是用双端队列的话,就能实现o(1)的复杂度:自然存储的是 pair<int,int>数据,这样当访问新的数据的时候,就把新的数据插入到队头,(也就是最近使用的存对 头,最久未使用的放队尾)
(3)这里就涉及到查找数据是否存在与队列中。为了实现o(1)的时间复杂度,很自然的想到hash_map,首先它 的K就是数据的key,V的话需要考虑一下,由于是根据map在list中找,就需要此key在list中的位置,也就 是下标索引,由于是不连续的空间,所用用list的迭代器定位它的位置
(4)下面我们来看具体实现,
首先:LRUCache(int capacity),通过构造函数实现
容量capacity,决定了LRU缓存的数据容量
然后:数据的写入操作 void put(int key, int value)
put(key, value) - 如果关键字已经存在,则变更其数据值----首先在hash_map中寻找是否存在,
a.如果存在,那这个数据是最近使用的,在list中找到对应的pair(key,原始_value),用临时变量 存储下,然年删除,再把对应的新的pair(key,value)插入在队头。
这里需要注意的点是:变更hash_map中key对应的list下标索引位置(应该是begin()位置)
b.如果关键字不存在,则直接在队头插入该pair(key,value),在hash_map中存储key 和 下标索引 begin()。
c.当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值 留出空间。也就是在list的队尾删除之,相对应的也在hash_map中删除这个最久未使用的数据。然 后在队头插入新的数据,hash_map记录数据。
d.至此,LRU的数据写入操作就完成了
其次:数据的读操作 int get(int key)
获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则 返回 -1。
a.首先根据查找的key,同样在hash_map中查找其位置,如果不存在(我认为hash_map和list除了 刚启动时是空的,后续操作是保持不空的),就直接返回-1;如果存在,就从list中返回key对应 的数据,同时变更位置(成为最近使用的数据,放队头)
b.至此,LRU的读操作就完成了
最后: LRU (最近最少使用) 缓存机制完成。
*/
class LRUCache {
private:
int cap; // capacity of thr LRUcache
list<pair<int, int>> cache; //double_list store the map<key,value>;
unordered_map<int, list<pair<int,int>>::iterator> mp; //unorder_map store (key, index of the map[key] int list)
public:
LRUCache(int capacity) { //构造函数 缓存容量
this -> cap = capacity; //init
}
int get(int key) {
auto get_pair = mp.find(key);
if(get_pair == mp.end()) //if not found
return -1;
else
{
//if found
// put mp[key] in the front
// return value
int ans = mp[key]->second;
cache.erase(mp[key]) ; //delete 注意:这里是根据位置删除,因此也可用auto index = mp[key] 删除
cache.push_front(make_pair(key,ans));//insert
mp[key] = cache.begin(); //updata
return ans;
}
}
void put(int key, int value) {
//step 1: if_have this key, update
//step 2: if_not_have this key, judge cap is_full
auto index = mp.find(key);
if( ! (index == mp.end()) ) //have this key
{
cache.erase(mp[key]);//erase
cache.push_front(make_pair(key,value)); //put the new invist in the begin
mp[key] = cache.begin(); //
}
else //put (key,value)
{
if(cap == cache.size()) //if cap full
{
//delete back of the list and the mp
auto last_pair = cache.back();
int last_key = last_pair.first;
mp.erase(last_key);
cache.pop_back();
}
//put the new(key,value)
cache.push_front(make_pair(key,value));
mp[key] = cache.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);
*/
还是想说一下,缓存机制LRU,以及LFU的设计与实现在面试中重要的一批,一定要掌握,加油!
上一篇: 程序员代码面试指南读书笔记1