La cache LRU in Python3.3 ha O(1) inserimento, cancellazione e ricerca.
Il design utilizza un elenco circolare di voci a doppio collegamento (disposte dal più antico al più recente) e una tabella hash per individuare i singoli collegamenti. I risultati nella cache utilizzano la tabella hash per trovare il collegamento pertinente e spostarlo all'inizio dell'elenco. Gli errori nella cache eliminano il collegamento più vecchio e creano un nuovo collegamento all'inizio dell'elenco collegato.
Ecco una versione semplificata (ma veloce) in 33 righe di Python molto semplice (usando solo semplici dizionari e operazioni di elenco). Funziona su Python2.0 e versioni successive (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 partire da Python 3.1, OrderedDict rende ancora più semplice implementare una cache 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
