造个轮子——实现python中的lru_cache

发表于 更新于 分类于 Changyan：

力扣题

首先看一道高频经典力扣题146. LRU 缓存机制，题干不再赘述。直接放出我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class ListNode:
    def __init__(self, key=0, val=0, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.currentSize = 0
        self.dic = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key) -> int:
        if key in self.dic:
            self.move_to_end(key)
            return self.dic[key].val
        else:
            return -1

    def put(self, key, value: int) -> None:

        if self.capacity == 0: return

        if key in self.dic:  # 存在不用考虑size
            self.dic[key].val = value
            self.move_to_end(key)
        else:  # 不存在
            if self.currentSize == self.capacity:  # 满了
                self.delete(self.head.next.key)
                self.currentSize -= 1
            self.append(key, value)
            self.currentSize += 1

    def append(self, key, value: int) -> None:
        nodePrev = self.tail.prev
        nodeNext = self.tail

        node = ListNode(key, value, nodePrev, nodeNext)
        self.dic[key] = node

        nodePrev.next = node
        nodeNext.prev = node

    def delete(self, key) -> ListNode:
        node = self.dic.pop(key)

        nodePrev = node.prev
        nodeNext = node.next

        nodePrev.next = nodeNext
        nodeNext.prev = nodePrev

        return node

    def move_to_end(self, key) -> None:
        popped = self.delete(key)
        self.append(popped.key, popped.val)

嗯。hashmap + 双向链表 搞定！

Python装饰器

既然LRU类都整出来了，自己可以自己实现 python functools里的 @lru_cache呀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from functools import wraps

# 自己定义一个lru装饰器
def lru_cache(size: [int, None] = 128):
    """
    size 如果是 None, 则缓存大小不受限制。但是递归深度python 是有限制的，
    使用这个装饰器并不能解决所有动态规划问题
    """
    if size is None:
        size = float('inf')

    def lru_cache_decorator(f):
        lru = LRUCache(size)

        @wraps(f)
        def decorated(*args, **kwargs):
            cached = lru.get(args)
            if cached == -1:
                ret = f(*args, **kwargs)
                lru.put(args, ret)
                return ret
            else:
                return cached

        return decorated

    return lru_cache_decorator

如何使用呢？

1
2
3
4
5
6
7
8
9
@lru_cache()
def feb(n):
    if n <= 1: return 1
    return feb(n - 1) + feb(n - 2)


if __name__ == '__main__':
    print(feb(1000)) # 跑起来飞快 去掉 装饰器慢如乌龟

参考链接

146. LRU 缓存机制

Python 函数装饰器 | 菜鸟教程 (runoob.com)