資訊專欄INFORMATION COLUMN
摘要：最近在看的源碼，不得不說的是，的源碼十分優(yōu)雅簡潔，下面就來分享下的緩存利用的算法算法。關于算法的具體流程，可以來看下這個，這個可視化過程，模擬了算法進行調(diào)度的過程。
最近在看Vue的源碼，不得不說的是，Vue的源碼十分優(yōu)雅簡潔，下面就來分享下Vue的緩存利用的算法LRU算法。
LRU算法LRU是Least recently used的簡寫，主要原理是根據(jù)歷史訪問記錄來淘汰數(shù)據(jù)，說白了就是這個算法認為如果數(shù)據(jù)被訪問過，那么將來被訪問的幾率也高。其存儲結構是一個雙鏈表，最近被訪問到的放在雙鏈表的尾部，頭部放的就是最早被訪問到數(shù)據(jù)。關于算法的具體流程，可以來看下這個，這個可視化過程，模擬了lru算法進行調(diào)度的過程。
缺頁數(shù)lru在筆試題中也會經(jīng)常出現(xiàn)，經(jīng)常會考到的那就是缺頁數(shù)，例如頁面訪問序列為：2,3,2,1,5,2,4,5,3,2,5,2， 分配給某個進程3頁內(nèi)存，求其缺頁次數(shù)。
缺頁數(shù)可以理解為，內(nèi)存不滿的次數(shù)，轉(zhuǎn)到lru來看就是鏈表中有空節(jié)點的次數(shù)。下面來走一下整個流程（左為head右為tail）：
2 ?????????? // 第一次缺頁
2 -> 3 ?? // 第二次缺頁
3 -> 2 ?? // 第三次缺頁
3 -> 2 -> 1
2 -> 1 ??// 第四次缺頁
2 -> 1 -> 5
1 -> 5 -> 2
5 -> 2 ??// 第五次缺頁
5 -> 2 -> 4
2 -> 4 -> 5
4 -> 5 ??// 第六次缺頁
4 -> 5 -> 3
5 -> 3 ?? // 第七次缺頁
5 -> 3 -> 2
3 -> 2 -> 5
3 -> 5 -> 2
所以總共有著7次缺頁，上面的這個流程也是算法的具體執(zhí)行流程，可以看出的是當有新的節(jié)點進入時，首先會檢測內(nèi)存是否已滿，如果滿了的話，就先將頭給移除，再在尾部添加上這個新節(jié)點；假若該節(jié)點在鏈表中存在，那么直接將這個節(jié)點拿到頭部。下面來看下Vue對這個算法的實現(xiàn)：
vue中的lru源碼時src/cache.js，先來看看其構造函數(shù)：
// limit是最大容量
function Cache (limit) {
this.size = 0;
this.limit = limit;
this.head = this.tail = undefined;
this._keymap = Object.create(null);
}
尤大利用集合_keymap來存儲已有的節(jié)點，在判斷是否存在時，直接讀取屬性就行，不用在遍歷一遍鏈表，這樣降低了在查找過程中的時間復雜度。head代表著頭節(jié)點，tail代表著尾節(jié)點，鏈表中的節(jié)點是這樣的：
node {
value: 鍵值,
key: 鍵名,
older: 指向前一個節(jié)點，head的older指向undefined,
newer: 指向下一個節(jié)點，tail的newer指向undefined
}
來看get方法：
Cache.prototype.get = function (key, returnEntry) {
var entry = this._keymap[key];
// 本身沒有,則不用調(diào)度,直接將新的節(jié)點插入到尾部即可
if (entry === undefined) return;
// 訪問的就是尾部節(jié)點,則不需要調(diào)度
if (entry === this.tail) {
return returnEntry ? entry : entry.value;
}
// 訪問的不是尾部節(jié)點,需要將被訪問節(jié)點拿到頭部
if (entry.newer) {
if (entry === this.head) {
this.head = entry.newer;
}
entry.newer.older = entry.older;
}
if (entry.older) {
entry.older.newer = entry.newer;
}
entry.newer = undefined;
entry.older = this.tail;
if (this.tail) {
this.tail.newer = entry;
}
this.tail = entry;
return returnEntry ? entry : entry.value;
};
get是為了得到鏈表中是否含有這個節(jié)點，假如有這個節(jié)點，那么還要對這個節(jié)點進行調(diào)度，也就是將節(jié)點拿到尾部。
// 將鏈表的頭給去除
Cache.prototype.shift = function () {
var entry = this.head;
if (entry) {
this.head = this.head.newer;
this.head.older = undefined;
entry.newer = entry.older = undefined;
this._keymap[entry.key] = undefined;
this.size--;
}
return entry;
};
p.put = function (key, value) {
var removed;
var entry = this.get(key, true);
// 插入的情況,插入到尾部
if (!entry) {
// 如果集合已經(jīng)滿了,移除一個,并將其return
if (this.size === this.limit) {
removed = this.shift();
}
entry = {
key: key
};
this._keymap[key] = entry;
if (this.tail) {
this.tail.newer = entry;
entry.older = this.tail;
} else { // 鏈表中插入第一個節(jié)點時，頭節(jié)點就是尾幾點
this.head = entry;
}
this.tail = entry; // 節(jié)點會添加或者拿到尾部
this.size++;
}
// 更新節(jié)點的value，假若本身鏈表中有，get方法中已經(jīng)調(diào)度好，只要更新值就好
entry.value = value;
return removed;
};
至此，vue的cache代碼已經(jīng)全部解析完，其具體的作用由于源碼剛剛開始讀嗎，目前還不清楚，不過應該在解析指令等方面有著重大的作用。
最后希望大家關注下算法演示
文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/87931.html
摘要：雙向鏈表用于管理緩存數(shù)據(jù)結點的順序，新增數(shù)據(jù)和緩存命中最近被訪問的數(shù)據(jù)被放置在結點，尾部的結點根據(jù)內(nèi)存大小進行淘汰。 了解 LRU 之前，我們應該了解一下緩存，大家都知道計算機具有緩存內(nèi)存，可以臨時存儲最常用的數(shù)據(jù)，當緩存數(shù)據(jù)超過一定大小時，系統(tǒng)會進行回收，以便釋放出空間來緩存新的數(shù)據(jù)，但從系統(tǒng)中檢索數(shù)據(jù)的成本...
摘要：中采用算法來實現(xiàn)緩存的高效管理。通過這兩個屬性，將緩存中的變量連接起來。以上圖舉例緩存這個對象中保存了三個變量。如果緩存數(shù)組為空，則返回將為傳入?yún)?shù)的緩存對象標識為最常使用的，即，并調(diào)整雙向鏈表，返回改變后的。 vue.js入坑也有了小半年的時間了，圈子里一直流傳著其源碼優(yōu)雅、簡潔的傳說。最近的一次技術分享會，同事分享vue.js源碼的緩存部分，鄙人將其整理出來，與大家一起學習 一、從...
摘要：如果處理不得當，就會造成緩存污染問題。解決緩存污染的算法算法，英文名，字面意思就是最不經(jīng)常使用的淘汰掉算法，是通過數(shù)據(jù)被訪問的頻率來判斷一個數(shù)據(jù)的熱點情況。分析降低了緩存污染帶來的問題，命中率比要高。 微信公眾號：IT一刻鐘大型現(xiàn)實非嚴肅主義現(xiàn)場一刻鐘與你分享優(yōu)質(zhì)技術架構與見聞，做一個有劇情的程序員關注可第一時間了解更多精彩內(nèi)容，定期有福利相送喲。 showImg(https://s...
摘要：但是內(nèi)存空間畢竟有限，隨著我們存儲數(shù)據(jù)的不斷增長，要緩存的數(shù)據(jù)量越來越大，當超過了我們的內(nèi)存大小時，該怎么辦呢解決方法有兩種增加物理內(nèi)存搭建集群和緩存數(shù)據(jù)的淘汰機制。增加物理內(nèi)存簡單粗暴，價格十分昂貴，內(nèi)存的價格大約是萬元左右。redis 使用的時內(nèi)存空間來存儲數(shù)據(jù)的，避免業(yè)務應用從后端數(shù)據(jù)庫中讀取數(shù)據(jù)，可以提升應用的響應速度。但是內(nèi)存空間畢竟有限，隨著我們存儲數(shù)據(jù)的不斷增長，要緩存的數(shù)據(jù)量...
閱讀 5170·2021-07-25 21:37
閱讀 728·2019-08-30 15:53
閱讀 3406·2019-08-29 18:47
閱讀 740·2019-08-29 15:39
閱讀 2193·2019-08-29 13:12
閱讀 1863·2019-08-29 12:43
閱讀 3048·2019-08-26 11:52
閱讀 1956·2019-08-26 10:15
