国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JS 實現(xiàn)緩存算法(FIFO/LRU)

awokezhou / 2607人閱讀

摘要:最簡單的一種緩存算法,設置緩存上限,當達到了緩存上限的時候,按照先進先出的策略進行淘汰,再增加進新的。隊列算法實現(xiàn)緩存需要一個對象和一個數(shù)組作為輔助數(shù)組記錄進入順序先進先出,刪除隊列第一個元素無論存在與否都對中的賦值,最近最少使用算法。

FIFO

最簡單的一種緩存算法,設置緩存上限,當達到了緩存上限的時候,按照先進先出的策略進行淘汰,再增加進新的 k-v 。

使用了一個對象作為緩存,一個數(shù)組配合著記錄添加進對象時的順序,判斷是否到達上限,若到達上限取數(shù)組中的第一個元素key,對應刪除對象中的鍵值。

/**
 * FIFO隊列算法實現(xiàn)緩存
 * 需要一個對象和一個數(shù)組作為輔助
 * 數(shù)組記錄進入順序
 */
class FifoCache{
    constructor(limit){
        this.limit = limit || 10
        this.map = {}
        this.keys = []
    }
    set(key,value){
        let map = this.map
        let keys = this.keys
        if (!Object.prototype.hasOwnProperty.call(map,key)) {
            if (keys.length === this.limit) {
                delete map[keys.shift()]//先進先出,刪除隊列第一個元素
            }
            keys.push(key)
        }
        map[key] = value//無論存在與否都對map中的key賦值
    }
    get(key){
        return this.map[key]
    }
}

module.exports = FifoCache
LRU

LRU(Least recently used,最近最少使用)算法。該算法的觀點是,最近被訪問的數(shù)據那么它將來訪問的概率就大,緩存滿的時候,優(yōu)先淘汰最無人問津者

算法實現(xiàn)思路:基于一個雙鏈表的數(shù)據結構,在沒有滿員的情況下,新來的 k-v 放在鏈表的頭部,以后每次獲取緩存中的 k-v 時就將該k-v移到最前面,緩存滿的時候優(yōu)先淘汰末尾的。

雙向鏈表的特點,具有頭尾指針,每個節(jié)點都有 prev(前驅) 和 next(后繼) 指針分別指向他的前一個和后一個節(jié)點。

關鍵點:在雙鏈表的插入過程中要注意順序問題,一定是在保持鏈表不斷的情況下先處理指針,最后才將原頭指針指向新插入的元素,在代碼的實現(xiàn)中請注意看我在注釋中說明的順序注意點!

class LruCache {
    constructor(limit) {
        this.limit = limit || 10
        //head 指針指向表頭元素,即為最常用的元素
        this.head = this.tail = undefined
        this.map = {}
        this.size = 0
    }
    get(key, IfreturnNode) {
        let node = this.map[key]
        // 如果查找不到含有`key`這個屬性的緩存對象
        if (node === undefined) return
        // 如果查找到的緩存對象已經是 tail (最近使用過的)
        if (node === this.head) { //判斷該節(jié)點是不是是第一個節(jié)點
            // 是的話,皆大歡喜,不用移動元素,直接返回
            return returnnode ?
                node :
                node.value
        }
        // 不是頭結點,鐵定要移動元素了
        if (node.prev) { //首先要判斷該節(jié)點是不是有前驅
            if (node === this.tail) { //有前驅,若是尾節(jié)點的話多一步,讓尾指針指向當前節(jié)點的前驅
                this.tail = node.prev
            }
            //把當前節(jié)點的后繼交接給當前節(jié)點的前驅去指向。
            node.prev.next = node.next
        }
        if (node.next) { //判斷該節(jié)點是不是有后繼
            //有后繼的話直接讓后繼的前驅指向當前節(jié)點的前驅
            node.next.prev = node.prev
            //整個一個過程就是把當前節(jié)點拿出來,并且保證鏈表不斷,下面開始移動當前節(jié)點了
        }
        node.prev = undefined //移動到最前面,所以沒了前驅
        node.next = this.head //注意!!! 這里要先把之前的排頭給接到手!!!!讓當前節(jié)點的后繼指向原排頭
        if (this.head) {
            this.head.prev = node //讓之前的排頭的前驅指向現(xiàn)在的節(jié)點
        }
        this.head = node //完成了交接,才能執(zhí)行此步!不然就找不到之前的排頭啦!
        return IfreturnNode ?
            node :
            node.value
    }
    set(key, value) {
        // 之前的算法可以直接存k-v但是現(xiàn)在要把簡單的 k-v 封裝成一個滿足雙鏈表的節(jié)點
        //1.查看是否已經有了該節(jié)點
        let node = this.get(key, true)
        if (!node) {
            if (this.size === this.limit) { //判斷緩存是否達到上限
                //達到了,要刪最后一個節(jié)點了。
                if (this.tail) {
                    this.tail = this.tail.prev
                    this.tail.prev.next = undefined
                    //平滑斷鏈之后,銷毀當前節(jié)點
                    this.tail.prev = this.tail.next = undefined
                    this.map[this.tail.key] = undefined
                    //當前緩存內存釋放一個槽位
                    this.size--
                }
                node = {
                    key: key
                }
                this.map[key] = node
                if(this.head){//判斷緩存里面是不是有節(jié)點
                    this.head.prev = node
                    node.next = this.head
                }else{
                    //緩存里沒有值,皆大歡喜,直接讓head指向新節(jié)點就行了
                    this.head = node
                    this.tail = node
                }
                this.size++//減少一個緩存槽位
            }
        }
        //節(jié)點存不存在都要給他重新賦值啊
        node.value = value
    }
}

module.exports = LruCache

具體的思路就是如果所要get的節(jié)點不是頭結點(即已經是最近使用的節(jié)點了,不需要移動節(jié)點位置)要先進行平滑的斷鏈操作,處理好指針指向的關系,拿出需要移動到最前面的節(jié)點,進行鏈表的插入操作。

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

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/93506.html

相關文章

  • 《CDN 之我見》系列二:原理篇(緩存、安全)

    摘要:真正要做高性能的系統(tǒng),不僅需要在數(shù)據結構與算法層面深入,更要從硬件操作系統(tǒng)文件系統(tǒng)底層原理等多個領域做更多的研究例如阿里云自研的系統(tǒng)使用了裸盤技術。 《CDN之我見》共由三個篇章組成,分為原理篇、詳解篇和隕坑篇。本篇章適合那些從未接觸過、或僅了解一些 CDN 專業(yè)術語,想深入了解和感受 CDN 究竟是什么的同學。本次由白金老師繼續(xù)為大家分享《CDN之我見》系列二,主要講解緩存是什么、工...

    maxmin 評論0 收藏0
  • 《CDN 之我見》系列二:原理篇(緩存、安全)

    摘要:真正要做高性能的系統(tǒng),不僅需要在數(shù)據結構與算法層面深入,更要從硬件操作系統(tǒng)文件系統(tǒng)底層原理等多個領域做更多的研究例如阿里云自研的系統(tǒng)使用了裸盤技術。 《CDN之我見》共由三個篇章組成,分為原理篇、詳解篇和隕坑篇。本篇章適合那些從未接觸過、或僅了解一些 CDN 專業(yè)術語,想深入了解和感受 CDN 究竟是什么的同學。本次由白金老師繼續(xù)為大家分享《CDN之我見》系列二,主要講解緩存是什么、工...

    rainyang 評論0 收藏0
  • 你應該知道的緩存進化史

    摘要:先簡單介紹一下愛奇藝的緩存道路的發(fā)展吧。可以看見圖中分為幾個階段第一階段數(shù)據同步加通過消息隊列進行數(shù)據同步至,然后應用直接去取緩存這個階段優(yōu)點是由于是使用的分布式緩存,所以數(shù)據更新快。愛奇藝的緩存的發(fā)展也是基于此之上,通過對的二次開發(fā) 1.背景 本文是上周去技術沙龍聽了一下愛奇藝的Java緩存之路有感寫出來的。先簡單介紹一下愛奇藝的java緩存道路的發(fā)展吧。 showImg(https...

    remcarpediem 評論0 收藏0
  • 你應該知道的緩存進化史

    摘要:先簡單介紹一下愛奇藝的緩存道路的發(fā)展吧。可以看見圖中分為幾個階段第一階段數(shù)據同步加通過消息隊列進行數(shù)據同步至,然后應用直接去取緩存這個階段優(yōu)點是由于是使用的分布式緩存,所以數(shù)據更新快。愛奇藝的緩存的發(fā)展也是基于此之上,通過對的二次開發(fā) 1.背景 本文是上周去技術沙龍聽了一下愛奇藝的Java緩存之路有感寫出來的。先簡單介紹一下愛奇藝的java緩存道路的發(fā)展吧。 showImg(https...

    Tangpj 評論0 收藏0
  • 【Mybatis系列】從源碼角度深度理解Mybatis的緩存特性

    摘要:一級緩存介紹及相關配置。在這個章節(jié),我們學習如何使用的一級緩存。一級緩存實驗配置完畢后,通過實驗的方式了解一級緩存的效果。源碼分析了解具體的工作流程后,我們隊查詢相關的核心類和一級緩存的源碼進行走讀。 我,后端Java工程師,現(xiàn)在美團點評工作。愛健身,愛技術,也喜歡寫點文字。個人網站: http://kailuncen.me公眾號: KailunTalk (凱倫說) 前言 本文主要涉及...

    Ku_Andrew 評論0 收藏0

發(fā)表評論

0條評論

awokezhou

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<