Qué es LRU y cómo implementar un mecanismo de caché LRU en JavaScript

Introducción

LRU es la abreviatura de Least Recently Used (menos recientemente usado), y es una estrategia de reemplazo de caché. Cuando la caché alcanza su límite de almacenamiento, LRU elimina la entrada menos recientemente usada. Esta estrategia se basa en la suposición de que los datos usados recientemente probablemente se volverán a usar en el futuro, mientras que los datos menos recientemente usados probablemente no se usarán nuevamente.

Implementación de una caché LRU en JavaScript

Para implementar una caché LRU en JavaScript, se puede utilizar Map combinado con una lista doblemente enlazada. Map asegura el orden de inserción de los elementos, y la lista doblemente enlazada ayuda a mover eficientemente los elementos más recientemente usados al inicio y eliminar los elementos menos recientemente usados.

Implementación del código

A continuación se muestra una implementación simple de la caché LRU:

1
// Definición de la clase del nodo de la lista doblemente enlazada
2
class Node {
3
  constructor(key, value) {
4
    this.key = key;
5
    this.value = value;
6
    this.prev = null;
7
    this.next = null;
8
  }
9
}
10


11
// Definición de la clase de la caché LRU
12
class LRUCache {
13
  constructor(capacity) {
14
    this.capacity = capacity; // Capacidad de la caché
15
    this.map = new Map(); // Almacenar datos de la caché
16
    this.head = new Node(null, null); // Nodo cabeza virtual
17
    this.tail = new Node(null, null); // Nodo cola virtual
18
    this.head.next = this.tail;
19
    this.tail.prev = this.head;
20
  }
21


22
  // Obtener el valor de la caché
23
  get(key) {
24
    if (!this.map.has(key)) {
25
      return -1; // Si la caché no tiene la clave, retorna -1
26
    }
27


28
    const node = this.map.get(key);
29
    this._remove(node); // Eliminar el nodo de la lista doblemente enlazada
30
    this._add(node); // Agregar el nodo al final de la lista (indicando que fue recientemente usado)
31


32
    return node.value;
33
  }
34


35
  // Agregar o actualizar el valor de la caché
36
  put(key, value) {
37
    if (this.map.has(key)) {
38
      this._remove(this.map.get(key)); // Si la caché ya tiene la clave, eliminar el nodo antiguo
39
    }
40


41
    const newNode = new Node(key, value);
42
    this._add(newNode); // Agregar el nuevo nodo al final de la lista
43
    this.map.set(key, newNode);
44


45
    if (this.map.size > this.capacity) {
46
      const lruNode = this.head.next; // Obtener el nodo menos recientemente usado
47
      this._remove(lruNode); // Eliminar el nodo menos recientemente usado de la lista
48
      this.map.delete(lruNode.key); // Eliminar la clave menos recientemente usada de la caché
49
    }
50
  }
51


52
  // Eliminar el nodo de la lista doblemente enlazada
53
  _remove(node) {
54
    node.prev.next = node.next;
55
    node.next.prev = node.prev;
56
  }
57


58
  // Agregar el nodo al final de la lista doblemente enlazada
59
  _add(node) {
60
    node.prev = this.tail.prev;
61
    node.next = this.tail;
62
    this.tail.prev.next = node;
63
    this.tail.prev = node;
64
  }
65
}

Ejemplo de uso

1
const lru = new LRUCache(2);
2


3
lru.put(1, 1);
4
lru.put(2, 2);
5
console.log(lru.get(1)); // Imprime 1
6
lru.put(3, 3); // Elimina la clave 2
7
console.log(lru.get(2)); // Imprime -1 (no encontrado)
8
lru.put(4, 4); // Elimina la clave 1
9
console.log(lru.get(1)); // Imprime -1 (no encontrado)
10
console.log(lru.get(3)); // Imprime 3
11
console.log(lru.get(4)); // Imprime 4

Explicación del código

  1. Clase Node: utilizada para los nodos de la lista doblemente enlazada, contiene key, value y los punteros prev y next.
  2. Clase LRUCache: la clase principal que gestiona la caché, se inicializa con una capacidad capacity y crea un Map y dos nodos centinela head y tail.
  3. Método get: obtiene el valor de la caché, si existe, mueve el nodo al final (indicando que fue recientemente usado).
  4. Método put: inserta un nuevo valor en la caché, si la clave ya existe, elimina el nodo antiguo. Después de insertar el nuevo nodo, verifica si se supera la capacidad, si es así, elimina el nodo al principio de la lista (indicando que es el menos recientemente usado).
  5. Método _remove: elimina el nodo de la lista doblemente enlazada.
  6. Método _add: agrega el nodo al final de la lista doblemente enlazada.

Esta implementación asegura que las operaciones get y put se puedan completar en tiempo de complejidad constante ( O(1) ).

Conclusión

Con el código y los comentarios anteriores, entendemos cómo implementar una caché LRU simple en JavaScript. La caché LRU es una estrategia de reemplazo de caché comúnmente utilizada y se aplica ampliamente en varios sistemas de caché. Espero que este artículo te ayude a comprender mejor el principio y la aplicación de la caché LRU.

Artículos similares

Cómo Instalar y Renovar Certificados Let’s Encrypt en un Servidor de Alibaba Cloud

Cómo Instalar y Renovar Certificados Let’s Encrypt en un Servidor de Alibaba Cloud

Cómo Crear un Blog: Guía Completa y Análisis de Plataformas

Cómo Crear un Blog: Guía Completa y Análisis de Plataformas