LeetCode #146 LRU cache – 陪你刷題

這是第一次寫專門探討單一題目的文章,本篇探討 LeetCode #146 的題目,要你設計一個資料結構實作出 LRU ,根據 LeetCode 的統計,這題在面試中有高機率會出現,尤其是亞馬遜,而我自己在接受亞馬遜的 online assessment 測驗,也真的遇到這題!雖然測驗中是以其他應用情境來包裝,但本質上就是要你設計一個 LRU cache ,當時我在十多個測資中,錯了其中一個,測資是隱藏的,所以也不了解我錯的原因是什麼,也因此讓我想要寫篇文章好好探討這題。

題目說明

LRU 全名為 less 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 滿了,優先移除 cache 尾端的資料,這是無法只透過 unordered_map 做到的,依照前面描述的場景,需要支援以下處理:

  1. 能將資料由任意位置移到開頭
  2. 能移除尾端資料
  3. 能新增資料到開頭

(較新的資料放在開頭或是結尾都可以,本篇將較新資料放於 list 開頭位置)

最符合的資料結構就屬於 doubly linked list ,在 C++ STL 中 std::list 即為 doubly linked list ,但是題目要求在 O(1) 內完成,在 linked list 上找尋資料需要 O(n) ...

為了在 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 才會跟著失效 。

至此可以歸納出整個 LFU cache 需要以下三種資料結構

  1. unordered_map<int, int> : 用於查詢 key 與 value
  2. list<int> : 用於維護 cache 的順序,list 開頭位置存放最近使用的資料,當需要移除資料時,優先移除尾端資料
  3. 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 的設計細節。

  1. 查詢是否存在 key
  2. 存在的話更新該資料在 cache 中位置 (包含由 cache 中移除 key ,並新增 key 到 cache 前端)
  3. 不存在直接回傳 -1

put value in cache

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

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

跟 cache 有關的操作,我會將他抽象化為 interface ,藉此保護 cache ,根據上面所做設計,跟 cache 有關的有以下操作:

  1. void removeKey (int key) :負責將 key 由 cache 中移除
  2. void insertKey (int key) :負責將 key 新增到 cache 前端
  3. 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 做結合,不必要分成兩個,整合為 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

  1. 146. LRU Cache