成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Vue的緩存算法—LRU算法

elina / 3659人閱讀

摘要：最近在看的源碼，不得不說的是，的源碼十分優(yōu)雅簡(jiǎn)潔，下面就來分享下的緩存利用的算法算法。關(guān)于算法的具體流程，可以來看下這個(gè)，這個(gè)可視化過程，模擬了算法進(jìn)行調(diào)度的過程。

最近在看Vue的源碼，不得不說的是，Vue的源碼十分優(yōu)雅簡(jiǎn)潔，下面就來分享下Vue的緩存利用的算法LRU算法。

LRU算法

LRU是Least recently used的簡(jiǎn)寫，主要原理是根據(jù)歷史訪問記錄來淘汰數(shù)據(jù)，說白了就是這個(gè)算法認(rèn)為如果數(shù)據(jù)被訪問過，那么將來被訪問的幾率也高。其存儲(chǔ)結(jié)構(gòu)是一個(gè)雙鏈表，最近被訪問到的放在雙鏈表的尾部，頭部放的就是最早被訪問到數(shù)據(jù)。關(guān)于算法的具體流程，可以來看下這個(gè)，這個(gè)可視化過程，模擬了lru算法進(jìn)行調(diào)度的過程。

缺頁(yè)數(shù)

lru在筆試題中也會(huì)經(jīng)常出現(xiàn)，經(jīng)常會(huì)考到的那就是缺頁(yè)數(shù)，例如頁(yè)面訪問序列為：2,3,2,1,5,2,4,5,3,2,5,2， 分配給某個(gè)進(jìn)程3頁(yè)內(nèi)存，求其缺頁(yè)次數(shù)。
缺頁(yè)數(shù)可以理解為，內(nèi)存不滿的次數(shù)，轉(zhuǎn)到lru來看就是鏈表中有空節(jié)點(diǎn)的次數(shù)。下面來走一下整個(gè)流程（左為head右為tail）：

2 ?????????? // 第一次缺頁(yè)

2 -> 3 ?? // 第二次缺頁(yè)

3 -> 2 ?? // 第三次缺頁(yè)

3 -> 2 -> 1

2 -> 1 ??// 第四次缺頁(yè)

2 -> 1 -> 5

1 -> 5 -> 2

5 -> 2 ??// 第五次缺頁(yè)

5 -> 2 -> 4

2 -> 4 -> 5

4 -> 5 ??// 第六次缺頁(yè)

4 -> 5 -> 3

5 -> 3 ?? // 第七次缺頁(yè)

5 -> 3 -> 2

3 -> 2 -> 5

3 -> 5 -> 2

所以總共有著7次缺頁(yè)，上面的這個(gè)流程也是算法的具體執(zhí)行流程，可以看出的是當(dāng)有新的節(jié)點(diǎn)進(jìn)入時(shí)，首先會(huì)檢測(cè)內(nèi)存是否已滿，如果滿了的話，就先將頭給移除，再在尾部添加上這個(gè)新節(jié)點(diǎn)；假若該節(jié)點(diǎn)在鏈表中存在，那么直接將這個(gè)節(jié)點(diǎn)拿到頭部。下面來看下Vue對(duì)這個(gè)算法的實(shí)現(xiàn)：

vue中的lru

源碼時(shí)src/cache.js，先來看看其構(gòu)造函數(shù)：

// limit是最大容量
function Cache (limit) {
    this.size = 0;
    this.limit = limit;
    this.head = this.tail = undefined;
    this._keymap = Object.create(null);
}

尤大利用集合_keymap來存儲(chǔ)已有的節(jié)點(diǎn)，在判斷是否存在時(shí)，直接讀取屬性就行，不用在遍歷一遍鏈表，這樣降低了在查找過程中的時(shí)間復(fù)雜度。head代表著頭節(jié)點(diǎn)，tail代表著尾節(jié)點(diǎn)，鏈表中的節(jié)點(diǎn)是這樣的：

node {
    value: 鍵值,
    key: 鍵名,
    older: 指向前一個(gè)節(jié)點(diǎn)，head的older指向undefined,
    newer: 指向下一個(gè)節(jié)點(diǎn)，tail的newer指向undefined
}

來看get方法：

Cache.prototype.get = function (key, returnEntry) {
     var entry = this._keymap[key];
     // 本身沒有,則不用調(diào)度,直接將新的節(jié)點(diǎn)插入到尾部即可
    if (entry === undefined) return;
    // 訪問的就是尾部節(jié)點(diǎn),則不需要調(diào)度    
    if (entry === this.tail) {
        return returnEntry ? entry : entry.value;
    }
    // 訪問的不是尾部節(jié)點(diǎn),需要將被訪問節(jié)點(diǎn)拿到頭部
    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是為了得到鏈表中是否含有這個(gè)節(jié)點(diǎn)，假如有這個(gè)節(jié)點(diǎn)，那么還要對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行調(diào)度，也就是將節(jié)點(diǎn)拿到尾部。

// 將鏈表的頭給去除
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)滿了,移除一個(gè),并將其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 {  // 鏈表中插入第一個(gè)節(jié)點(diǎn)時(shí)，頭節(jié)點(diǎn)就是尾幾點(diǎn)
            this.head = entry;
        }
        this.tail = entry;   // 節(jié)點(diǎn)會(huì)添加或者拿到尾部
        this.size++;
    }
    // 更新節(jié)點(diǎn)的value，假若本身鏈表中有，get方法中已經(jīng)調(diào)度好，只要更新值就好
    entry.value = value;
    return removed;
};

至此，vue的cache代碼已經(jīng)全部解析完，其具體的作用由于源碼剛剛開始讀嗎，目前還不清楚，不過應(yīng)該在解析指令等方面有著重大的作用。

最后希望大家關(guān)注下算法演示

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/87931.html

相關(guān)文章

  • web技術(shù)分享| LRU 緩存淘汰算法

    摘要：雙向鏈表用于管理緩存數(shù)據(jù)結(jié)點(diǎn)的順序，新增數(shù)據(jù)和緩存命中最近被訪問的數(shù)據(jù)被放置在結(jié)點(diǎn)，尾部的結(jié)點(diǎn)根據(jù)內(nèi)存大小進(jìn)行淘汰。 了解 LRU 之前，我們應(yīng)該了解一下緩存，大家都知道計(jì)算機(jī)具有緩存內(nèi)存，可以臨時(shí)存儲(chǔ)最常用的數(shù)據(jù)，當(dāng)緩存數(shù)據(jù)超過一定大小時(shí)，系統(tǒng)會(huì)進(jìn)行回收，以便釋放出空間來緩存新的數(shù)據(jù)，但從系統(tǒng)中檢索數(shù)據(jù)的成本...

    graf 評(píng)論0 收藏0

  • 探索vue源碼之緩存篇

    摘要：中采用算法來實(shí)現(xiàn)緩存的高效管理。通過這兩個(gè)屬性，將緩存中的變量連接起來。以上圖舉例緩存這個(gè)對(duì)象中保存了三個(gè)變量。如果緩存數(shù)組為空，則返回將為傳入?yún)?shù)的緩存對(duì)象標(biāo)識(shí)為最常使用的，即，并調(diào)整雙向鏈表，返回改變后的。 vue.js入坑也有了小半年的時(shí)間了，圈子里一直流傳著其源碼優(yōu)雅、簡(jiǎn)潔的傳說。最近的一次技術(shù)分享會(huì)，同事分享vue.js源碼的緩存部分，鄙人將其整理出來，與大家一起學(xué)習(xí) 一、從...

    Forest10 評(píng)論0 收藏0

  • 你與解決“緩存污染”只差這篇文章的距離

    摘要：如果處理不得當(dāng)，就會(huì)造成緩存污染問題。解決緩存污染的算法算法，英文名，字面意思就是最不經(jīng)常使用的淘汰掉算法，是通過數(shù)據(jù)被訪問的頻率來判斷一個(gè)數(shù)據(jù)的熱點(diǎn)情況。分析降低了緩存污染帶來的問題，命中率比要高。 微信公眾號(hào)：IT一刻鐘大型現(xiàn)實(shí)非嚴(yán)肅主義現(xiàn)場(chǎng)一刻鐘與你分享優(yōu)質(zhì)技術(shù)架構(gòu)與見聞，做一個(gè)有劇情的程序員關(guān)注可第一時(shí)間了解更多精彩內(nèi)容，定期有福利相送喲。 showImg(https://s...

    shadowbook 評(píng)論0 收藏0

  • Redis 緩存淘汰策略

    摘要：但是內(nèi)存空間畢竟有限，隨著我們存儲(chǔ)數(shù)據(jù)的不斷增長(zhǎng)，要緩存的數(shù)據(jù)量越來越大，當(dāng)超過了我們的內(nèi)存大小時(shí)，該怎么辦呢解決方法有兩種增加物理內(nèi)存搭建集群和緩存數(shù)據(jù)的淘汰機(jī)制。增加物理內(nèi)存簡(jiǎn)單粗暴，價(jià)格十分昂貴，內(nèi)存的價(jià)格大約是萬元左右。redis 使用的時(shí)內(nèi)存空間來存儲(chǔ)數(shù)據(jù)的，避免業(yè)務(wù)應(yīng)用從后端數(shù)據(jù)庫(kù)中讀取數(shù)據(jù)，可以提升應(yīng)用的響應(yīng)速度。但是內(nèi)存空間畢竟有限，隨著我們存儲(chǔ)數(shù)據(jù)的不斷增長(zhǎng)，要緩存的數(shù)據(jù)量...

    Tecode 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<