SolveConPython

Python Reto #25 — LRU Cache simplificado (capacidad máxima)

Nivel: Intermedio+
Tema: Caché, política LRU (Least Recently Used), dict ordenado, diseño de APIs, tests con pytest
Objetivo: Implementar una caché con capacidad limitada que expulsa el elemento menos recientemente usado cuando se llena.

En Python 3.7+ los dict preservan el orden de inserción. Usaremos ese comportamiento para simular LRU moviendo claves “usadas” al final.

Enunciado

Crea una clase LRUCache con:

Constructor

LRUCache(capacidad)

Reglas:

  1. Si capacidad es None o no es int, lance TypeError.
  2. Si capacidad <= 0, lance ValueError.

Métodos

get(clave)

  • Devuelve el valor asociado a clave si existe.
  • Si no existe, devuelve None.
  • Si existe, debe marcar esa clave como “recientemente usada” (moverla al final).

set(clave, valor)

  • Inserta o actualiza el par clave → valor.
  • Si la clave ya existe, actualiza el valor y marca como usada.
  • Si se excede la capacidad, debe expulsar la clave menos recientemente usada.
  • clave debe ser hashable; si no, lance TypeError.

__len__()

  • Devuelve el número de elementos en caché.

Ejemplos

cache = LRUCache(2)
cache.set("a", 1)
cache.set("b", 2)

cache.get("a") # 1 (ahora "a" es la más reciente)
cache.set("c", 3) # expulsa "b" (porque "b" es la menos usada)

cache.get("b") # None
cache.get("c") # 3
len(cache) # 2

Pistas

  1. Usa un dict interno: self._data = {}
  2. Para mover una clave al final:
    • lee el valor
    • elimina la clave
    • reinsertarla con el mismo valor
  3. Para expulsar la menos reciente:
    • la primera clave del dict es la menos reciente
    • obtén next(iter(self._data)) y elimínala
  4. Verifica hashability con hash(clave).

Solución explicada (paso a paso)

  1. Validamos la capacidad.
  2. set():
    • validar hashability
    • si existe: borrar y reinsertar (mover al final)
    • si no existe y está lleno: expulsar la primera clave
    • insertar
  3. get():
    • si existe: mover al final y devolver valor
    • si no: devolver None
  4. __len__: retornar len(self._data).

Ejecuta:

  • pytest -q

Variantes para subir de nivel (opcional)

  1. Método items() para inspeccionar el estado del caché (para debugging)
  2. Soportar pop(clave) explícito
  3. Añadir estadísticas (hits/misses/evictions)
  4. Implementar LRU con lista doblemente enlazada (más “clásico”, O(1) real para mover nodos)

Lo que aprendiste

  • Qué es LRU y por qué se usa en sistemas reales
  • Cómo usar el orden de inserción de dict como estructura base
  • Cómo diseñar una clase pequeña con contrato claro
  • Cómo testear expulsión y actualización correctamente

Accede al código completo y a los tests en GitHub para ejecutar y modificar la solución localmente.

Si quieres seguir con retos “tipo producción”, el siguiente recomendado es:
Reto #26 — Rate limiter (token bucket simple) para practicar tiempo, estado y lógica defensiva.