JS実現キャッシュアルゴリズム(FIFO/LRU)

FIFO
最も簡単なキャッシュアルゴリズムでは、キャッシュ上限を設定し、キャッシュ上限に達したら、先入先出の戦略に従って淘汰し、新たなk-vを追加します.
一つのオブジェクトをキャッシュとして使用し、一つの配列が記録に合わせてオブジェクトを追加する時の順番で、上限に到達するかどうかを判断し、上限に達したら配列の中の最初の要素keyを取り、削除対象のキー値に対応します.

/**
 * FIFO        
 *                
 *         
 */
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)アルゴリズム.このアルゴリズムの観点は、最近訪問されたデータは将来的にアクセスする確率が高く、キャッシュが満杯になると、最も無名の人を優先的に淘汰するということです.
アルゴリズムの構想を実現します.ダブルチェーンのデータ構造に基づいて、満員でない場合、新しく来たk-vはチェーンの頭に置いて、後でキャッシュのk-vを取得するたびに、そのk-vを一番前に移動します.キャッシュがいっぱいになったら、優先的に最後の方を淘汰します.
双方向リンク表の特徴は、先頭と後尾のポインタを持ち、各ノードはprev(前駆)とnext(後続)のポインタをそれぞれ彼の前のノードと後のノードに向けている.
ポイント:ダブルチェーンの挿入過程において、順序問題に注意しなければいけません.必ずチェーンを維持している状態で、先にポインタを処理して、最後に元のヘッドポインタを新たに挿入された要素に向けます.コードの実現において、注釈に説明されている順序に注意してください.

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) { //              
            //    ，    ，      ，    
            return returnnode ?
                node :
                node.value
        }
        //      ，        
        if (node.prev) { //              
            if (node === this.tail) { //   ，          ，             
                this.tail = node.prev
            }
            //                     。
            node.prev.next = node.next
        }
        if (node.next) { //           
            //                      
            node.next.prev = node.prev
            //                ，        ，           
        }
        node.prev = undefined //      ，      
        node.next = this.head //  ！！！               ！！！！             
        if (this.head) {
            this.head.prev = node //                
        }
        this.head = node //     ，      ！            ！
        return IfreturnNode ?
            node :
            node.value
    }
    set(key, value) {
        //           k-v          k-v              
        //1.           
        let node = this.get(key, true)
        if (!node) {
            if (this.size === this.limit) { //          
                //   ，         。
                if (this.tail) {
                    this.tail = this.tail.prev
                    this.tail.prev.next = undefined
                    //      ，      
                    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){//            
                    this.head.prev = node
                    node.next = this.head
                }else{
                    //      ，    ，   head        
                    this.head = node
                    this.tail = node
                }
                this.size++//        
            }
        }
        //               
        node.value = value
    }
}

module.exports = LruCache

具体的な考えは、GETするノードが、ヘッダノードではない場合(すなわち、最近使用されているノードであり、ノード位置を移動する必要はない)、先にスムーズなオフチェーン操作を行い、ポインタ指向の関係を処理し、一番前のノードに移動して、チェーンの挿入操作を行うということです.