溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關C++如何實現LRU與LFU的緩存算法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
詳見 LeetCode Q146
https:// leetcode.com/problems/l ru-cache/
https:// leetcode-cn.com/problem s/lru-cache/
問題描述：
LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字已經存在，則變更其數據值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。
在 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)
詳見 LeetCode Q460
https:// leetcode.com/problems/l fu-cache/
https:// leetcode-cn.com/problem s/lru-cache/
問題描述：
LFUCache(int capacity) - 用數據結構的容量 capacity 初始化對象
int get(int key) - 如果鍵存在于緩存中，則獲取鍵的值，否則返回 -1 。
void put(int key, int value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當緩存達到其容量時，則應該在插入新項之前，使最不經常使用的項無效。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除 最近最久未使用的鍵。
「項的使用次數」就是自插入該項以來對其調用 get 和 put 函數的次數之和。使用次數會在對應項被移除后置為 0 。
為了確定最不常使用的鍵，可以為緩存中的每個鍵維護一個 使用計數器 。使用計數最小的鍵是最久未使用的鍵。
當一個鍵首次插入到緩存中時，它的使用計數器被設置為 1 (由于 put 操作)。對緩存中的鍵執行 get 或 put 操作，使用計數器的值將會遞增。
所用數據結構：
為了使 get 與 put 操作的平均時間復雜度為 O(1) ，
使用哈希表 (STL unordered_map ) 儲存 “key” 到 “value 與 frequency” 的關系映射 (使用 STL pair {value, frequency} 表示)
使用哈希表 (STL unordered_map ) 儲存 “frequency” 到 “對應所有的 key” 的關系映射 (key 使用雙向鏈表，即 STL list 存儲)
使用哈希表 (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的緩存算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
