LeetCode #146 LRU cache – 陪你刷題

這是第一次寫專門探討單一題目的文章，本篇探討 LeetCode #146 的題目，要你設計一個資料結構實作出 LRU ，根據 LeetCode 的統計，這題在面試中有高機率會出現，尤其是亞馬遜。這題可能以其他應用情境來包裝，但本質上就是要你設計一個 LRU cache ，也因此讓我想要寫篇文章好好探討這題。

題目說明

LRU 全名為 least recently used ，如果 cache 容量滿了，最久沒使用的資料將被刪除，以空出容量將新資放入 cache 中。

題目要求實現 get 與 put 的操作，前者傳入 key 並回傳對應的 value ，後者則是新增 key 與對應的 value 到 cache 中，這兩者操作需要在 O(1) 完成。

資料結構需求

首先 get 需要在 O(1) 時間完成，直覺想到使用 hash table ，即採用 C++ STL unordered_map ，可以在 O(1) 時間內存 key 和對應 value ，又能在 O(1) 時間內依照 key 得到對應 value 。

但在 get() 和 put() 的運作背後，還包含維護 LRU ，某筆資料被查詢或是新增，就要將該筆資料從 cache 中放到最近才被使用的位置，每當 cache 滿了，優先移除 cache 中最近最少使用的資料，這是無法只透過 hash table 做到的。

維護 LRU cache 直覺想到使用 doubly linked list ，依照最近使用的順序來排序，可以在 O(1) 時間來管理 cache 內資料順序，但在 linked list 上搜尋 key 需要 O(n) 的時間。

兩種方法都可以完美的解決部份問題，沒有一種資料結構可以完美解決所有需求，我們需要做任何取捨嗎？不用！小孩子才做選擇，兩個資料結構都拿來使用，各取彼此的優點。

到這邊先歸納需要的操作有哪些：

依照 key 取得對應 value 。
新增 key 與對應 value 。
找出最近最少被使用的 (key, value)。
如果 cache 滿了，刪除最近最少被使用的 (key, value)。
更新剛剛被使用的 (key, value) 在 cache 中的位置。

前兩項操作透過 hash table 即可完成，第三項操作直接取 doubly linked list 尾端資料即可（最近最少被使用的資料放在 List 開頭或是結尾都可以，本篇將較新資料放於 list 開頭位置），第四項操作利用第三項即可完成。

第五項操作比較麻煩，為了在 O(1) 內時間由 key 查詢到資料在 linked list 的位置，還需要一個 hash table 來協助，可以由 key 直接查詢資料在 linked list 的位置，這邊不能單純紀錄 linked list 的 index ，有 index 仍舊要從頭開始走訪，應該直接儲存 key 對應 linked list node ，透過 list::iterator 即可滿足這邊的需求， iterator 如同一個 pointer 指向指定的 linked list node ，另一個好處是 iterator 並不會因為 list 上有新增或移除而失效，只有該 iterator 代表的元素被移除，該 iterator 才會跟著失效。

至此可以歸納出建立並維護 LRU cache 需要以下三種資料結構

Hash Table unordered_map<int, int> : 用於查詢 key 與 value
Doubly Linked List list<int> : 用於維護 cache 的順序，list 開頭位置存放最近使用的資料，當需要移除資料時，優先移除尾端資料
Hash Table unordered_map<int, list<int>::iterator> : 用於查詢 key 與其在 list 上的位置，方便做 cache 的更新。

get() 與 put() 的設計

接著思考 get() 與 put() ，執行這兩個動作，都會影響到 cache 和兩個 hash table ，這邊較好的作法，將操作資料結構的細節封裝起來，這個動作有助於程式碼的理解與維護，也加強資料的安全性。

get value from cache

題目要求實現 int get (int key) ，以下探討這個 function 的設計細節。

查詢是否存在 key ?

存在的話更新該資料在 cache 中位置 (包含由 cache 中移除 key ，並新增 key 到 cache 前端）
不存在直接回傳 -1

put value in cache

題目要求實現 void put (int key, int value) ，以下探討這個 function 的設計細節。

查詢是否存在 key
存在的話：
1. 更新 hash table 中對應 value 。
2. 更新該資料在 cache 中位置 (包含由 cache 中移除 key ，並新增 key 到 cache 前端）。
不存在的話：
1. 先確認 cache size 是否滿了，滿了則移除最久未使用資料。
2. 新增 hash table 中對應 value 。
3. 新增該資料到 cache 前端。

將 cache 有關的操作抽象化為 interface ，藉此保護 cache ，根據上面所做設計，跟 cache 有關的有以下操作：

void removeKey (int key) ：負責將 key 由 cache 中移除
void insertKey (int key) ：負責將 key 新增到 cache 前端
void evict() ：將最久未使用的資料移除

class LRUCache {
public:
    int size;
    unordered_map<int, int> dataRecord;
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        if (dataRecord.find (key) == dataRecord.end())
            return -1;

        removeKey (key);
        insertKey (key);
        return dataRecord[key];
    }

    void put(int key, int value) {
        if (dataRecord.find (key) != dataRecord.end ())
        {
            dataRecord[key] = value;
            removeKey (key);
            insertKey (key);
        }
        else
        {
            if (dataRecord.size () == size)
            {
                envict ();
            }
            dataRecord[key] = value;
            insertKey (key);
        }
    }

private:
    list<int> cache;
    unordered_map<int, list<int>::iterator> cacheRecord;

    void removeKey (int key) {
        cache.erase(cacheRecord[key]);
    }

    void insertKey (int key)
    {
        cache.push_front(key);
        cacheRecord[key] = cache.begin();
    }

    void envict ()
    {
        dataRecord.erase (cache.back());
        cacheRecord.erase (cache.back());
        cache.pop_back ();
    }
};

再優化

觀察所需的3個資料結構，其實可以將 doubly linked list 和儲存 key, value 的 hash table 做結合，<key, value> 作為 linked list node 儲存的值，整合為 list<pair<int, int>> ，當 key 由 cache 移除，key 對應的 value 也被移除，這個方法相比於前述方法，減少使用一個 hash table 。

class LRUCache {
public:
    int size;
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        if (!findKey (key))
            return -1;

        updateKey (key);
        return getValue (key);
    }

    void put(int key, int value) {
        if ( findKey (key))
        {
            updateKeyAndVal (key, value);
        }
        else
        {
            full_evict ();
            insertKeyAndVal (key, value);
        }
    }

private:
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> cacheRecord;
    bool findKey (int key)
    {
        auto itr = cacheRecord.find (key);
        if (itr != cacheRecord.end())
        {
            return true;
        }
        return false;
    }
    int getValue (int key)
    {
        return cacheRecord[key]->second;
    }

    void updateKey (int key)
    {
        // Move node to the beginning of linked list
        cache.splice (cache.begin(), cache, cacheRecord[key]);
        cacheRecord[key] = cache.begin ();
    }

    void updateKeyAndVal (int key, int value)
    {
        updateKey (key);
        cache.begin()->second = value;
    }
    void insertKeyAndVal (int key, int value)
    {
        cache.push_front(pair<int, int>(key, value));
        cacheRecord[key] = cache.begin ();
    }

    void full_evict ()
    {
        if (cacheRecord.size () == size)
        {
            int key = cache.back().first;
            cacheRecord.erase (key);
            cache.pop_back ();
        }
    }
};

Reference

Leetcode #146. LRU Cache
Cracking the coding interview, 6th edition, Chapter 16.

Updated on 2022-04-23 16:21:41 星期六