欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU(最近最久未使用)数据缓存机制的实现

程序员文章站 2024-02-27 16:11:57
...

面试常问
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的设计与实现在面试中重要的一批,一定要掌握,加油!LRU(最近最久未使用)数据缓存机制的实现