Structure des données du cache LRU (la moins récemment utilisée)

Le cache LRU (le moins récemment utilisé) est un type de cache qui expulse l'élément le moins récemment consulté lorsque le cache dépasse sa capacité. C'est utile dans les scénarios où la mémoire est limitée et où vous souhaitez mettre en cache uniquement les données les plus fréquemment consultées.

En JavaScript, un cache LRU peut être implémenté en utilisant une combinaison d'une carte (pour des recherches rapides et le maintien de l'ordre d'insertion) et d'une liste doublement liée (pour des insertions et des suppressions efficaces aux deux extrémités). Cependant, par souci de simplicité, nous utiliserons une Map dans l'implémentation suivante.

Voici une implémentation JavaScript d'un 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);
    }
}

Explication :
Constructeur : la classe LRUCache est initialisée avec une capacité donnée et utilise une carte pour stocker les paires clé-valeur mises en cache. La carte garde une trace de l'ordre d'insertion, ce qui permet d'identifier l'élément le moins récemment utilisé (LRU).

obtenir(clé):

• Si la clé existe dans le cache, la méthode renvoie sa valeur et déplace la clé vers la position la plus récente en supprimant d'abord la clé puis en la réinsérant.
• Si la clé n'existe pas, elle renvoie -1.

put(clé, valeur):

• Si la clé existe déjà dans le cache, il la supprime et la réinsère (en mettant à jour sa position comme la plus récemment utilisée).
• Si le cache atteint sa capacité, il supprime la clé la moins récemment utilisée (la première de la Map).
• Enfin, la nouvelle paire clé-valeur est ajoutée au cache.

Exemple d'utilisation :

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)

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!