効率的なデータの保存と取得は、特に大量のデータセットや限られたメモリを扱う場(chǎng)合、ソフトウェア開発の重要な側(cè)面です。 最も最近使用されていない (LRU) キャッシュ は、この一般的な課題に対する洗練されたソリューションを提供します。この投稿では、LRU キャッシュについて、その機(jī)能、重要性、実裝、実際のアプリケーションについて説明します。

LRU キャッシュについて

LRU キャッシュは、所定の數(shù)のアイテムを保存するように設(shè)計(jì)されたデータ構(gòu)造です。 その中心的な機(jī)能は、キャッシュがその容量に達(dá)したときに、最も最近アクセスされていないアイテムを削除することにあります。 これにより、頻繁にアクセスされるデータはすぐに利用できる狀態(tài)に保たれ、使用頻度の低いデータは破棄されます。

要するに:

• LRU: 最近使用されていないもの。
• 機(jī)能: 限られた數(shù)のアイテムを維持します。いっぱいになると、新しいデータに対応するために、最も長(zhǎng)く使用されていない項(xiàng)目が削除されます。

LRU キャッシュは、メモリ キャッシュ、Web ブラウジング、データベース管理など、頻繁に使用されるデータへの迅速なアクセスが最も重要ですが、メモリに制約があるアプリケーションにとって非常に貴重です。

LRU キャッシュを使用する利點(diǎn)

LRU キャッシュを統(tǒng)合すると、次のような重要な利點(diǎn)が得られます。

1. パフォーマンスの向上: 最近アクセスしたデータを保存すると、繰り返しリクエストの取得時(shí)間が大幅に短縮されます。
2. メモリ使用の最適化: 最も重要なデータまたは頻繁にアクセスされるデータのみを保持することで、メモリの過負(fù)荷を防ぎます。
3. 大規(guī)模なデータセットの処理: 関連する項(xiàng)目のみをメモリ內(nèi)に保持することで大規(guī)模なデータセットを効率的に管理し、低速ストレージ (データベースや API など) からの繰り返しのフェッチを最小限に抑えます。
4. 待ち?xí)r間の短縮: 遅いソースからのデータ取得を最小限に抑えることで、応答時(shí)間が短縮されます。

LRU キャッシュの仕組み

LRU キャッシュは通常、次の 2 つのデータ構(gòu)造の組み合わせを使用します。

• 二重リンクリスト: アクセス順序 (最新のものから新しいものへ) を保持します。
• ハッシュ マップ (またはディクショナリ): キャッシュされたアイテムへの定時(shí) O(1) アクセスを有効にします。

プロセスは次のように動(dòng)作します:

• アイテム アクセス: アクセスされたアイテムは、二重リンク リストの先頭 (最近使用されたもの) に移動(dòng)されます。
• キャッシュ制限に達(dá)しました: スペースを確保するために、最も最近使用されていない項(xiàng)目 (リストの末尾) が削除されます。
• 新しい項(xiàng)目の挿入: キャッシュがいっぱいでない場(chǎng)合、新しい項(xiàng)目はリストの先頭と O(1) アクセスのハッシュ マップに追加されます。

このハッシュ マップと二重リンク リストの組み合わせにより、get と put の両方の操作で定數(shù)時(shí)間 O(1) の複雑さが確保されます。

実用的な LRU キャッシュの実裝 (JavaScript)

Map (挿入順序を維持する) と容量制限を使用した簡(jiǎn)単な JavaScript 実裝は次のとおりです。

コード例 (JavaScript):

class LRUCache {
    constructor(capacity) {
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, val);
        return val;
    }

    put(key, value) {
        if (this.cache.has(key)) this.cache.delete(key);
        else if (this.cache.size >= this.capacity) this.cache.delete(this.cache.keys().next().value);
        this.cache.set(key, value);
    }
}

// Usage Example:
const cache = new LRUCache(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
console.log(cache.get(1)); // "A"
cache.put(4, "D"); // Evicts 2
console.log(cache.get(2)); // -1
console.log(cache.get(3)); // "C"
console.log(cache.get(4)); // "D"

説明:

• get(key): キーが存在する場(chǎng)合は値を返します。それ以外の場(chǎng)合は -1 を返します。 アクセスされたキーを前面に移動(dòng)します。
• put(key, value): キーと値のペアを挿入します。 キャッシュがいっぱいの場(chǎng)合、最も最近使用されていないアイテムが削除されます。

LRU キャッシュ アプリケーション

LRU キャッシュは、さまざまなシナリオで非常に有益です。

1. Web キャッシュ: HTTP 応答、畫像、または API 結(jié)果をキャッシュします。
2. データベース クエリ キャッシュ: 頻繁にアクセスされるクエリ結(jié)果を保存します。
3. セッション管理: メモリ內(nèi)のユーザー セッション データを管理します。
4. メモリ管理: 頻繁に使用されるオブジェクトに優(yōu)先順位を付けてメモリ使用量を最適化します。

メリットとデメリット

利點(diǎn):

• O(1) 時(shí)間計(jì)算量: 非常に効率的な get および put 操作。
• スペース効率: 頻繁に使用されるデータのみを保存することでキャッシュ サイズを最適化します。

欠點(diǎn):

• 制限された容量: 事前定義された容量により、保存されるデータの量が制限されます。
• キャッシュ ミス: キャッシュにないデータ (キャッシュ ミス) にアクセスするには、元のソースからフェッチする必要があります。

結(jié)論

LRU キャッシュは、効率的なメモリ管理とデータ取得のための強(qiáng)力なデータ構(gòu)造です。定時(shí)操作とスペースの最適化により、さまざまなアプリケーションのパフォーマンスとスケーラビリティを向上させるための貴重なツールになります。 LRU キャッシュを理解して実裝することは、効率的で応答性の高いシステムを構(gòu)築するために非常に重要です。

以上がLRU キャッシュについて: 効率的なデータの保存と取得の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。