Python:xây dựng bộ nhớ cache LRU

LRU cache trong Python3.3 có chèn, xóa và tìm kiếm O (1).

Thiết kế sử dụng danh sách các mục nhập được liên kết kép theo hình tròn (được sắp xếp từ cũ nhất đến mới nhất) và một bảng băm để xác định các liên kết riêng lẻ. Lần truy cập bộ nhớ cache sử dụng bảng băm để tìm liên kết có liên quan và di chuyển nó lên đầu danh sách. Bộ nhớ cache bỏ lỡ xóa liên kết cũ nhất và tạo một liên kết mới ở đầu danh sách được liên kết.

Đây là một phiên bản đơn giản (nhưng nhanh) trong 33 dòng của Python rất cơ bản (chỉ sử dụng từ điển và các thao tác danh sách đơn giản). Nó chạy trên Python2.0 trở lên (hoặc PyPy hoặc Jython hoặc 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))

Bắt đầu bằng Python 3.1, OrderDict làm cho việc triển khai bộ đệm LRU thậm chí còn đơn giản hơn:

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