Le cache LRU dans Python3.3 a O(1) insertion, suppression et recherche.
La conception utilise une liste circulaire d'entrées à double lien (organisées du plus ancien au plus récent) et une table de hachage pour localiser les liens individuels. Les accès au cache utilisent la table de hachage pour trouver le lien pertinent et le déplacer en tête de liste. Le cache manque de supprimer le lien le plus ancien et de créer un nouveau lien en tête de la liste liée.
Voici une version simplifiée (mais rapide) en 33 lignes de Python très basique (utilisant uniquement des opérations simples de dictionnaire et de liste). Il fonctionne sur Python2.0 et versions ultérieures (ou PyPy ou Jython ou 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))
À partir de Python 3.1, OrderedDict rend encore plus simple l'implémentation d'un 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
