目標(biāo)
- 緩存的概念
- 緩存的數(shù)據(jù)淘汰策略
- LRU策略的實(shí)現(xiàn)
- 時(shí)間和空間復(fù)雜度分析
- 優(yōu)化的可能性
- 近似LRU算法
Using Redis as an LRU cache
image.png
題目示例
LeetCode 146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
基本概念
-
什么是緩存，緩存有什么特點(diǎn)？
舉個(gè)例子，去圖書(shū)館查資料，一般情況下我們會(huì)集中把我們有可能查閱的幾本書(shū)從書(shū)架取下來(lái)，放在我們的桌面上，以便交叉查閱，從而避免頻繁的從座位上跑到書(shū)架旁去取書(shū)。在這個(gè)例子里，書(shū)桌所扮演的就是緩存的角色。
緩存有兩個(gè)特點(diǎn)：
- 能在某種程度上降低訪問(wèn)數(shù)據(jù)的成本；
- 其容量遠(yuǎn)小于外部存儲(chǔ)的容量，如本例子中，書(shū)桌上能容納的書(shū)本數(shù)就遠(yuǎn)小于書(shū)架的。
體現(xiàn)的思想
- 空間換時(shí)間
- LRU是什么？
LRU緩存是一種以LRU策略(距離當(dāng)前最久沒(méi)使用過(guò)的數(shù)據(jù)應(yīng)該被淘汰)為緩存策略的緩存。
而所謂的緩存策略，就是當(dāng)緩存滿了之后，又有新數(shù)據(jù)需要加入到緩存中時(shí)，我們?cè)趺磸木彺嬷袆h除舊數(shù)據(jù)為新數(shù)據(jù)騰出空間的策略。
LRU，Least Recently Used的簡(jiǎn)寫(xiě)，即近期最少使用算法。該算法依據(jù)于程序的局部性原理， 其淘汰舊數(shù)據(jù)的策略是，距離當(dāng)前最久沒(méi)有被訪問(wèn)過(guò)的數(shù)據(jù)應(yīng)該被淘汰。
實(shí)現(xiàn)原理
- 實(shí)現(xiàn)LRU的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
unordered_map + double linked list
（1）維護(hù)一個(gè)雙向鏈表，該鏈表將緩存中的數(shù)據(jù)塊按訪問(wèn)時(shí)間從新到舊排列起來(lái)（由于雙向鏈表節(jié)點(diǎn)的交換代價(jià)很低，所以使用雙向鏈表作為主要數(shù)據(jù)結(jié)構(gòu)）
節(jié)點(diǎn)為包含key,value的結(jié)構(gòu)體（一條記錄）
（2）使用哈希表（map）保證緩存中數(shù)據(jù)的訪問(wèn)速度（由于引入哈希表可以提高查詢速度，所以使用哈希表作為輔助數(shù)據(jù)結(jié)構(gòu)）
map中的一個(gè)元素包含鍵值key以及鏈表中鍵值為key的迭代器（指針），通過(guò)key查找記錄的地址，即可O(1)時(shí)間內(nèi)訪問(wèn)鏈表中訪問(wèn)的記錄
接口描述
int get(int key)；
- 功能
在哈希表中查找鍵值為key的元素，如果不存在返回-1；如果存在返回該key對(duì)應(yīng)的value值； - 實(shí)現(xiàn)
這里說(shuō)存在key的情況，如何get：
step1: 將鍵值為key的記錄與鏈表首元交換位置;
step2: 更新哈希表中鍵值為key的迭代器
void put(int key, int value)；
- 功能與實(shí)現(xiàn)
將key,value這條記錄放入緩存，如果該記錄已經(jīng)在緩存中，更新該記錄到緩存鏈表頭部；如果不在緩存中且緩存未滿，插入緩存鏈表頭部，如果緩存滿，刪除尾部數(shù)據(jù)。
代碼細(xì)節(jié)
class LRUCache {
private:
typedef int key_t;
typedef int value_t;
typedef struct{
key_t key;
value_t value;
} Node_t;
typedef list<Node_t> cacheList_t;
typedef map<key_t,cacheList_t::iterator> map_t;
int m_capacity;
cacheList_t m_cacheList;
map_t m_mp;
public:
LRUCache(int capacity) : m_capacity(capacity){
}
int get(int key) {
auto it = m_mp.find(key);
// not cached
if(it == m_mp.end()) return -1;
// cached
else{
auto list_it = m_mp[key];
Node_t node = {key,list_it->value};
m_cacheList.erase(list_it);
m_cacheList.push_front(node);
m_mp[key] = m_cacheList.begin();
return m_cacheList.begin()->value;
}
}
void put(int key, int value) {
auto it = m_mp.find(key);
// cached
if(it != m_mp.end()){
auto listIt = m_mp[key];
// delete the cached node, and then insert it to the list head
Node_t node = {key, value};
m_cacheList.erase(listIt);
m_cacheList.push_front(node);
m_mp[key] = m_cacheList.begin();
}
// not cached
else{
// cache is full
if(m_cacheList.size() == m_capacity){
m_mp.erase(m_cacheList.back().key);
m_cacheList.pop_back();
}
// cache is not full
Node_t node = {key,value};
m_cacheList.push_front(node);
m_mp[key] = m_cacheList.begin();
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
優(yōu)化的可能性
- get命中數(shù)據(jù)時(shí)，可以用移動(dòng)構(gòu)造的方式替代臨時(shí)對(duì)象的拷貝
