原理
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.
首先我覺得這個題目很有意思，能夠自己實現(xiàn)一個操作系統(tǒng)中的算法本身就是比較有意思的事情，同時又能夠復習一下操作系統(tǒng)的知識，何樂而不為呢。
LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。
1.LRU Cache簡單版
最常見的實現(xiàn)是使用一個鏈表保存緩存數(shù)據(jù)，如下圖所示：
1)新數(shù)據(jù)插入到鏈表頭部；
2)每當緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部；
3)當鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄。
【命中率】
當存在熱點數(shù)據(jù)時，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。
【復雜度】
實現(xiàn)簡單。
【代價】
命中時需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引，然后需要將數(shù)據(jù)移到頭部。
2.LRU Cache復雜版—LRU-K
LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題，其核心思想是將“最近使用過1次”的判斷標準擴展為“最近使用過K次”。
相比LRU，LRU-K需要多維護一個隊列，用于記錄所有緩存數(shù)據(jù)被訪問的歷史。只有當數(shù)據(jù)的訪問次數(shù)達到K次的時候，才將數(shù)據(jù)放入緩存。當需要淘汰數(shù)據(jù)時，LRU-K會淘汰第K次訪問時間距當前時間最大的數(shù)據(jù)。如下圖所示：
1)數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；
2)如果數(shù)據(jù)在訪問歷史列表里后沒有達到K次訪問，則按照一定規(guī)則（FIFO，LRU）淘汰；
3)當訪問歷史隊列中的數(shù)據(jù)訪問次數(shù)達到K次后，將數(shù)據(jù)索引從歷史隊列刪除，將數(shù)據(jù)移到緩存隊列中，并緩存此數(shù)據(jù)，緩存隊列重新按照時間排序；
4)緩存數(shù)據(jù)隊列中被再次訪問后，重新排序；
5)需要淘汰數(shù)據(jù)時，淘汰緩存隊列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)。
實現(xiàn)
OK，針對本題目，我們給出一段簡單的實現(xiàn)代碼，在下面的代碼中我們使用map+list的方式來實現(xiàn)，其復雜度是O(logN)。其實，也就是使用紅黑樹+雙向鏈表的方式來實現(xiàn)，map相當于一個紅黑樹，用來負責查找一塊Cashe是否已經(jīng)在內(nèi)存中，而list相當于一個雙向鏈表，能夠方便地插入和刪除某個元素。我們可以發(fā)現(xiàn)，map的查找效率是O(logN)，list插入刪除的效率是O(1)，因此總體的復雜度是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中的相應項??
????????????????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?;??
}其實，我們可以發(fā)現(xiàn)，主要的耗時操作就是查找，因此，我們可以使用hash_map來代替map,因此時間復雜度可以降低到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中的相應項??
????????????????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?;??
}
下載文檔
