异常重要的一个python装饰器：用于记忆化递归
2020-02-09 本文已影响0人
yousa_
部分转载知乎chenjiandongx回答
import functools
@functools.lru_cache(None)
def fun():
pass
LeetCode刷题的时候，我们发现，很多情况下光用递归是不行的，重复调用了许多次操作。很多情况下程序能跑通，但是经常超时。
这时我们经常提到一种记忆化递归的操作，说白了就是再开辟一个额外空间用来存储之前的值。The Question is有时候构建额外空间还得自己构思一阵子，总之挺麻烦的。
今天在LeetCode解答中看到了一个神级操作，只添加了一个python装饰器，完美地解决了问题。
@functools.lru_cache
@functools.lru_cache(maxsize=128, typed=False)
New in version 3.2.
Changed in version 3.3: Added the typed option.
这个装饰器实现了备忘的功能，是一项优化技术，把耗时的函数的结果保存起来，避免传入相同的参数时重复计算。lru 是（least recently used）的缩写，即最近最少使用原则。表明缓存不会无限制增长，一段时间不用的缓存条目会被扔掉。
这个装饰器支持传入参数，还能有这种操作的？maxsize 是保存最近多少个调用的结果，最好设置为 2 的倍数，默认为 128。如果设置为 None 的话就相当于是 maxsize 为正无穷了。还有一个参数是 type，如果 type 设置为 true，即把不同参数类型得到的结果分开保存，如 f(3) 和 f(3.0) 会被区分开。
写了个函数追踪结果
def track(func):
@functools.wraps(func)
def inner(*args):
result = func(*args)
print("{} --> ({}) --> {} ".format(func.__name__, args[0], result))
return result
return inner
递归函数适合使用这个装饰器，那就拿经典的斐波那契数列来测试吧
不使用缓存
@track
def fib(n):
if n < 2:
return n
return fib(n - 2) + fib(n - 1)
使用缓存
@functools.lru_cache()
@track
def fib_with_cache(n):
if n < 2:
return n
return fib_with_cache(n - 2) + fib_with_cache(n - 1)
测试代码，本电脑的 cpu 是 i5-5200U
fib(10)
759 function calls (407 primitive calls) in 0.007 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.007 0.007 {built-in method builtins.exec}
1 0.000 0.000 0.007 0.007 decorator.py:1(<module>)
177/1 0.000 0.000 0.007 0.007 decorator.py:5(inner)
177/1 0.000 0.000 0.007 0.007 decorator.py:12(fib)
177 0.006 0.000 0.006 0.000 {built-in method builtins.print}
177 0.000 0.000 0.000 0.000 {method 'format' of 'str' objects}
2 0.000 0.000 0.000 0.000 decorator.py:4(track)
3 0.000 0.000 0.000 0.000 functools.py:43(update_wrapper)
1 0.000 0.000 0.000 0.000 functools.py:422(decorating_function)
21 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
15 0.000 0.000 0.000 0.000 {built-in method builtins.setattr}
2 0.000 0.000 0.000 0.000 functools.py:73(wraps)
3 0.000 0.000 0.000 0.000 {method 'update' of 'dict' objects}
1 0.000 0.000 0.000 0.000 functools.py:391(lru_cache)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
# 追踪结果
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
fib --> (1) --> 1
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
fib --> (3) --> 2
fib --> (4) --> 3
fib --> (1) --> 1
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
fib --> (3) --> 2
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
fib --> (1) --> 1
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
fib --> (3) --> 2
fib --> (4) --> 3
fib --> (5) --> 5
fib --> (6) --> 8
fib --> (1) --> 1
fib --> (0) --> 0
fib --> (1) --> 1
fib --> (2) --> 1
往后的省略...
fib(10) 调用了 177 次， 共花费了 0.007 秒
fib_with_cache(10)
95 function calls (75 primitive calls) in 0.002 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.002 0.002 {built-in method builtins.exec}
1 0.000 0.000 0.002 0.002 decorator.py:1(<module>)
11/1 0.000 0.000 0.002 0.002 decorator.py:5(inner)
11/1 0.000 0.000 0.002 0.002 decorator.py:18(fib_with_cache)
11 0.002 0.000 0.002 0.000 {built-in method builtins.print}
2 0.000 0.000 0.000 0.000 decorator.py:4(track)
3 0.000 0.000 0.000 0.000 functools.py:43(update_wrapper)
11 0.000 0.000 0.000 0.000 {method 'format' of 'str' objects}
1 0.000 0.000 0.000 0.000 functools.py:422(decorating_function)
21 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
15 0.000 0.000 0.000 0.000 {built-in method builtins.setattr}
2 0.000 0.000 0.000 0.000 functools.py:73(wraps)
3 0.000 0.000 0.000 0.000 {method 'update' of 'dict' objects}
1 0.000 0.000 0.000 0.000 functools.py:391(lru_cache)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
# 追踪结果
fib_with_cache --> (0) --> 0
fib_with_cache --> (1) --> 1
fib_with_cache --> (2) --> 1
fib_with_cache --> (3) --> 2
fib_with_cache --> (4) --> 3
fib_with_cache --> (5) --> 5
fib_with_cache --> (6) --> 8
fib_with_cache --> (7) --> 13
fib_with_cache --> (8) --> 21
fib_with_cache --> (9) --> 34
fib_with_cache --> (10) --> 55
可以很明显的看到，使用缓存的时候，只调用了 11 次就得出了结果，并且花费时间只为 0.002 秒
我们再把数字调大，传入的参数改为 31
fib(31)
17426519 function calls (8713287 primitive calls) in 168.122 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 168.122 168.122 {built-in method builtins.exec}
1 0.000 0.000 168.122 168.122 decorator.py:1(<module>)
4356617/1 8.046 0.000 168.122 168.122 decorator.py:5(inner)
4356617/1 4.250 0.000 168.122 168.122 decorator.py:12(fib)
4356617 150.176 0.000 150.176 0.000 {built-in method builtins.print}
4356617 5.650 0.000 5.650 0.000 {method 'format' of 'str' objects}
2 0.000 0.000 0.000 0.000 decorator.py:4(track)
3 0.000 0.000 0.000 0.000 functools.py:43(update_wrapper)
1 0.000 0.000 0.000 0.000 functools.py:422(decorating_function)
21 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
15 0.000 0.000 0.000 0.000 {built-in method builtins.setattr}
2 0.000 0.000 0.000 0.000 functools.py:73(wraps)
3 0.000 0.000 0.000 0.000 {method 'update' of 'dict' objects}
1 0.000 0.000 0.000 0.000 functools.py:391(lru_cache)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
调用了 4356617 次，花费 168.122 秒
fib_with_cache(31)
179 function calls (117 primitive calls) in 0.003 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.003 0.003 {built-in method builtins.exec}
1 0.000 0.000 0.003 0.003 decorator.py:1(<module>)
32/1 0.000 0.000 0.003 0.003 decorator.py:5(inner)
32/1 0.000 0.000 0.003 0.003 decorator.py:18(fib_with_cache)
32 0.002 0.000 0.002 0.000 {built-in method builtins.print}
32 0.000 0.000 0.000 0.000 {method 'format' of 'str' objects}
2 0.000 0.000 0.000 0.000 decorator.py:4(track)
3 0.000 0.000 0.000 0.000 functools.py:43(update_wrapper)
1 0.000 0.000 0.000 0.000 functools.py:422(decorating_function)
21 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
15 0.000 0.000 0.000 0.000 {built-in method builtins.setattr}
2 0.000 0.000 0.000 0.000 functools.py:73(wraps)
3 0.000 0.000 0.000 0.000 {method 'update' of 'dict' objects}
1 0.000 0.000 0.000 0.000 functools.py:391(lru_cache)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
仅仅调用了 32 次，花费 0.003 秒...，这...，差别太大了，容我算一算花费时间, 56040 倍！
再往后的我就不加了，我怕明天没有缓存的那个还没算完
这个装饰器还提供 cache_clear() 用于清理缓存，以及 cache_info() 用于查看缓存信息
官方还提供了另外一个例子，用于缓存静态网页的内容
@lru_cache(maxsize=32)
def get_pep(num):
'Retrieve text of a Python Enhancement Proposal'
resource = 'http://www.python.org/dev/peps/pep-%04d/' % num
try:
with urllib.request.urlopen(resource) as s:
return s.read()
except urllib.error.HTTPError:
return 'Not Found'
实际刷题环境下
未使用functools.lru_cache装饰器
使用functools.lru_cache装饰器
差距太大了，所以今后有递归的地方不妨试着把这个装饰器加上优化一下~~
