1.1.4 LRU缓存机制的 Python 实现不好，并不是 O(1)

[isudox]

可以通过类似 LinkedHashMap 的方式降低时间复杂度。

[zhiyong0804]

可以，直接上代码不？ :)

[isudox]

不好意思，没有及时回复 Issue。 因为目前 1.1.4 里提供的 LRU Python implementation 使用了 list.remove(value)，所以时间复杂度不会是 O(1)。 如果要实现 get 和 set 都是 O(1) 复杂度，需要用类似 LinkedHashMap 来实现。

class LRUCache:

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

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = self.LinkedMap(0, -1)
        self.tail = self.LinkedMap(0, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key not in self.map:
            return None
        target = self.map[key]
        self._remove(target)
        self._add(target)
        return target.value

    def put(self, key, value):
        if key not in self.map:
            if len(self.map) == self.capacity:
                del self.map[self.head.next.key]
                self._remove(self.head.next)
        else:
            self._remove(self.map[key])
        target = self.LinkedMap(key, value)
        self._add(target)
        self.map[key] = target

    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

    def _add(self, node):
        p = self.tail.prev
        p.next = node
        self.tail.prev = node
        node.prev = p
        node.next = self.tail