LRU Cache原理和實(shí)現(xiàn)

時間：2019-07-10 09:15:01

關(guān)鍵字： cache 算法 lru

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]原理LeetCode上有著樣一道題目：Design and implement a data structure for Least Recently Used (LRU) cache. It sho

原理

LeetCode上有著樣一道題目：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.
首先我覺得這個題目很有意思，能夠自己實(shí)現(xiàn)一個操作系統(tǒng)中的算法本身就是比較有意思的事情，同時又能夠復(fù)習(xí)一下操作系統(tǒng)的知識，何樂而不為呢。
LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。
1.LRU Cache簡單版

最常見的實(shí)現(xiàn)是使用一個鏈表保存緩存數(shù)據(jù)，如下圖所示：

1)新數(shù)據(jù)插入到鏈表頭部；
2)每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部；
3)當(dāng)鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄。
【命中率】
當(dāng)存在熱點(diǎn)數(shù)據(jù)時，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重。
【復(fù)雜度】
實(shí)現(xiàn)簡單。
【代價】
命中時需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引，然后需要將數(shù)據(jù)移到頭部。

2.LRU Cache復(fù)雜版—LRU-K

LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認(rèn)為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題，其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過K次”。
相比LRU，LRU-K需要多維護(hù)一個隊(duì)列，用于記錄所有緩存數(shù)據(jù)被訪問的歷史。只有當(dāng)數(shù)據(jù)的訪問次數(shù)達(dá)到K次的時候，才將數(shù)據(jù)放入緩存。當(dāng)需要淘汰數(shù)據(jù)時，LRU-K會淘汰第K次訪問時間距當(dāng)前時間最大的數(shù)據(jù)。如下圖所示：

1)數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；
2)如果數(shù)據(jù)在訪問歷史列表里后沒有達(dá)到K次訪問，則按照一定規(guī)則（FIFO，LRU）淘汰；
3)當(dāng)訪問歷史隊(duì)列中的數(shù)據(jù)訪問次數(shù)達(dá)到K次后，將數(shù)據(jù)索引從歷史隊(duì)列刪除，將數(shù)據(jù)移到緩存隊(duì)列中，并緩存此數(shù)據(jù)，緩存隊(duì)列重新按照時間排序；
4)緩存數(shù)據(jù)隊(duì)列中被再次訪問后，重新排序；
5)需要淘汰數(shù)據(jù)時，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)。
實(shí)現(xiàn)

OK，針對本題目，我們給出一段簡單的實(shí)現(xiàn)代碼，在下面的代碼中我們使用map+list的方式來實(shí)現(xiàn)，其復(fù)雜度是O(logN)。其實(shí)，也就是使用紅黑樹+雙向鏈表的方式來實(shí)現(xiàn)，map相當(dāng)于一個紅黑樹，用來負(fù)責(zé)查找一塊Cashe是否已經(jīng)在內(nèi)存中，而list相當(dāng)于一個雙向鏈表，能夠方便地插入和刪除某個元素。我們可以發(fā)現(xiàn)，map的查找效率是O(logN)，list插入刪除的效率是O(1)，因此總體的復(fù)雜度是O(logN)。好了下面上代碼：

#include#include#include#includeusing?namespace?std;??
??
class?LRUCache{??
public:??
????LRUCache(int?capacity)?{??
????????m_capacity?=?capacity?;??
????}??
??
????int?get(int?key)?{??
????????int?retValue?=?-1?;??
????????map<int,?list<pair>?::?iterator>?::iterator?it?=?cachesMap.find(key)?;??
??
?????????//如果在Cashe中，將記錄移動到鏈表的最前端??
????????if?(it?!=?cachesMap.end())??
????????{??
????????????retValue?=?it?->second->second?;??
????????????//移動到最前端??
????????????list<pair>?::?iterator?ptrPair?=?it?->?second?;??
????????????pairtmpPair?=?*ptrPair?;??
????????????caches.erase(ptrPair)?;??
????????????caches.push_front(tmpPair)?;??
??
????????????//修改map中的值??
????????????cachesMap[key]?=?caches.begin()?;??
????????}??
????????return?retValue?;??????????
????}??
??
????void?set(int?key,?int?value)?{??
??
????????map<int,?list<pair>?::?iterator>?::iterator?it?=?cachesMap.find(key)?;??
??
????????if?(it?!=?cachesMap.end())?//已經(jīng)存在其中??
????????{??
?????????????list<pair>?::?iterator?ptrPait?=?it?->second?;??
????????????ptrPait->second?=?value?;??
????????????//移動到最前面??
????????????pairtmpPair?=?*ptrPait?;??
????????????caches.erase(ptrPait)?;??
????????????caches.push_front(tmpPair)?;??
??
????????????//更新map??
????????????cachesMap[key]?=?caches.begin()?;??
????????}??
????????else?//不存在其中??
????????{??
????????????pairtmpPair?=?make_pair(key,?value)?;??
??
????????????if?(m_capacity?==?caches.size())?//已經(jīng)滿??
????????????{??
????????????????int?delKey?=?caches.back().first?;??
????????????????caches.pop_back()?;?//刪除最后一個??
??
????????????????//刪除在map中的相應(yīng)項(xiàng)??
????????????????map<int,?list<pair>?::?iterator>?::iterator?delIt?=?cachesMap.find(delKey)?;??
????????????????cachesMap.erase(delIt)?;??
????????????}??
??
????????????caches.push_front(tmpPair)?;??
????????????cachesMap[key]?=?caches.begin()?;?//更新map??
????????}??
????}??
??
private:??
????int?m_capacity?;????????????????????????????????????????????????????????//cashe的大小??
????list<pair>?caches?;??????????????????????????????????????????//用一個雙鏈表存儲cashe的內(nèi)容??
????map<?int,?list<pair>?::?iterator>?cachesMap?;????????????????//使用map加快查找的速度??
};??
??
int?main(int?argc,?char?**argv)??
{??
????LRUCache?s(2)?;??
????s.set(2,?1)?;??
????s.set(1,?1)?;??
????cout?<<?s.get(2)?<<?endl;??
????s.set(4,?1)?;??
????cout?<<?s.get(1)?<<?endl;??
????cout?<<?s.get(2)?<<?endl;??
????return?0?;??
}

其實(shí)，我們可以發(fā)現(xiàn)，主要的耗時操作就是查找，因此，我們可以使用hash_map來代替map,因此時間復(fù)雜度可以降低到O(1)。

#include#include#include#includeusing?namespace?std;??
using?namespace?stdext;??
??
class?LRUCache{??
public:??
????LRUCache(int?capacity)?{??
????????m_capacity?=?capacity?;??
????}??
??
??
????int?get(int?key)?{??
????????int?retValue?=?-1?;??
????????hash_map<int,?list<pair>?::?iterator>?::iterator?it?=?cachesMap.find(key)?;??
??
??
????????//如果在Cashe中，將記錄移動到鏈表的最前端??
????????if?(it?!=?cachesMap.end())??
????????{??
????????????retValue?=?it?->second->second?;??
????????????//移動到最前端??
????????????list<pair>?::?iterator?ptrPair?=?it?->?second?;??
????????????pairtmpPair?=?*ptrPair?;??
????????????caches.erase(ptrPair)?;??
????????????caches.push_front(tmpPair)?;??
??
??
????????????//修改map中的值??
????????????cachesMap[key]?=?caches.begin()?;??
????????}??
????????return?retValue?;??
????}??
??
??
????void?set(int?key,?int?value)?{??
??
??
????????hash_map<int,?list<pair>?::?iterator>?::iterator?it?=?cachesMap.find(key)?;??
??
??
????????if?(it?!=?cachesMap.end())?//已經(jīng)存在其中??
????????{??
????????????list<pair>?::?iterator?ptrPait?=?it?->second?;??
????????????ptrPait->second?=?value?;??
????????????//移動到最前面??
????????????pairtmpPair?=?*ptrPait?;??
????????????caches.erase(ptrPait)?;??
????????????caches.push_front(tmpPair)?;??
??
??
????????????//更新map??
????????????cachesMap[key]?=?caches.begin()?;??
????????}??
????????else?//不存在其中??
????????{??
????????????pairtmpPair?=?make_pair(key,?value)?;??
??
??
????????????if?(m_capacity?==?caches.size())?//已經(jīng)滿??
????????????{??
????????????????int?delKey?=?caches.back().first?;??
????????????????caches.pop_back()?;?//刪除最后一個??
??
??
????????????????//刪除在map中的相應(yīng)項(xiàng)??
????????????????hash_map<int,?list<pair>?::?iterator>?::iterator?delIt?=?cachesMap.find(delKey)?;??
????????????????cachesMap.erase(delIt)?;??
????????????}??
??
????????????caches.push_front(tmpPair)?;??
????????????cachesMap[key]?=?caches.begin()?;?//更新map??
????????}??
????}??
??
??
private:??
????int?m_capacity?;????????????????????????????????????????????????????????//cashe的大小??
????list<pair>?caches?;??????????????????????????????????????????//用一個雙鏈表存儲cashe的內(nèi)容??
????hash_map<?int,?list<pair>?::?iterator>?cachesMap?;???????????//使用map加快查找的速度??
};??
??
??
int?main(int?argc,?char?**argv)??
{??
????LRUCache?s(2)?;??
????s.set(2,?1)?;??
????s.set(1,?1)?;??
????cout?<<?s.get(2)?<<?endl;??
????s.set(4,?1)?;??
????cout?<<?s.get(1)?<<?endl;??
????cout?<<?s.get(2)?<<?endl;??
????return?0?;??
}