02_LRU_cache

"""
python3 only
LRU cache
"""
from collections import OrderedDict
from functools import wraps

"""缓存装饰器"""
def cache(func):
    """先引入一个简单的装饰器缓存，其实原理很简单，就是内部用一个字典缓存已经计算过的结果"""
    store = {}

    @wraps(func)
    def _(n): # 函数命名没实际意义，随便命名
        if n in store:
            return store[n]
        else:
            res = func(n)
            store[n] = res
            return res
    return _

@cache
def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)


class LRUCache:
    def __init__(self, capacity=128):
        self.capacity = capacity
        # OrderedDict 内部也是用循环双端链表实现
        self.od = OrderedDict

    def get(self, key, default=None):
        val = self.od.get(key, default)
        self.od.move_to_end(key) #最近被访问的放到最后面
        return val

    def add_or_update(self, key, value):
        if key in self.od:
            self.od[key] = value
            self.od.move_to_end(key)
        else:
            self.od[key] = value
            if len(self.od) > self.capacity:
                self.od.popitem(last=False)

    def __call__(self, func):
        """
        简单的LRU实现策略
        1 使用内置的dict，实际上是存储到python进程里，而使用redis可存储更多数据到服务器
        2 同时考虑超时timeout参数，如menmcahce的lazy expiration策略
        3 缺点：对于周期性的数据访问会导致命中率迅速下降，有一种优化是LRU-K，访问次数达到k次才将数据放入缓存
        """
        def _(n):
            if n in self.od:
                return self.get(n)
            else:
                val = func(n)
                self.add_or_update(n, val)
                return val
        return _

@LRUCache(10)
def f_use_lru(n):
    if n <= 1:
        return n
    return f(n-1) + f(n-2)

def test():
    import time
    beg = time.time()
    for i in range(34):
        print(f(i))
    print(time.time() - beg)
    beg = time.time()
    for i in range(34):
        print(f_use_lru(i))
    print(time.time() - beg)

if __name__ == '__main__':
    test()

• console

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
0.0