La caché LRU en Python3.3 tiene inserción, eliminación y búsqueda O(1).
El diseño utiliza una lista circular de entradas con doble enlace (ordenadas de la más antigua a la más nueva) y una tabla hash para ubicar enlaces individuales. Los hits de caché usan la tabla hash para encontrar el enlace relevante y moverlo al encabezado de la lista. La memoria caché no elimina el enlace más antiguo y crea un nuevo enlace al principio de la lista de enlaces.
Aquí hay una versión simplificada (pero rápida) en 33 líneas de Python muy básico (usando solo operaciones simples de diccionario y lista). Se ejecuta en Python2.0 y versiones posteriores (o PyPy o Jython o Python3.x):
class LRU_Cache:
def __init__(self, original_function, maxsize=1024):
# Link structure: [PREV, NEXT, KEY, VALUE]
self.root = [None, None, None, None]
self.root[0] = self.root[1] = self.root
self.original_function = original_function
self.maxsize = maxsize
self.mapping = {}
def __call__(self, *key):
mapping = self.mapping
root = self.root
link = mapping.get(key)
if link is not None:
link_prev, link_next, link_key, value = link
link_prev[1] = link_next
link_next[0] = link_prev
last = root[0]
last[1] = root[0] = link
link[0] = last
link[1] = root
return value
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
oldest = root[1]
next_oldest = oldest[1]
root[1] = next_oldest
next_oldest[0] = root
del mapping[oldest[2]]
last = root[0]
last[1] = root[0] = mapping[key] = [last, root, key, value]
return value
if __name__ == '__main__':
p = LRU_Cache(ord, maxsize=3)
for c in 'abcdecaeaa':
print(c, p(c))
A partir de Python 3.1, OrderedDict hace que sea aún más simple implementar un caché LRU:
from collections import OrderedDict
class LRU_Cache:
def __init__(self, original_function, maxsize=1024):
self.original_function = original_function
self.maxsize = maxsize
self.mapping = OrderedDict()
def __call__(self, *key):
mapping = self.mapping
try:
value = mapping[key]
mapping.move_to_end(key)
except KeyError:
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
mapping.popitem(False)
mapping[key] = value
return value
