Exemple d'algorithme de mise en cache JS implémentant

Cet article présente principalement des exemples d'implémentation JS d'algorithmes de mise en cache (FIFO/LRU). Maintenant, je le partage avec vous et le donne comme référence.

FIFO

L'algorithme de mise en cache le plus simple, définit la limite supérieure du cache Lorsque la limite supérieure du cache est atteinte, elle sera éliminée selon le premier entré, premier. -out stratégie, puis ajouté Entrez le nouveau k-v.

utilise un objet comme cache. Un tableau correspond à l'ordre dans lequel les enregistrements sont ajoutés à l'objet pour déterminer si la limite supérieure a été atteinte, prenez la première clé d'élément dans le. tableau et supprimez la valeur clé dans l’objet en conséquence.

/**
 * 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

Algorithme LRU (Le moins récemment utilisé, le moins récemment utilisé). Le point de vue de cet algorithme est que les données consultées récemment ont une plus grande probabilité d'être consultées dans le futur. Lorsque le cache est plein, les données les moins intéressées seront éliminées en premier.

Idée d'implémentation de l'algorithme : basé sur la structure de données d'une liste chaînée double, lorsqu'elle n'est pas pleine, le nouveau k-v est placé en tête de la liste chaînée, et le k-v est déplacé à chaque fois que le k-v est dans le cache est obtenu Lorsque le cache est plein, ceux qui se trouvent à la fin seront éliminés en premier.

Les caractéristiques d'une liste doublement chaînée sont des pointeurs de tête et de queue. Chaque nœud a des pointeurs prev (prédécesseur) et next (successeur) pointant respectivement vers ses nœuds précédent et suivant.

Point clé : faites attention au problème d'ordre lors du processus d'insertion de la liste chaînée en double. Le pointeur doit d'abord être traité tout en gardant la liste chaînée continue, et enfin le pointeur d'origine pointe vers l'élément nouvellement inséré. Dans l'implémentation du code Veuillez faire attention à l'ordre que j'ai expliqué dans les commentaires !

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

L'idée spécifique est que si le nœud que vous souhaitez obtenir n'est pas le nœud principal (c'est-à-dire qu'il est déjà le nœud le plus récemment utilisé et qu'il n'est pas nécessaire de déplacer la position du nœud) , vous devez d'abord effectuer une opération de rupture de lien en douceur et gérer le pointeur pointant vers la relation, retirer le nœud qui doit être déplacé vers l'avant et effectuer l'opération d'insertion dans la liste chaînée.

Ce qui précède est ce que j'ai compilé pour vous. J'espère que cela vous sera utile à l'avenir.

Articles connexes :

Maîtrisez rapidement l'Ajax inversé en 30 minutes

Ajax implémente la fonction de recherche d'invite intelligente

Ouvrez une nouvelle adresse de fenêtre une fois la requête Ajax réussie

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!