FIFO/LRU implementiert den Caching-Algorithmus

FIFO

Der einfachste Caching-Algorithmus legt die Cache-Obergrenze fest. Wenn die Cache-Obergrenze erreicht ist, wird sie gemäß der First-In-First-Out-Strategie eliminiert , und dann werden neue k-v hinzugefügt.

verwendet ein -Objekt als Cache und ein -Array , um die Reihenfolge anzupassen, in der Datensätze zum Objekt hinzugefügt werden, um zu bestimmen, ob die Obergrenze erreicht ist Wenn die Obergrenze erreicht ist, wird das erste Element im Array verwendet, das dem Löschen des Schlüsselwerts im -Objekt entspricht.

/**
 * 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-Algorithmus (Am wenigsten kürzlich verwendet, am wenigsten kürzlich verwendet). Der Standpunkt dieses Algorithmus besteht darin, dass die Wahrscheinlichkeit eines Zugriffs auf die Daten, auf die kürzlich zugegriffen wurde, größer ist. Wenn der Cache voll ist, werden die am wenigsten interessierten Daten zuerst gelöscht.

Idee zur Algorithmusimplementierung: Basierend auf der Datenstruktur einer doppelt verknüpften Liste wird das neue k-v an den Kopf der verknüpften Liste gesetzt, wenn es nicht voll ist, und das k-v wird jedes Mal verschoben, wenn das k-v eingeht Der Cache wird abgerufen. Wenn der Cache voll ist, werden diejenigen am Ende zuerst gelöscht.

Das Merkmal einer doppelt verknüpften Liste ist, dass sie Kopf- und Endzeiger hat. Jeder Knoten hat einen vorherigen (Vorläufer) und einen nächsten (Nachfolger) Zeiger, die auf seinen vorherigen bzw. nächsten Knoten zeigen.

Wichtiger Punkt: Achten Sie beim Einfügevorgang der doppelt verknüpften Liste auf die Reihenfolge. Der Zeiger muss zuerst verarbeitet werden, während die verknüpfte Liste kontinuierlich bleibt, und schließlich zeigt der ursprüngliche Zeiger auf das neu eingefügte Element. Bitte achten Sie bei der Umsetzung des Codes auf die Reihenfolge, die ich in den

Anmerkungen erklärt habe!

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

Die konkrete Idee besteht darin, dass Sie, wenn der Knoten, den Sie erhalten möchten, nicht der Hauptknoten ist (d. h. es ist bereits der zuletzt verwendete Knoten und es nicht erforderlich ist, die Knotenposition zu verschieben). Sie müssen zuerst einen reibungslosen Link-Unterbrechungsvorgang durchführen und den Zeiger verarbeiten, auf den die Beziehung zeigt, den Knoten herausnehmen, der nach vorne verschoben werden muss, und den Einfügevorgang in die verknüpfte Liste ausführen.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Was sind die Schritte zur dynamischen Übergabe von Abfrageparametern im Vue-Router?

Die lokale Entwicklung Umgebung kann nicht verwendet werden. Wie man mit dem IP-Zugriff umgeht

Das obige ist der detaillierte Inhalt vonFIFO/LRU implementiert den Caching-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!