Implémentation du cache LRU à l'aide de Javascript

Introduction

LRU signifie Le moins récemment utilisé. Un cache LRU est un type de cache dans lequel les entrées les moins récemment utilisées sont supprimées lorsque le cache atteint sa capacité.

• La principale raison d'utiliser un cache LRU est d'améliorer les performances d'accès aux données. L'accès aux données à partir d'un cache est généralement plus rapide que leur récupération à partir de la mémoire principale ou d'un serveur distant.
• En stockant les données les plus récemment utilisées dans le cache, le risque d'accès au cache est augmenté, ce qui à son tour améliore la vitesse de récupération des données.

Pour info :

• Une structure de données cartographiques est utilisée pour imiter le comportement d'une table de hachage. Cela permet des opérations de recherche, d'insertion et de suppression efficaces.
• Une liste à double lien est mise en œuvre pour permettre un déplacement facile entre les éléments. Cela offre la possibilité de parcourir dans les deux sens (avant et arrière) et d'effectuer des insertions et des suppressions à temps constant.
• La combinaison de ces deux structures de données permet des opérations efficaces, en tirant parti des avantages des tables de hachage et des listes à double lien.

Voici un exemple de base de la façon dont un cache LRU peut être implémenté en JavaScript :

// Why we need this LRU
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

//Least Recently used
class LRU {
    constructor() {
     this.head = this.tail = null;
     this.map = new Map();
     this.size = 0; // Why I added size, because may be in future we can say if capacity reach to the size, we will remove the tail first and then insert.
    }

    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        }

        return -1;
    }

    update(key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        } else {
            console.log('Key not found'); 
            // Here we can check for capacity if available we can call insert
            // if capacity is not available we will remove the tail and then insert.
        }
    }

    remove(node) {
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    insert(key, value) {
        const newNode = new Node(key, value);
        this.map.set(key, newNode);
        if (this.head === null) {
            this.head = this.tail = newNode;
            this.size = 1;
            return;
        }
        // We need to insert at the Begining
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head= newNode;
        this.size++;
        return;
    }
}

const test = new LRU();
test.insert('A', 20);
test.insert('B', 10);
test.insert('C', 5);
test.insert('D', 7);

console.log(test);
console.log('------------------');
console.log('C ---> ', test.get('C'));
console.log('D ---> ', test.get('D'));

console.log('D ---> ', test.update('B', 100));

/*
LRU {
  tail: <ref *1> Node {
    key: 'A',
    value: 20,
    next: null,
    prev: Node { key: 'B', value: 10, next: [Circular *1], prev: [Node] }
  },
  head: <ref *2> Node {
    key: 'D',
    value: 7,
    next: Node { key: 'C', value: 5, next: [Node], prev: [Circular *2] },
    prev: null
  },
  map: Map(4) {
    'A' => <ref *1> Node {
      key: 'A',
      value: 20,
      next: null,
      prev: [Node]
    },
    'B' => Node { key: 'B', value: 10, next: [Node], prev: [Node] },
    'C' => Node { key: 'C', value: 5, next: [Node], prev: [Node] },
    'D' => <ref *2> Node {
      key: 'D',
      value: 7,
      next: [Node],
      prev: null
    }
  },
  size: 4
}
------------------
C --->  5
D --->  7
D --->  100
B --->  100
*/

N'hésitez pas à me contacter si vous avez des inquiétudes.

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!