LRUアルゴリズムに基づいてNodejsで実装されるキャッシュ処理操作方法を詳しく解説

この記事では、LRU アルゴリズムに基づいて Node

js によって実装されるキャッシュ処理 操作を主に紹介し、具体的な例に基づいて LRU アルゴリズムの原理と機能、および LRU を使用した Nodejs の関連実装スキルを分析します。キャッシュ処理操作を実装するためのアルゴリズム 必要なもの 友人はそれを参照できます

この記事では、LRU アルゴリズムに基づいて Nodejs によって実装されたキャッシュ処理操作について説明します。詳細は次のとおりです。

LRU は、最も最近使用されていないページ置換アルゴリズムの略称であり、仮想ページのストレージ管理を提供し、その使用状況に基づいて決定を行います。メモリに転送された後のページ。各ページの将来の使用状況を予測することは不可能であるため、「最近の過去」を「近い将来」の近似値として使用することしかできません。そのため、LRU アルゴリズムは、長期間使用されていないページを削除します。

特別なスタックを使用して、現在使用している各ページのページ番号を保存できます。新しいプロセスがページにアクセスすると、ページ番号がスタックの一番上にプッシュされ、メモリが不足している場合は、他のページ番号がスタックの一番下に移動されます。削除されました。このように、スタックの一番上は常に最後にアクセスされたページの番号になり、スタックの一番下は最も長い間アクセスされていないページのページ番号になります。

たとえば、次のシーケンスを入力すると: 4,7,0,7,1,0,1,2,1,2,6

結果は次のようになります:

4

4 7
4 0
4 0 7
4 1 2
4 7 0 2 1
4 7 0 1 2
7 0 1 2 6


Node.js
のLRUキャッシュ、capacityはキャッシュ容量、0の場合は一般的なキャッシュ構築されています。

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

LRU アルゴリズムは、いくつかの実用的なアプリケーションでも使用できます。たとえば、淘宝網クライアントに似たブラウザーやアプリケーションを作成したい場合は、この原則を使用する必要があります。 Web を閲覧すると、ブラウザーはダウンロードした写真をローカル マシン上のフォルダーに一時的に保存し、次回アクセスするときにローカル マシン上の一時フォルダーから直接読み取られることは誰もが知っています。ただし、画像を保存する一時フォルダーには一定の容量制限があり、Web ページを閲覧しすぎると、最も頻繁に使用しない画像の一部が削除され、最近使用した画像のみが保持されます。このとき、LRU アルゴリズムを使用できます。このとき、上記のアルゴリズムの特別なスタックはページのシリアル番号ではなく、各ピクチャのシリアル番号またはサイズを保存するため、上記のスタックの要素が使用されます。

Object クラス
この場合、スタックはオブジェクトを保存できます。

以上がLRUアルゴリズムに基づいてNodejsで実装されるキャッシュ処理操作方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。