Explication détaillée de la méthode d'opération de traitement du cache implémentée par Nodejs basée sur l'algorithme LRU

Cet article présente principalement le fonctionnement du traitement du cache de Nodejs basé sur l'algorithme LRU. Il analyse les principes et les fonctions de l'algorithme LRU et la mise en œuvre de l'algorithme LRU dans. nodejs basé sur des exemples spécifiques. Pour les compétences d'implémentation liées aux opérations de traitement du cache, les amis dans le besoin peuvent se référer à

Cet article décrit les opérations de traitement du cache implémentées par Nodejs sur la base de l'algorithme LRU. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

LRU est l'abréviation de Least Récemment utilisé, c'est-à-dire l'algorithme de remplacement de page le moins récemment utilisé, qui sert à la gestion du stockage de pages virtuelles et est chargé dans la mémoire en fonction de la page. Les décisions d'utilisation sont prises. Puisqu'il est impossible de prédire l'utilisation future de chaque page, nous ne pouvons utiliser que le « passé récent » comme approximation du « futur proche ». Par conséquent, l'algorithme LRU élimine les pages qui n'ont pas été utilisées depuis le plus longtemps.

Une pile spéciale peut être utilisée pour enregistrer le numéro de page de chaque page actuellement utilisée. Lorsqu'un nouveau processus accède à une page, le numéro de page est poussé vers le haut de la pile et les autres numéros de page sont déplacés vers le bas de la pile. S'il n'y a pas assez de mémoire, le numéro de page en bas de la pile est déplacé. supprimé. De cette façon, le haut de la pile est toujours le numéro de la page la plus récemment consultée, et le bas de la pile est le numéro de la page la plus récemment visitée.

Par exemple, en saisissant la séquence suivante : 4,7,0,7,1,0,1,2,1,2,6

Le résultat est :

4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 7 1 2
4 7 1 🎜>Un cache LRU de Node.js
, la capacité est la capacité du cache, construite lorsqu'elle est à 0 Mise en cache générale.

L'algorithme LRU peut également être utilisé dans certaines applications pratiques, comme si vous souhaitez créer un navigateur, ou quelque chose de similaire aux applications client Taobao utilisera ce principe. Tout le monde sait que lors de la navigation sur le Web, le navigateur enregistrera temporairement les images téléchargées dans un dossier sur la machine locale. La prochaine fois que vous le visiterez, elles seront lues directement à partir du dossier temporaire sur la machine locale. Cependant, le dossier temporaire qui enregistre les images a une certaine limite de capacité. Si vous parcourez trop de pages Web, certaines des images que vous utilisez le moins fréquemment seront supprimées et seules les images les plus récemment utilisées seront conservées. À ce stade, l'algorithme LRU peut être utilisé. À ce stade, la pile spéciale dans l'algorithme ci-dessus n'enregistre pas le numéro de série de la page, mais le numéro de série ou la taille de chaque image, donc les éléments de la pile ci-dessus sont utilisés ; La

function CacheLRU(capacity) {
/* 利用Buffer写的一个LRU缓存，capacity为缓存容量，为0时不限容量。
myCache = new CacheLRU(capacity); //构造缓存
myCache.get(key); //读取名为key的缓存值
myCache.put(key, value); //写入名为key的缓存值
myCache.remove(key); //删除名为key的缓存值
myCache.removeAll(); //清空缓存
myCache.info(); //返回myCache缓存信息
LRU原理：对所有缓存数据的key构建hash链表，当对某一数据进行get或put操作时，将其key提到链表前端（最新）。当进行put数据超出容量时，删除链表尾端（最旧）的缓存数据。
hash链表操作可直接定位key，无需历遍整个hash对象，故读写极快。缓存容量不再影响读写速度。
*/
  this.capacity = capacity || Number.MAX_VALUE;
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  if (capacity <= 0) this.capacity = Number.MAX_VALUE;
};
CacheLRU.prototype.get = function(key) {
  key = &#39;_&#39; + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return;
  refresh(this.linkedList, lruEntry);
  return JSON.parse(this.data[key].toString());
};
CacheLRU.prototype.put = function(key, value) {
  key = &#39;_&#39; + key;
  var lruEntry = this.hash[key];
  if (value === undefined) return this;
  if (!lruEntry) {
    this.hash[key] = {key: key};
    this.linkedList.length += 1;
    lruEntry = this.hash[key];
  }
  refresh(this.linkedList, lruEntry);
  this.data[key] = new Buffer(JSON.stringify(value));
  if (this.linkedList.length > this.capacity) this.remove(this.linkedList.end.key.slice(1));
  return this;
};
CacheLRU.prototype.remove = function(key) {
  key = &#39;_&#39; + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return this;
  if (lruEntry === this.linkedList.head) this.linkedList.head = lruEntry.p;
  if (lruEntry === this.linkedList.end) this.linkedList.end = lruEntry.n;
  link(lruEntry.n, lruEntry.p);
  delete this.hash[key];
  delete this.data[key];
  this.linkedList.length -= 1;
  return this;
};
CacheLRU.prototype.removeAll = function() {
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  return this;
};
CacheLRU.prototype.info = function() {
  var size = 0,
    data = this.linkedList.head;
  while (data){
    size += this.data[data.key].length;
    data = data.p;
  }
  return {
    capacity: this.capacity,
    length: this.linkedList.length,
    size: size
  };
};
// 更新链表，把get或put方法操作的key提到链表head，即表示最新
function refresh(linkedList, entry) {
  if (entry != linkedList.head) {
    if (!linkedList.end) {
      linkedList.end = entry;
    } else if (linkedList.end == entry) {
      linkedList.end = entry.n;
    }
    link(entry.n, entry.p);
    link(entry, linkedList.head);
    linkedList.head = entry;
    linkedList.head.n = null;
  }
}
// 对两个链表对象建立链接，形成一条链
function link(nextEntry, prevEntry) {
  if (nextEntry != prevEntry) {
    if (nextEntry) nextEntry.p = prevEntry;
    if (prevEntry) prevEntry.n = nextEntry;
  }
}
module.exports = CacheLRU;
// test:
/*var user = new CacheLRU(5);
user.put(&#39;user1&#39;, {name:&#39;admin&#39;, age: 30});
user.put(&#39;user2&#39;, {name:&#39;user&#39;, age: 31});
user.put(&#39;user3&#39;, {name:&#39;guest&#39;, age: 32});
user.put(&#39;user4&#39;, {name:&#39;guest&#39;, age: 34});
user.put(&#39;user5&#39;, {name:&#39;guest&#39;, age: 35});
console.log(user.get(&#39;user1&#39;));
console.log(user.get(&#39;user2&#39;));
console.log(user.get(&#39;user3&#39;));
user.put(&#39;user6&#39;, {name:&#39;guest&#39;, age: 36});
console.log(user.info());*/

Classe d'objet

est représentée, afin que la pile puisse enregistrer des objets.

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!