Caché LRU

Desaloja el elemento menos usado recientemente cuando se llena. Hash map + lista doblemente ligada = O(1) en todo.

Dos necesidades O(1), ninguna estructura sola

• Buscar por key, rápido → hash map (pero sin orden)
• Rastrear y actualizar recencia, rápido → lista ligada (pero búsqueda O(n))
• Combínalas: map de key → nodo en una lista doblemente ligada ordenada por recencia
• Frente = más reciente · atrás = menos reciente (la víctima del desalojo)

Observa la lista de recencia

put E (lleno) → desaloja B (atrás, el menos reciente). get A → mueve A al frente. El frente se llena con lo que usas; el fondo es lo que desalojas.

Por qué LRU: hit rate

Carga sesgada (Zipf), capacidad 50: LRU 71% vs FIFO/aleatoria 65%. La recencia predice la reutilización.

Lo "doblemente ligada" es lo que sostiene todo

• El desalojo y el mover-al-frente necesitan quitar en O(1) un nodo DE EN MEDIO
• La simplemente ligada no puede (necesita el predecesor) → tiene que ser doblemente ligada
• Los centinelas de cabeza/cola evitan casos borde
• Punto ciego: los SCANS contaminan el caché → variantes ARC / 2Q / LRU-K

Para llevar

Dos estructuras compartiendo nodos cumplen un requisito de dos partes — el patrón de composición. OrderedDict / functools.lru_cache SON esto por dentro. Siguiente: árboles k-d — búsqueda de vecinos más cercanos particionando el espacio.