Python:een LRU-cache bouwen

De LRU-cache in Python3.3 heeft O(1) invoegen, verwijderen en zoeken.

Het ontwerp maakt gebruik van een ronde dubbel gekoppelde lijst met vermeldingen (gerangschikt van oud naar nieuw) en een hashtabel om individuele links te lokaliseren. Cachehits gebruiken de hashtabel om de relevante link te vinden en deze naar de kop van de lijst te verplaatsen. Cache mist de oudste link verwijderen en een nieuwe link maken bovenaan de gekoppelde lijst.

Hier is een vereenvoudigde (maar snelle) versie in 33 regels van zeer eenvoudige Python (met alleen eenvoudige woordenboek- en lijstbewerkingen). Het draait op Python2.0 en hoger (of PyPy of Jython of 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))

Vanaf Python 3.1, OrderedDict maakt het nog eenvoudiger om een ​​LRU-cache te implementeren:

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