Struktur Data Cache LRU (Paling Kurang Digunakan).

LRU (Paling Kurang Digunakan) Cache ialah sejenis cache yang mengusir item yang paling kurang diakses baru-baru ini apabila cache melebihi kapasitinya. Ia berguna dalam senario di mana ingatan terhad dan anda mahu cache hanya data yang paling kerap diakses.

Dalam JavaScript, Cache LRU boleh dilaksanakan menggunakan gabungan Peta (untuk carian pantas dan mengekalkan susunan sisipan) dan Senarai Berganda (untuk sisipan dan pemadaman yang cekap pada kedua-dua hujung). Walau bagaimanapun, untuk kesederhanaan, kami akan menggunakan Peta dalam pelaksanaan berikut.

Berikut ialah pelaksanaan JavaScript Cache LRU:

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Using Map to maintain key-value pairs
    }
    // Get the value from the cache
    get(key) {
        if (!this.cache.has(key)) {
            return -1; // If the key is not found, return -1
        }

        // Key is found, move the key to the most recent position
        const value = this.cache.get(key);
        this.cache.delete(key); // Remove the old entry
        this.cache.set(key, value); // Reinsert to update its position (most recently used)

        return value;
    }

    // Add or update the value in the cache
    put(key, value) {
        if (this.cache.has(key)) {
            // If the key already exists, remove it to update its position
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // If the cache is at capacity, delete the least recently used item
            const leastRecentlyUsedKey = this.cache.keys().next().value;
            this.cache.delete(leastRecentlyUsedKey);
        }

        // Insert the new key-value pair (most recent)
        this.cache.set(key, value);
    }
}

Penjelasan:
Pembina: Kelas LRUCache dimulakan dengan kapasiti tertentu, dan ia menggunakan Peta untuk menyimpan pasangan nilai kunci yang dicache. Peta menjejaki susunan sisipan, yang membantu mengenal pasti item yang paling kurang digunakan (LRU) baru-baru ini.

dapatkan(kunci):

• Jika kunci wujud dalam cache, kaedah mengembalikan nilainya dan mengalihkan kunci ke kedudukan terbaharu dengan memadamkan kunci dahulu dan kemudian memasukkannya semula.
• Jika kunci tidak wujud, ia mengembalikan -1.

letak(kunci, nilai):

• Jika kunci sudah wujud dalam cache, ia mengalih keluar kunci dan memasukkannya semula (mengemas kini kedudukannya sebagai yang paling baru digunakan).
• Jika cache mencapai kapasitinya, ia mengalih keluar kunci yang paling kurang digunakan baru-baru ini (yang pertama dalam Peta).
• Akhir sekali, pasangan nilai kunci baharu ditambahkan pada cache.

Contoh Penggunaan:

const lruCache = new LRUCache(3); // Cache with a capacity of 3

lruCache.put(1, 'one');   // Add key 1
lruCache.put(2, 'two');   // Add key 2
lruCache.put(3, 'three'); // Add key 3

console.log(lruCache.get(1)); // Output: 'one' (key 1 becomes the most recently used)

lruCache.put(4, 'four'); // Cache is full, so it evicts key 2 (least recently used)

console.log(lruCache.get(2)); // Output: -1 (key 2 has been evicted)
console.log(lruCache.get(3)); // Output: 'three' (key 3 is still in the cache)
console.log(lruCache.get(4)); // Output: 'four' (key 4 is in the cache)

Atas ialah kandungan terperinci Struktur Data Cache LRU (Paling Kurang Digunakan).. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!