LRUキャッシュ

lru_cache.py

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                           # key -> Node
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key, default=None):
        node = self.map.get(key)
        if node is None:
            return default
        self._unlink(node)                      # touch: move to the front
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) >= self.capacity:      # evict the least recently used
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)


cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")                                  # "a" is now the most recent
cache.put("c", 3)                               # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c"))  # None 1 3

python lru_cache.py