LRU（Least Recently Used）緩存算法的實(shí)現(xiàn)
LRU就是Least Recently Used，即最近最少使用，是一種常用的頁(yè)面置換算法，將最近長(zhǎng)時(shí)間未使用的頁(yè)面淘汰，其實(shí)也很簡(jiǎn)單，就是要將不受歡迎的頁(yè)面及時(shí)淘汰，不讓它占著茅坑不拉shit，浪費(fèi)資源。
LRU是一種常見(jiàn)的頁(yè)面置換算法，在計(jì)算中，所有的文件操作都要放在內(nèi)存中進(jìn)行，然而計(jì)算機(jī)內(nèi)存大小是固定的，所以我們不可能把所有的文件都加載到內(nèi)存，因此我們需要制定一種策略對(duì)加入到內(nèi)存中的文件進(jìn)項(xiàng)選擇。
常見(jiàn)的頁(yè)面置換算法有如下幾種：
- LRU 最近最久未使用
- FIFO 先進(jìn)先出置換算法 類(lèi)似隊(duì)列
- OPT 最佳置換算法 (理想中存在的)
- NRU Clock置換算法
- LFU 最少使用置換算法
- PBA 頁(yè)面緩沖算法
LRU原理
LRU的設(shè)計(jì)原理就是，當(dāng)數(shù)據(jù)在最近一段時(shí)間經(jīng)常被訪問(wèn)，那么它在以后也會(huì)經(jīng)常被訪問(wèn)。這就意味著，如果經(jīng)常訪問(wèn)的數(shù)據(jù)，我們需要然其能夠快速命中，而不常訪問(wèn)的數(shù)據(jù)，我們?cè)谌萘砍鱿拗苾?nèi)，要將其淘汰。
其核心就是利用棧，進(jìn)行操作，其中主要有兩項(xiàng)操作，get和put
get
get時(shí)，若棧中有值則將該值的key提到棧頂，沒(méi)有時(shí)則返回null
put
棧未滿時(shí)，若棧中有要put的key，則更新此key對(duì)應(yīng)的value，并將該鍵值提到棧頂，若無(wú)要put的key，直接入棧
棧滿時(shí)，若棧中有要put的key，則更新此key對(duì)應(yīng)的value，并將該鍵值提到棧頂;若棧中沒(méi)有put的key 時(shí)，去掉棧底元素，將put的值入到棧頂
解法：維護(hù)一個(gè)數(shù)組，提供 get 和 put 方法，并且限定 max 數(shù)量。
使用時(shí)，get 可以標(biāo)記某個(gè)元素是最新使用的，提升它去第一項(xiàng)。put 可以加入某個(gè)key-value，但需要判斷是否已經(jīng)到最大限制 max
若未到能直接往數(shù)組第一項(xiàng)里插入 若到了最大限制 max，則需要淘汰數(shù)據(jù)尾端一個(gè)元素。
- LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
- cache.put(1, 1);
- cache.put(2, 2);
- cache.get(1); // 返回 1
- cache.put(3, 3); // 該操作會(huì)使得密鑰 2 作廢
- cache.get(2); // 返回 -1 (未找到)
- cache.put(4, 4); // 該操作會(huì)使得密鑰 1 作廢
- cache.get(1); // 返回 -1 (未找到)
- cache.get(3); // 返回 3
- cache.get(4); // 返回 4
LRU 算法設(shè)計(jì)
分析上面的操作過(guò)程，要讓 put 和 get 方法的時(shí)間復(fù)雜度為 O(1)，我們可以總結(jié)出 cache 這個(gè)數(shù)據(jù)結(jié)構(gòu)必要的條件：查找快，插入快，刪除快，有順序之分。
因?yàn)轱@然 cache 必須有順序之分，以區(qū)分最近使用的和久未使用的數(shù)據(jù);而且我們要在 cache 中查找鍵是否已存在;如果容量滿了要?jiǎng)h除最后一個(gè)數(shù)據(jù);每次訪問(wèn)還要把數(shù)據(jù)插入到隊(duì)頭。
那么，什么數(shù)據(jù)結(jié)構(gòu)同時(shí)符合上述條件呢?哈希表查找快，但是數(shù)據(jù)無(wú)固定順序;鏈表有順序之分，插入刪除快，但是查找慢。所以結(jié)合一下，形成一種新的數(shù)據(jù)結(jié)構(gòu)：哈希鏈表。
LRU 緩存算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表，雙向鏈表和哈希表的結(jié)合體。這個(gè)數(shù)據(jù)結(jié)構(gòu)長(zhǎng)這樣：
js 實(shí)現(xiàn)
- 具體代碼 一般的解法，通過(guò)維護(hù)一個(gè)數(shù)組，數(shù)組項(xiàng)存放了 key-value 鍵值對(duì)對(duì)象，每次需要遍歷去尋找 key 值所在的數(shù)組下標(biāo)操作。
已經(jīng)通過(guò) leetCode 146 的檢測(cè)。執(zhí)行用時(shí) : 720 ms。內(nèi)存消耗 : 58.5 MB。
- function LRUCache(capacity) {
- this.capacity = capacity; // 最大限制
- this.cache = [];
- };
- /**
- * @param {number} key
- * @return {number}
- */
- LRUCache.prototype.get = function (key) {
- let index = this.cache.findIndex((item) => item.key === key);
- if (index === -1) {
- return -1;
- }
- // 刪除此元素后插入到數(shù)組第一項(xiàng)
- let value = this.cache[index].value;
- this.cache.splice(index, 1);
- this.cache.unshift({
- key,
- value,
- });
- return value;
- };
- /**
- * @param {number} key
- * @param {number} value
- * @return {void}
- */
- LRUCache.prototype.put = function (key, value) {
- let index = this.cache.findIndex((item) => item.key === key);
- // 想要插入的數(shù)據(jù)已經(jīng)存在了，那么直接提升它就可以
- if (index > -1) {
- this.cache.splice(index, 1);
- } else if (this.cache.length >= this.capacity) {
- // 若已經(jīng)到達(dá)最大限制，先淘汰一個(gè)最久沒(méi)有使用的
- this.cache.pop();
- }
- this.cache.unshift({ key, value });
- };
上面的做法其實(shí)有變種，可以通過(guò)一個(gè)對(duì)象來(lái)存鍵值對(duì)，一個(gè)數(shù)組來(lái)存放鍵的順序。
- 進(jìn)階要求O(1)
時(shí)間復(fù)雜度 O(1)，那就不能數(shù)組遍歷去查找 key 值?？梢杂?ES6 的 Map 來(lái)解了，因?yàn)?Map 既能保持鍵值對(duì)，還能記住插入順序。
- function LRUCache(capacity) {
- this.cache = new Map();
- this.capacity = capacity; // 最大限制
- };
- LRUCache.prototype.get = function (key) {
- if (this.cache.has(key)) {
- // 存在即更新
- let temp = this.cache.get(key);
- this.cache.delete(key);
- this.cache.set(key, temp);
- return temp;
- }
- return -1;
- };
- LRUCache.prototype.put = function (key, value) {
- if (this.cache.has(key)) {
- // 存在即更新（刪除后加入）
- this.cache.delete(key);
- } else if (this.cache.size >= this.capacity) {
- // 不存在即加入
- // 緩存超過(guò)最大值，則移除最近沒(méi)有使用的
- this.cache.delete(this.cache.keys().next().value);
- }
- this.cache.set(key, value);
- };
