异常重要的一个python装饰器：用于记忆化递归

作者: yousa_ | 来源:发表于2020-02-09 21:14 被阅读0次

异常重要的一个python装饰器：用于记忆化递归
python3 尾递归优化装饰器
Flask 视图和路由的进阶技能
Python ☞ day 5
理解装饰器的各种执行细节
Python :生成器、迭代器、装饰器、递归函数与正则表达式
装饰器
Python 装饰器执行顺序迷思
python装饰器的使用（详细解析）
Tenacity——Exception Retry 从此无比简单

部分转载知乎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装饰器

差距太大了，所以今后有递归的地方不妨试着把这个装饰器加上优化一下~~

异常重要的一个python装饰器：用于记忆化递归
部分转载知乎chenjiandongx回答 LeetCode刷题的时候，我们发现，很多情况下光用递归是不行的，重复...
python3 尾递归优化装饰器
python3中没有进行尾递归优化，但是我们可以实现通过一个装饰器实现尾递归优化。网上常见的尾递归装饰器是基于P...
Flask 视图和路由的进阶技能
视图装饰器 Python 装饰器是用于转换其它函数的函数。当一个装饰的函数被调用的时候，装饰器也会被调用。接着装饰...
Python ☞ day 5
Python学习笔记之装饰器& 偏函数 & 异常处理 & 断言 & 文件读写 &编码与解码装饰器概念：是一个...
理解装饰器的各种执行细节
当装饰器遇上尾递归函数如果一个尾递归函数套用了装饰器，那么当一次递归发生后，是尾递归内部的代码先执行，还是装饰器...
Python :生成器、迭代器、装饰器、递归函数与正则表达式
Python 第四篇:生成器、迭代器、装饰器、递归函数与正则表达式 Python迭代器和生成器 Python 迭代...
装饰器
装饰器是python提供的一个重要特性,使用装饰器,可以允许修改其他函数功能. 什么是装饰器上边已经提到,装饰器...
Python 装饰器执行顺序迷思
探究多个装饰器执行顺序装饰器是Python用于封装...
python装饰器的使用（详细解析）
什么是装饰器？ python装饰器（fuctional decorators）就是用于拓展原来函数功能的一种函数，...
Tenacity——Exception Retry 从此无比简单
Python 装饰器装饰类中的方法这篇文章，使用了装饰器来捕获代码异常。这种方式可以让代码变得更加简洁和Pytho...