Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 31/32

LRU cache

✕
1/8

Forget the least recent

A cache stores results that took work to get, so you don't ask for them again. Since not everything fits, something has to go when it's full. The LRU rule (*least recently used*) removes whatever has gone unused the longest, like your phone's recent apps.

In JavaScript, a Map remembers the order in which keys were added. If you delete a key when you use it and add it back, it moves to the end: the start of the Map is always the oldest.

leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • At first the order is arrival order: a, b, c.
  • Deleting and re-adding "a" sends it to the end.
  • m.keys().next().value gives the first key, the oldest: "b".

Map on MDN (Spanish) ↗

The whole lesson on one page

Forget the least recent

A cache stores results that took work to get, so you don't ask for them again. Since not everything fits, something has to go when it's full. The LRU rule (*least recently used*) removes whatever has gone unused the longest, like your phone's recent apps.

In JavaScript, a Map remembers the order in which keys were added. If you delete a key when you use it and add it back, it moves to the end: the start of the Map is always the oldest.

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);
  • At first the order is arrival order: a, b, c.
  • Deleting and re-adding "a" sends it to the end.
  • m.keys().next().value gives the first key, the oldest: "b".

LRU with a Map

With that trick the cache takes just a few lines:

  • get: if the key is there, take it out and put it back (now it's the most recent) and return its value; otherwise -1.
  • put: add it at the end and, if it no longer fits, delete the first one, the oldest.

Both operations are 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") returns 30 and, along the way, makes "tacos" recent.
  • Adding "sopes" makes three, which doesn't fit: "tortas" goes, since it had been unused the longest, which is why its get returns -1.
  • "tacos" and "sopes" remain, oldest to newest.

The classic version: map and doubly linked list

In many languages a map doesn't keep order, and an LRU is built from two pieces:

  • A doubly linked list with the order of use: the most recent in front, the oldest at the back.
  • A map from key to node, to reach any node in O(1) without walking the list.

The list has to be doubly linked because, to remove a node from the middle in O(1), you need to know its previous node. Two dummy nodes (sentinels) at the ends save you from checking whether the list is empty.

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());
  • Here the list goes from most recent to oldest: after adding a, b and c, the order is c, b, a.
  • get("a") moves "a" to the front without walking anything: the map gives the node and the doubly linked list unhooks it.
  • Adding "d" makes one too many, and the one at the back, "b", goes. That's the state in the drawing: d, a, c.