Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 31/32

Caché LRU

✕
1/8

Olvidar lo menos reciente

Una caché guarda resultados que costó trabajo conseguir, para no volver a pedirlos. Como no cabe todo, cuando se llena hay que sacar algo. La regla LRU (*least recently used*) saca lo que lleva más tiempo sin usarse, como las apps recientes del teléfono.

En JavaScript, un Map recuerda el orden en que se metieron las claves. Si al usar una clave la borras y la vuelves a meter, se va al final: el principio del Map es siempre lo más viejo.

leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • Al principio el orden es el de llegada: a, b, c.
  • Borrar y volver a meter «a» la manda al final.
  • m.keys().next().value da la primera clave, la más vieja: «b».

Map en MDN ↗

Toda la lección en una página

Olvidar lo menos reciente

Una caché guarda resultados que costó trabajo conseguir, para no volver a pedirlos. Como no cabe todo, cuando se llena hay que sacar algo. La regla LRU (*least recently used*) saca lo que lleva más tiempo sin usarse, como las apps recientes del teléfono.

En JavaScript, un Map recuerda el orden en que se metieron las claves. Si al usar una clave la borras y la vuelves a meter, se va al final: el principio del Map es siempre lo más viejo.

const m = new Map();
m.set("a", 1);
m.set("b", 2);
m.set("c", 3);
console.log([...m.keys()]);

m.delete("a");
m.set("a", 1);
console.log([...m.keys()]);

console.log(m.keys().next().value);
  • Al principio el orden es el de llegada: a, b, c.
  • Borrar y volver a meter «a» la manda al final.
  • m.keys().next().value da la primera clave, la más vieja: «b».

LRU con un Map

Con ese truco la caché sale en pocas líneas:

  • get: si la clave está, se saca y se vuelve a meter (ahora es la más reciente) y se devuelve su valor; si no, -1.
  • put: se mete al final y, si ya no cabe, se borra la primera, la más vieja.

Las dos operaciones son O(1).

class CacheLRU {
  constructor(capacidad) {
    this.capacidad = capacidad;
    this.datos = new Map();
  }
  get(clave) {
    if (!this.datos.has(clave)) return -1;
    const valor = this.datos.get(clave);
    this.datos.delete(clave);
    this.datos.set(clave, valor);
    return valor;
  }
  put(clave, valor) {
    this.datos.delete(clave);
    this.datos.set(clave, valor);
    if (this.datos.size > this.capacidad) {
      const masVieja = this.datos.keys().next().value;
      this.datos.delete(masVieja);
    }
  }
}

const c = new CacheLRU(2);
c.put("tacos", 30);
c.put("tortas", 45);
console.log(c.get("tacos"));
c.put("sopes", 25);
console.log(c.get("tortas"));
console.log([...c.datos.keys()]);
  • get("tacos") da 30 y, de paso, vuelve reciente a «tacos».
  • Al meter «sopes» ya no caben tres: sale «tortas», que era la que llevaba más tiempo sin usarse, y por eso su get da -1.
  • Quedan «tacos» y «sopes», de la más vieja a la más nueva.

La versión clásica: mapa y lista doble

En muchos lenguajes el mapa no guarda el orden, y la LRU se arma con dos piezas:

  • Una lista doblemente enlazada con el orden de uso: la más reciente adelante, la más vieja atrás.
  • Un mapa de clave a nodo, para llegar a cualquier nodo en O(1) sin recorrer la lista.

La lista tiene que ser doble porque, para sacar un nodo de en medio en O(1), hay que conocer a su anterior. Dos nodos de mentira (centinelas) en las puntas evitan revisar si la lista está vacía.

dacnull
class Nodo {
  constructor(clave, valor) {
    this.clave = clave;
    this.valor = valor;
    this.ant = null;
    this.sig = null;
  }
}

class LRU {
  constructor(capacidad) {
    this.capacidad = capacidad;
    this.mapa = new Map();
    this.cabeza = new Nodo();
    this.cola = new Nodo();
    this.cabeza.sig = this.cola;
    this.cola.ant = this.cabeza;
  }
  quitar(n) {
    n.ant.sig = n.sig;
    n.sig.ant = n.ant;
  }
  alFrente(n) {
    n.sig = this.cabeza.sig;
    n.ant = this.cabeza;
    this.cabeza.sig.ant = n;
    this.cabeza.sig = n;
  }
  get(clave) {
    const n = this.mapa.get(clave);
    if (!n) return -1;
    this.quitar(n);
    this.alFrente(n);
    return n.valor;
  }
  put(clave, valor) {
    if (this.mapa.has(clave)) this.quitar(this.mapa.get(clave));
    const n = new Nodo(clave, valor);
    this.mapa.set(clave, n);
    this.alFrente(n);
    if (this.mapa.size > this.capacidad) {
      const viejo = this.cola.ant;
      this.quitar(viejo);
      this.mapa.delete(viejo.clave);
    }
  }
  orden() {
    const r = [];
    for (let n = this.cabeza.sig; n !== this.cola; n = n.sig) r.push(n.clave);
    return r;
  }
}

const c = new LRU(3);
c.put("a", 1);
c.put("b", 2);
c.put("c", 3);
console.log(c.orden());
c.get("a");
console.log(c.orden());
c.put("d", 4);
console.log(c.orden());
  • Aquí la lista va de la más reciente a la más vieja: después de meter a, b y c, el orden es c, b, a.
  • get("a") mueve «a» al frente sin recorrer nada: el mapa da el nodo y la lista doble lo desengancha.
  • Al meter «d» sobra uno y sale el de atrás, «b». Es el estado del dibujo: d, a, c.