Python:vytvoření mezipaměti LRU

mezipaměť LRU v Pythonu3.3 má O(1) vkládání, mazání a vyhledávání.

Návrh používá kruhový dvojitě propojený seznam položek (uspořádaných od nejstarších k nejnovějším) a hashovací tabulku k nalezení jednotlivých odkazů. Přístupy do mezipaměti používají hašovací tabulku k vyhledání příslušného odkazu a jeho přesunutí na začátek seznamu. Chyby v mezipaměti odstraní nejstarší odkaz a vytvoří nový odkaz na začátku seznamu odkazů.

Zde je zjednodušená (ale rychlá) verze na 33 řádcích velmi základního Pythonu (používá pouze jednoduché operace se slovníky a seznamy). Běží na Pythonu 2.0 a novějších (nebo PyPy nebo Jythonu nebo Pythonu3.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))

Počínaje Pythonem 3.1, OrderedDict ještě jednodušší implementovat mezipaměť 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