天天看點

LRU緩存機制LRU(Least Recently Used)最近少用

目錄

LRU(Least Recently Used)最近少用

what

why

where

how

int get(int key)

void put(int key,int value)

資料結構的選用

具體實作(附詳細注釋)

LRU(Least Recently Used)最近少用

  • what

它是一種緩存淘汰機制,顧名思義,将最近使用次數最少的緩存淘汰

  • why

根據程式的局部性原理,最近經常使用的緩存留在記憶體中,而将最近不常用的緩存換出記憶體,是比較接近理想的一種緩存置換算法

  • where

在凡是帶有緩存的場景中,LRU都可以作為最基本的緩存置換政策,例如:作業系統記憶體的頁面置換、Redis緩存淘汰機制等等

  • how

如何設計一個簡單的LRU緩存算法?

舉個栗子,記憶體容量大小為2,按照key-value形式存儲,結構的頭部為最近最常使用的結點,尾部為最近最少使用的結點

LRU有兩個操作:get和put,每次get和put操作都将查詢的值變為最近最常使用的結點,當put容量已滿時,删除最近最少使用的結點

int get(int key)

  1. 輸入一個key值
  2. 如果key值不存在,則傳回-1
  3. 如果key值存在,則将key-value鍵值對放到結構頭部

void put(int key,int value)

  1. 首先檢視是否存在相同key值的結點
  2. 如果存在,把它删除;
  3. 如果不存在,先檢視容量是否已滿
  4. 如果容量已經滿了,從尾部删除最近最少使用的結點,為新插入結點騰出位置
  5. 如果容量未滿,在最前面放入一個key-value的鍵值對

資料結構的選用

對于get操作的第2.3步

需要通過key值查找是否存在,則應該使得查找的時間複雜度為O(1),鍊式結構肯定不可以,因為需要周遊查找,考慮使用數組、hash

如果查找到key值對應的結點存在,需要将key-value鍵值對放到結構頭部,則應該使得頭部插入的時間複雜度為O(1),考慮使用連結清單

對于put操作的第1步

同get操作

對于put操作的第2步

則應該使得在任意位置删除的時間複雜度為O(1),數組結構肯定不可以,因為删除後需要向前移動補齊,考慮使用鍊式結構

對于put操作的第4步

則需要在尾部删除的時間複雜度為O(1),數組連結清單皆可

對于put操作的第5步

同get操作

綜合考慮,因為需要在任意位置删除的時間複雜度為O(1),數組結構肯定是不能選用的,那麼如果使用鍊式結構,該如何在O(1)時間找到這個要删除的位置呢?

思路是這樣的,

我們需要以時間複雜度O(1)得知Cache中key值對應的結點是否存在,可以使用一個hash映射

我們需要在頭插尾删時間複雜度為O(1),那麼使用雙向連結清單是最好的選擇,想要在雙向連結清單中以時間複雜度O(1)删除某個結點,則首先要找到這個結點對應的疊代器

那麼這個hash映射,key值就是結點的key值,而value值,我們存放key值對應結點的疊代器,通過疊代器調用erase就可以實作以O(1)時間複雜度删除指定位置結點

它的結構圖是下面醬嬸兒的

LRU緩存機制LRU(Least Recently Used)最近少用

使用這種方式我們可以實作以下操作的時間複雜度都是O(1):

在Cache的頭插入、任意位置删除

查找key值對應的結點是否在Cache中

具體實作(附詳細注釋)

class LRUCache {
public:
    list<pair<int,int>> cache;
    unordered_map<int,list<pair<int,int>>::iterator> hash;
    int cap;
    LRUCache(int capacity) :cap(capacity){
    }
    int get(int key) {
        //先看映射中有沒有 沒有 傳回-1
        if(hash.find(key) == hash.end())
            return -1;
        //如果有,取得結點
        pair<int,int> node = *hash[key];
        //通過結點的疊代器,删除
        cache.erase(hash[key]);
        //将結點重新插入到頭部,變為最近最常使用
        cache.push_front(node);
        //更新hash中疊代器的位置
        hash[key] = cache.begin();
        //傳回value值
        return node.second;
    }
    void put(int key, int value) {
        //先看映射中有沒有
        if(hash.find(key) != hash.end()){
            //有 通過疊代器删除
            cache.erase(hash[key]);
        }else{
            //沒有 判斷這次插入是否越界
            if(cap == cache.size()){
                //越界了 
                //注意順序:通過Cache取得key值,删除hash中的該結點
                //在Cache尾巴删除最近最少使用的結點
                hash.erase(cache.back().first);
                cache.pop_back();
            }
        }
        //頭插入
        cache.push_front(make_pair(key,value));
        //更新map的疊代器
        hash[key] = cache.begin();
            
    }
};