FIFO/LRU はキャッシュ アルゴリズムを実装します

FIFO

最も単純なキャッシュアルゴリズムで、キャッシュの上限を設定します。キャッシュの上限に達すると、先入れ先出し戦略に従って削除され、新しい k-v が追加されます。

は、 オブジェクト をキャッシュとして使用し、レコードがオブジェクトに追加される順序と一致する 配列 を使用して、上限に達したかどうかを判断します。上限に達した場合は、最初の要素キーを取得します。配列内で を削除し、それに応じてオブジェクト内の オブジェクトを削除します。

/**
 * 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 (最も最近使用されていない、最も最近使用されていない) アルゴリズム。このアルゴリズムの観点は、最近アクセスされたデータは将来アクセスされる可能性が高いため、キャッシュがいっぱいになると、最も関心のないデータが最初に削除されるということです。

アルゴリズム実装アイデア: 二重リンクリストのデータ構造に基づいて、それがいっぱいではない場合、新しい 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

具体的な考え方は、取得したいノードがヘッド ノードではない場合 (つまり、すでに最も最近使用されたノードであり、ノードの位置を移動する必要がない場合)、最初に次の操作を実行する必要があるということです。リンク解除操作をスムーズに行い、ポインタ間の関係を処理して取り出します。リンクされたリストに挿入するには、前のノードに移動する必要があります。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

vue-router でクエリパラメータを動的に渡す手順は何ですか?

以上がFIFO/LRU はキャッシュ アルゴリズムを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。