LRU 快取

題目連結

LRU，即Least-Recently-Used。是一種快取記憶體替換策略，是一種快取機制。主要是利用區域性性原理。

區域性性原理分兩種，空間區域性性和時間區域性性。

在一個具有良好時間區域性性的程式中，被參照過一次的記憶體位置很可能在不遠的將來再被多次應用。

在一個具有良好空間區域性性的程式中，如果一個記憶體位置被參照了一次，那麼程式很可能在不遠的將來參照附近的一個記憶體位置。

顯然，LRU是利用到了時間區域性性。

在CSAPP的P434 組相聯快取記憶體中不命中時的行替換 出現。

最近最少使用（LRU）策略會替換最後一次存取時間最久遠的那一行。

題目分析

實現 LRUCache 類：

LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 快取
int get(int key) 如果關鍵字 key 存在於快取中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字 key 已經存在，則變更其資料值 value ；如果不存在，則向快取中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該逐出最久未使用的關鍵字。函數 get 和 put 必須以 O(1) 的平均時間複雜度執行。

來源：力扣（LeetCode）

這是一道很優秀的設計問題，而不是關於某個問題的演演算法。

題目要求你利用相關的知識，設計一個能夠簡單實現LRU 快取機制的類。

根據剛剛所說的CSAPP中的背景知識，可以知道要設計出的類：

需要儲存每個鍵值。（put函數插入，get函數查詢）
鍵值對（key，value）需要用雜湊表來儲存。（O(1) 的平均時間複雜度）

那現在留下的問題就是，如何做到逐出。

佇列

首先可以想到，利用佇列的先進先出原則。

如果使用了，就將它拿出，再插入到佇列中。
隊首為最久未使用，隊尾為最近使用。

那麼如何逐出？拿出怎麼做到？這裡就遇到了難以刪除的問題。

雙向連結串列

所以，下面介紹雙向連結串列的解法。

雙向連結串列可以直接存取到尾部。尾部代表最久未使用。
連結串列方便插入和刪除。
根據鍵值，利用雜湊表能定位到對應的儲存節點。

記憶體漏失？

雙向連結串列可以利用指向關係做到刪除，將節點剔除於連結串列外。

然而我們在剔除後，對於存取的節點來說，還需要再加到頭部節點。而對於沒有存取的節點，我們需要真正刪除它。

所以程式碼中有兩個delete函數，來避免記憶體漏失。

程式碼

class LRUCache {
private:
    struct DoubleLinkNode {
        int key;
        int value;
        DoubleLinkNode* prev;
        DoubleLinkNode* next;
        DoubleLinkNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
        DoubleLinkNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}
    };
    map<int, DoubleLinkNode *> cache;
    DoubleLinkNode* head;
    DoubleLinkNode* tail;
    int capacity;
    int size;

    void addNodeHead(DoubleLinkNode* node)//雙向連結串列頭插法
    {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void deleteNode(DoubleLinkNode* node)//剔除尾節點
    {
        node->next->prev = node->prev;
        node->prev->next = node->next;
    }

    void moveNodeHead(DoubleLinkNode* node)
    {
        deleteNode(node);
        addNodeHead(node);
    }

    DoubleLinkNode* deleteTail()//刪除尾節點
    {
        DoubleLinkNode* temp = tail->prev;
        deleteNode(temp);
        return temp;
    }
public:
    LRUCache(int capacity) 
    {
        this->capacity = capacity;
        size = 0;

        head = new DoubleLinkNode();
        tail = new DoubleLinkNode();

        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) 
    {
        if (cache.count(key))
        {
            moveNodeHead(cache[key]);
            return cache[key]->value;
        }else
        {
            return -1;
        }
    }
    
    void put(int key, int value) 
    {
        if (cache.count(key))
        {
            cache[key]->value = value;
            moveNodeHead(cache[key]);
        }else
        {
            DoubleLinkNode* node = new DoubleLinkNode(key, value);
            addNodeHead(node);
            cache[key] = node;
            size += 1;
            
            if (size > capacity)
            {
                DoubleLinkNode* temp = deleteTail();
                cache.erase(temp->key);
                delete temp;//避免記憶體漏失
                size -= 1;
            }
        }
    }
};

/**
 * 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快取機制

LRU 快取

題目分析

佇列

雙向連結串列

記憶體漏失？

程式碼