Der LRU-Cache in Python3.3 hat O(1) Insertion, Deletion und Search.
Das Design verwendet eine kreisförmige, doppelt verknüpfte Liste von Einträgen (geordnet vom ältesten zum neuesten) und eine Hash-Tabelle, um einzelne Links zu lokalisieren. Cache-Treffer verwenden die Hash-Tabelle, um den relevanten Link zu finden und an den Kopf der Liste zu verschieben. Cache-Mißerfolge löschen den ältesten Link und erstellen einen neuen Link am Anfang der verknüpften Liste.
Hier ist eine vereinfachte (aber schnelle) Version in 33 Zeilen von sehr einfachem Python (unter Verwendung nur einfacher Wörterbuch- und Listenoperationen). Es läuft auf Python2.0 und höher (oder PyPy oder Jython oder 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))
Ab Python 3.1 OrderedDict macht es noch einfacher, einen LRU-Cache zu implementieren:
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
