Beispiel für die Implementierung eines Caching-Algorithmus durch JS

In diesem Artikel werden hauptsächlich Beispiele für die JS-Implementierung von Caching-Algorithmen (FIFO/LRU) vorgestellt. Jetzt teile ich ihn mit Ihnen und gebe ihn als Referenz.

FIFO

Der einfachste Caching-Algorithmus legt die Cache-Obergrenze fest. Wenn die Cache-Obergrenze erreicht ist, wird sie gemäß dem First-In-First-Prinzip gelöscht -out-Strategie, und fügen Sie dann ein neues k-v ein.

verwendet ein Objekt als Cache, um festzustellen, ob die Obergrenze erreicht wurde. Wenn die Obergrenze erreicht ist, wird der erste Elementschlüssel verwendet Array und löschen Sie den Schlüsselwert im Objekt entsprechend.

/**
 * 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 Implementierung des Codes auf die Reihenfolge, die ich in den Kommentaren 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 habe das Obige für Sie zusammengestellt und hoffe, dass es Ihnen in Zukunft hilfreich sein wird.

Verwandte Artikel:

Schnelle Beherrschung von Reverse Ajax in 30 Minuten

Ajax implementiert eine intelligente Eingabeaufforderungssuchfunktion

Öffnen Sie eine neue Fensteradresse, nachdem die Ajax-Anfrage erfolgreich war

Das obige ist der detaillierte Inhalt vonBeispiel für die Implementierung eines Caching-Algorithmus durch JS. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!