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:

Si capacidad es None o no es int, lance TypeError.
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

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

Solución explicada (paso a paso)

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

Python

			
class LRUCache:
    """
    LRU Cache simplificado usando dict ordenado (insertion-order).
    Política:
    - Cada get/set marca la clave como 'recientemente usada' moviéndola al final.
    - Si se excede la capacidad, expulsa la clave menos recientemente usada
      (la primera del dict).
    """
    def __init__(self, capacidad: int):
        if capacidad is None or not isinstance(capacidad, int):
            raise TypeError("El parámetro 'capacidad' debe ser un entero (int).")
        if capacidad <= 0:
            raise ValueError("'capacidad' debe ser mayor que 0.")
        self.capacidad = capacidad
        self._data = {}
    def __len__(self) -> int:
        return len(self._data)
    def _asegurar_hashable(self, clave):
        try:
            hash(clave)
        except TypeError as exc:
            raise TypeError("La 'clave' debe ser hashable (p. ej. str, int, tuple).") from exc
    def get(self, clave):
        self._asegurar_hashable(clave)
        if clave not in self._data:
            return None
        valor = self._data[clave]
        # mover al final
        del self._data[clave]
        self._data[clave] = valor
        return valor
    def set(self, clave, valor) -> None:
        self._asegurar_hashable(clave)
        if clave in self._data:
            # actualizar y mover al final
            del self._data[clave]
            self._data[clave] = valor
            return
        # nueva clave
        if len(self._data) >= self.capacidad:
            # expulsar la menos reciente (primera insertada)
            clave_menos_reciente = next(iter(self._data))
            del self._data[clave_menos_reciente]
        self._data[clave] = valor

		

Python

			
import pytest
from reto_25_lru_cache import LRUCache
def test_lru_basico_expulsiona_menos_reciente():
    cache = LRUCache(2)
    cache.set("a", 1)
    cache.set("b", 2)
    assert cache.get("a") == 1  # "a" pasa a ser la más reciente
    cache.set("c", 3)           # debe expulsar "b"
    assert cache.get("b") is None
    assert cache.get("c") == 3
    assert len(cache) == 2
def test_set_actualiza_y_mueve_al_final():
    cache = LRUCache(2)
    cache.set("a", 1)
    cache.set("b", 2)
    cache.set("a", 10)  # actualizar "a" la vuelve reciente
    cache.set("c", 3)   # debe expulsar "b"
    assert cache.get("a") == 10
    assert cache.get("b") is None
    assert cache.get("c") == 3
def test_get_inexistente_devuelve_none():
    cache = LRUCache(2)
    assert cache.get("x") is None
def test_capacidad_invalida():
    with pytest.raises(TypeError):
        LRUCache(None)
    with pytest.raises(TypeError):
        LRUCache("2")
    with pytest.raises(ValueError):
        LRUCache(0)
    with pytest.raises(ValueError):
        LRUCache(-1)
def test_clave_no_hashable_lanza_typeerror():
    cache = LRUCache(2)
    with pytest.raises(TypeError):
        cache.set(["lista"], 1)
    with pytest.raises(TypeError):
        cache.get(["lista"])

		

Ejecuta:

pytest -q

Variantes para subir de nivel (opcional)

Método items() para inspeccionar el estado del caché (para debugging)
Soportar pop(clave) explícito
Añadir estadísticas (hits/misses/evictions)
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.