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