Detaillierte Erläuterung der von Nodejs basierenden Cache-Verarbeitungsoperationsmethode basierend auf dem LRU-Algorithmus-js-Tutorial-php.cn

Detaillierte Erläuterung der von Nodejs basierenden Cache-Verarbeitungsoperationsmethode basierend auf dem LRU-Algorithmus

高洛峰

Freigeben： 2017-03-19 09:45:42

Original

1488 Leute haben es durchsucht

In diesem Artikel wird hauptsächlich die Cache-Verarbeitung-Operation von Nodejs basierend auf dem LRU-Algorithmus vorgestellt. Er analysiert die Prinzipien und Funktionen des LRU-Algorithmus und die Implementierung des LRU-Algorithmus Informationen zu entsprechenden Implementierungsfähigkeiten von Cache-Verarbeitungsvorgängen finden Sie unter

Dieser Artikel beschreibt die von Nodejs basierenden Cache-Verarbeitungsvorgänge basierend auf dem LRU-Algorithmus. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

LRU ist die Abkürzung für „Least Recent Used“, also den zuletzt verwendeten Seitenersetzungsalgorithmus, der der virtuellen Seitenspeicherverwaltung dient und in den geladen wird Es werden Nutzungsentscheidungen über den Speicher getroffen. Da es unmöglich ist, die zukünftige Nutzung jeder Seite vorherzusagen, können wir die „jüngste Vergangenheit“ nur als Annäherung an die „nahe Zukunft“ verwenden. Daher eliminiert der LRU-Algorithmus die Seiten, die am längsten nicht verwendet wurden.

Ein spezieller Stapel kann verwendet werden, um die Seitenzahl jeder aktuell verwendeten Seite zu speichern. Wenn ein neuer Prozess auf eine Seite zugreift, wird die Seitennummer an den oberen Rand des Stapels verschoben, und andere Seitennummern werden an den unteren Rand des Stapels verschoben. Wenn nicht genügend Speicher vorhanden ist, wird die Seitennummer am unteren Rand des Stapels verschoben ENTFERNT. Auf diese Weise steht oben im Stapel immer die Nummer der zuletzt aufgerufenen Seite und unten im Stapel die Seitennummer der zuletzt besuchten Seite.

Zum Beispiel bei der Eingabe der folgenden Sequenz: 4,7,0,7,1,0,1,2,1,2,6

Das Ergebnis ist:

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 🎜>Ein LRU-Cache von Node.js
, Kapazität ist die Cache-Kapazität, die erstellt wird, wenn sie 0 ist. Allgemeines Caching.

Der LRU-Algorithmus kann auch in einigen praktischen Anwendungen verwendet werden, beispielsweise wenn Sie einen Browser erstellen möchten, oder Ähnliche Taobao-Clientanwendungen verwenden dieses Prinzip. Jeder weiß, dass der Browser beim Surfen im Internet die heruntergeladenen Bilder vorübergehend in einem Ordner auf dem lokalen Computer speichert. Beim nächsten Besuch werden sie direkt aus dem temporären Ordner auf dem lokalen Computer gelesen. Allerdings unterliegt der temporäre Ordner, in dem Bilder gespeichert werden, einer bestimmten Kapazitätsgrenze. Wenn Sie zu viele Webseiten durchsuchen, werden einige der Bilder, die Sie am seltensten verwenden, gelöscht und nur die zuletzt verwendeten Bilder bleiben erhalten. Zu diesem Zeitpunkt kann der LRU-Algorithmus verwendet werden. Zu diesem Zeitpunkt speichert der spezielle Stapel im obigen Algorithmus nicht die Seriennummer der Seite, sondern die Seriennummer oder Größe jedes Bildes

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());*/

Nach dem Login kopieren

Objektklasse

wird dargestellt, damit der Stapel Objekte speichern kann.

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der von Nodejs basierenden Cache-Verarbeitungsoperationsmethode basierend auf dem LRU-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!