一、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)鍵字-值」。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。- 在
O(1)時間復(fù)雜度內(nèi)完成這兩種操作
所用數(shù)據(jù)結(jié)構(gòu)：
為了使 get 與 put 操作的平均時間復(fù)雜度為 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)
運(yù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/
問題描述：
LFUCache(int capacity)- 用數(shù)據(jù)結(jié)構(gòu)的容量capacity初始化對象int get(int key) - 如果鍵存在于緩存中，則獲取鍵的值，否則返回 -1 。void put(int key,int value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當(dāng)緩存達(dá)到其容量時，則應(yīng)該在插入新項之前，使最不經(jīng)常使用的項無效。在此問題中，當(dāng)存在平局（即兩個或更多個鍵具有相同使用頻率）時，應(yīng)該去除 最近最久未使用的鍵。- 「項的使用次數(shù)」就是自插入該項以來對其調(diào)用 get 和 put 函數(shù)的次數(shù)之和。使用次數(shù)會在對應(yīng)項被移除后置為 0 。
- 為了確定最不常使用的鍵，可以為緩存中的每個鍵維護(hù)一個 使用計數(shù)器 。使用計數(shù)最小的鍵是最久未使用的鍵。
- 當(dāng)一個鍵首次插入到緩存中時，它的使用計數(shù)器被設(shè)置為 1 (由于 put 操作)。對緩存中的鍵執(zhí)行 get 或 put 操作，使用計數(shù)器的值將會遞增。
所用數(shù)據(jù)結(jié)構(gòu)：
為了使 get 與 put 操作的平均時間復(fù)雜度為 O(1) ，
- 使用哈希表 (STL
unordered_map) 儲存 “key” 到 “value與frequency” 的關(guān)系映射 (使用 STLpair {value, frequency} 表示) - 使用哈希表 (STL
unordered_map) 儲存 “frequency” 到 “對應(yīng)所有的key” 的關(guān)系映射 (key 使用雙向鏈表，即 STL list 存儲) - 使用哈希表 (STL
unordered_map) 儲存 “key” 到 “2 中存儲 key 所用 list 中對應(yīng)iterator” 的關(guān)系映射
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
代碼實現(xiàn)：
#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)
運(yù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)
到此這篇關(guān)于C++ 實現(xiàn)LRU 與 LFU 的緩存算法的文章就介紹到這了,更多相關(guān)C++ 實現(xiàn)LRU 與 LFU 緩存算法內(nèi)容請搜索html5模板網(wǎng)以前的文章希望大家以后多多支持html5模板網(wǎng)！
【網(wǎng)站聲明】本站部分內(nèi)容來源于互聯(lián)網(wǎng),旨在幫助大家更快的解決問題，如果有圖片或者內(nèi)容侵犯了您的權(quán)益，請聯(lián)系我們刪除處理，感謝您的支持！