El LRU cache en Python3.3 tiene O (1) inserción, eliminación y búsqueda.
El diseño utiliza una lista de entradas circular doblemente unida (dispuestas del más antiguo al más nuevo) y una tabla hash para localizar enlaces individuales. Los hits de caché usan la tabla hash para encontrar el enlace relevante y moverlo al encabezado de la lista. La caché falla al eliminar el enlace más antiguo y crear un nuevo enlace en la cabecera de la lista vinculada.
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 más tarde (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))
Esto parece interesante, pero ¿cómo puedo obtenerlo del repositorio? No sé cómo hacer eso \ – daydreamer
@learner: la forma más fácil sería copiarlo desde el archivo al que me he vinculado. – delnan
he intentado pero cuando intento importar functools arroja functools error >>> importación Rastreo (llamada más reciente pasado): Archivo "", línea 1, en Archivo "functools.py", línea 151 no local hits, pierde ^ SyntaxError: sintaxis no válida Error en sys.excepthook: –
daydreamer