C++ 實現(xiàn)LRU 與 LFU 的緩存算法

更新時間：2021年09月13日 11:11:31 作者：Ito Schum

設計和實現(xiàn)一個LRU 緩存機制。其支持獲取數(shù)據(jù) get 和寫入數(shù)據(jù) put，設計并實現(xiàn)最少訪問頻率（LFU）緩存的數(shù)據(jù)結(jié)構(gòu)。LFU的每個數(shù)據(jù)塊都有一個引用計數(shù)，所有數(shù)據(jù)塊按照引用計數(shù)排序，具有相同引用計數(shù)的數(shù)據(jù)塊則按照時間進行排序。其支持get 和 put，具體了解請看下文

一、LRU (Least Recently Used) 緩存

詳見 LeetCode Q146

https:// leetcode.com/problems/l ru-cache/

https:// leetcode-cn.com/problem s/lru-cache/

問題描述：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當緩存容量達到上限時，它應該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
在 O(1) 時間復雜度內(nèi)完成這兩種操作

所用數(shù)據(jù)結(jié)構(gòu)：

為了使 get 與 put 操作的平均時間復雜度為 O(1) ，

使用雙向鏈表 (STL list ) 儲存緩存內(nèi)容 (使用 STL pair {key, value} 表示),
使用哈希表 (STL unordered_map ) 儲存 “key” 到 “pair iterator ” 的關(guān)系映射

typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;

流程圖：

get function

put function

代碼實現(xiàn)：

#include <iostream>
#include <list>
#include <unordered_map>

typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;

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

    int get(int key) {
        CacheMap::iterator cache_itr = _cacheMap.find(key);
        if (cache_itr == _cacheMap.end() ) { 
            return -1; 
        }
        makeMostRecent(key, _cacheMap[key]->second);
        LRUList::iterator list_itr = _LRUList.end();
        --list_itr;
        return list_itr->second;
    }

    void put(int key, int value) {
        if (_cacheMap.find(key) != _cacheMap.end()) {
            makeMostRecent(key, value);
            return;
        }
        if (_LRUList.size() >= _capacity) {
            removeLeastRecentTask(key);
        }
        addMostRecentTask(key, value);
    }

private:
    void makeMostRecent(int key, int value) {
        _LRUList.erase(_cacheMap[key]);
        _LRUList.push_back(std::make_pair(key, value) );
        LRUList::iterator list_itr = _LRUList.end();
        _cacheMap[key] = --list_itr;
    }

    void removeLeastRecentTask(int key) {
        int keyToRemove = _LRUList.begin()->first;
        _LRUList.erase(_LRUList.begin());
        _cacheMap.erase(keyToRemove);
    }

    void addMostRecentTask(int key, int value) {
        _LRUList.push_back(std::make_pair(key, value) );
        LRUList::iterator list_itr = _LRUList.end();
        _cacheMap[key] = --list_itr;
    }

    int _capacity;
    LRUList _LRUList;
    CacheMap _cacheMap;
};

// n = item number of the LRU list, aka capacity
// Time: O(1)
// Space: O(n)

運行測試：

Accepted
22/22 cases passed (412 ms)
Your runtime beats 69.45 % of cpp submissions
Your memory usage beats 48.08 % of cpp submissions (174 MB)

二、LFU (Least Frequently Used) 緩存

詳見 LeetCode Q460

https:// leetcode.com/problems/l fu-cache/