LRU算法原理

LRU (Least Recently Used，最近最少使用) 算法是一种缓存淘汰策略。其根据数据的历史访问记录来进行淘汰，核心思想是，“如果数据最近被访问过，那么将来被访问的几率也更高”。该算法最初为操作系统中一种内存管理的页面置换算法，主要用于找出内存中较久时间没有使用的内存块，将其移出内存从而为新数据提供空间。

python中的LRU

Python 的 3.2 版本中，引入了一个非常优雅的缓存机制，即 functool 模块中的 lru_cache 装饰器，可以直接将函数或类方法的结果缓存住，后续调用则直接返回缓存的结果。lru_cache 原型如下：

@functools.lru_cache(maxsize=None, typed=False)

使用 functools 模块的 lur_cache 装饰器，可以缓存最多 maxsize 个此函数的调用结果，从而提高程序执行的效率，特别适合于耗时的函数。参数 maxsize 为最多缓存的次数，如果为 None，则无限制，设置为 2 的幂 时，性能最佳；如果 typed=True（注意，在 functools32 中没有此参数），则不同参数类型的调用将分别缓存，例如 f(3) 和 f(3.0)。

二、举例说明

1.现在我们先不使用缓存来写一个求两数之和的函数，并调用执行它两次：

def test(a, b):
    print('开始计算a+b的值...')
    return a + b

print('1+2等于:', test(1, 2))
print('1+2等于:', test(1, 2))

执行结果

开始计算a+b的值...
1+2等于: 3
开始计算a+b的值...
1+2等于: 3

可以看到test被执行了两次，现在我们加上缓存再进行执行：

from functools import lru_cache

@lru_cache
def test(a, b):
    print('开始计算a+b的值...')
    return a + b

print(test(1, 2))
print(test(1, 2))

执行结果

开始计算a+b的值...
1+2等于: 3
1+2等于: 3

可以看到test函数只被执行了一次，第二次的调用直接输出了结果，使用了缓存起来的值。

2.当我们使用递归求斐波拉契数列 （斐波那契数列指的是这样一个数列：0,1,1,2,3,5,8，它从第3项开始，每一项都等于前两项之和） 的时候，缓存对性能的提升就尤其明显了：

不使用缓存求第40项的斐波拉契数列

import datetime

def fibonacci(num):
    # 不使用缓存时，会重复执行函数
    return num if num < 2 else fibonacci(num - 1) + fibonacci(num - 2)

start = datetime.datetime.now()
print(fibonacci(40))
end = datetime.datetime.now()
print('执行时间', end - start)

执行时间

执行时间 0:00:29.004424

使用缓存求第40项的斐波拉契数列：

@lru_cache
def fibonacci(num):
    # 不使用缓存时，会重复执行函数
    return num if num < 2 else fibonacci(num - 1) + fibonacci(num - 2)

执行时间

执行时间 0:00:00

两个差距是非常明显的，因为不使用缓存时，相当于要重复执行了很多的函数，而使用了lru_cache则把之前执行的函数结果已经缓存了起来，就不需要再次执行了。

三、lru_cache 用法

1.参数详解

查看lru_cache源码会发现它可以传递两个参数：maxsize、typed：

def lru_cache(maxsize=128, typed=False):
    """Least-recently-used cache decorator.

    If *maxsize* is set to None, the LRU features are disabled and the cache
    can grow without bound.
    ...
    """

1） maxsize
代表被lru_cache装饰的方法最大可缓存的结果数量 （被装饰方法传参不同一样，则结果不一样；如果传参一样则为同一个结果）， 如果不指定传参则默认值为128，表示最多缓存128个返回结果，当达到了128个时，有新的结果要保存时，则会删除最旧的那个结果。如果maxsize传入为None则表示可以缓存无限个结果；

2）typed
默认为false，代表不区分数据类型，如果设置为True，则会区分传参类型进行缓存，官方是这样描述的:

如果typed为True，则将分别缓存不同类型的参数,
例如，f（3.0）和f（3）将被视为具有明显的结果。

但在python3.9.8版本下进行测试，typed为false时，按照官方的测试方法测试得到的还是会被当成不同的结果处理，这个时候typed为false还是为true都会区别缓存，这与官方文档的描述存在差异：

from functools import lru_cache

@lru_cache
def test(a):
    print('函数被调用了...')
    return a

print(test(1.0))
print(test(1))

执行结果

函数被调用了...
1.0
函数被调用了...
1

但如果是多参数的情况下，则会被当成一个结果：

from functools import lru_cache

@lru_cache
def test(a, b):
    print('函数被调用了...')
    return a , b

print(test(1.0, 2.0))
print(test(1, 2))

执行结果

函数被调用了...
(1.0, 2.0)
(1.0, 2.0)

这个时候设置typed为true时，则会区别缓存：

from functools import lru_cache

@lru_cache(typed=True)
def test(a, b):
    print('函数被调用了...')
    return a , b

print(test(1.0, 2.0))
print(test(1, 2))

执行结果

函数被调用了...
(1.0, 2.0)
函数被调用了...
(1, 2)

当传参个数大于1时，才符合官方的说法，不清楚是不是官方举例有误

2. lru_cache不支持可变参数

当传递的参数是dict、list等的可变参数时，lru_cache是不支持的，会报错：

from functools import lru_cache

@lru_cache
def test(a):
    print('函数被执行了...')
    return a

print(test({'a':1}))

报错结果

TypeError: unhashable type: 'dict'

四、lru_cache 与redis的区别