C++ 實現LRU 與 LFU 的緩存算法

Posted on by

一、LRU (Least Recently Used) 緩存

詳見 LeetCode Q146

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

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

問題描述：

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

所用數據結構：

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

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

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

代碼實現：

#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/

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

問題描述：

  1. LFUCache(int capacity) – 用數據結構的容量 capacity 初始化對象
  2. int get(int key) – 如果鍵存在於緩存中，則獲取鍵的值，否則返回 -1 。
  3. void put(int key, int value) – 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當緩存達到其容量時，則應該在插入新項之前，使最不經常使用的項無效。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除 最近最久未使用的鍵。
  4. 「項的使用次數」就是自插入該項以來對其調用 get 和 put 函數的次數之和。使用次數會在對應項被移除後置為 0 。
  5. 為瞭確定最不常使用的鍵，可以為緩存中的每個鍵維護一個 使用計數器 。使用計數最小的鍵是最久未使用的鍵。
  6. 當一個鍵首次插入到緩存中時，它的使用計數器被設置為 1 (由於 put 操作)。對緩存中的鍵執行 get 或 put 操作，使用計數器的值將會遞增。

所用數據結構：

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

  1. 使用哈希表 (STL unordered_map ) 儲存 “key” 到 “value 與 frequency” 的關系映射 (使用 STL pair {value, frequency} 表示)
  2. 使用哈希表 (STL unordered_map ) 儲存 “frequency” 到 “對應所有的 key” 的關系映射 (key 使用雙向鏈表，即 STL list 存儲)
  3. 使用哈希表 (STL unordered_map ) 儲存 “key” 到 “2 中存儲 key 所用 list 中對應 iterator ” 的關系映射
std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
std::unordered_map<int, std::list<int> > _freqToKeyList;
std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;

流程圖：

  • get function

  • put function

代碼實現：

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

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

    int get(int key) {
        // If key doesn't exist
        if (_keyToValFreq.find(key) == _keyToValFreq.end() ) {
            return -1;
        }
        // if key exists, increse frequency and reorder
        increaseFreq(key);
        return _keyToValFreq[key].first;
    }

    void put(int key, int value) {
        if (_capacity <= 0) { return; }
        // if key exists
        if (_keyToValFreq.find(key) != _keyToValFreq.end() ) {
            _keyToValFreq[key].first = value;
            increaseFreq(key);
            return;
        }
        // if key doesn't exist
        // if reached hashmap's max capacity, remove the LFU (LRU if tie)
        if (_keyToValFreq.size() >= _capacity) {
            int keyToRmove = _freqToKeyList[_minFreq].back();
            _freqToKeyList[_minFreq].pop_back();
            _keyToKeyListItr.erase(keyToRmove);
            _keyToValFreq.erase(keyToRmove);
        }
        // Then add new item with frequency = 1
        addNewTask(key, value);
    }

    void increaseFreq(int key) {
        // Update the freq in the pair
        int oldFreq = _keyToValFreq[key].second++;

        // Detele the old freq by itr
        _freqToKeyList[oldFreq].erase(_keyToKeyListItr[key]);
        // Add the new freq and re-assign the itr
        _freqToKeyList[oldFreq + 1].emplace_front(key);
        _keyToKeyListItr[key] = _freqToKeyList[oldFreq + 1].begin();

        // Update minFreq
        if (_freqToKeyList[_minFreq].empty() ) {
            _minFreq = oldFreq + 1;
        }
    }

    void addNewTask(int key, int value) {
        // Add new key-value/freq to all hashmaps
        _minFreq = 1;
        _keyToValFreq[key] = std::make_pair(value, _minFreq);
        _freqToKeyList[_minFreq].emplace_front(key);
        _keyToKeyListItr[key] = _freqToKeyList[_minFreq].begin();
    }

private:
    int _capacity;
    int _minFreq;
    std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
    std::unordered_map<int, std::list<int> > _freqToKeyList;
    std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;
};

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

運行測試：

Accepted
24/24 cases passed (464 ms)
Your runtime beats 72.37 % of cpp submissions
Your memory usage beats 45.99 % of cpp submissions (186.7 MB)

到此這篇關於C++ 實現LRU 與 LFU 的緩存算法的文章就介紹到這瞭,更多相關C++ 實現LRU 與 LFU 緩存算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：