Python:membangun cache LRU

Cache LRU di Python3.3 memiliki O(1) penyisipan, penghapusan, dan pencarian.

Desainnya menggunakan daftar entri tertaut ganda melingkar (diurutkan dari yang terlama hingga yang terbaru) dan tabel hash untuk menemukan tautan individual. Klik cache menggunakan tabel hash untuk menemukan tautan yang relevan dan memindahkannya ke bagian atas daftar. Cache tidak terjawab menghapus tautan terlama dan membuat tautan baru di bagian atas daftar tertaut.

Ini adalah versi sederhana (tapi cepat) dalam 33 baris Python yang sangat dasar (hanya menggunakan kamus sederhana dan operasi daftar). Ini berjalan di Python2.0 dan yang lebih baru (atau PyPy atau Jython atau 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))

Mulai dari Python 3.1, OrderedDict membuatnya lebih mudah untuk mengimplementasikan 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