222-547523-[专业选修]递归的优化_lru_cache.sy.md

show	version	enable_checker
step	1.0	true

嵌套调用

回忆

• 上次研究了计时函数timeit.timeit()
  • 可以把一段代码的文本作为参数传进来
  • 然后重复执行number次
  • 把这个时间记录下来
  • 这样就可以比较递归和循环的运行时间
• 实践出真知
• 得出哪个函数更好
• 或者说得出哪个算法更好
• 很明显是循环比递归快很多
• 关键递归有很多重复的内容
• 我可以把这些重复的部分给优化了么？

优化思路

• 制作一个斐波那契数列的缓存字典

• 如果字典里面有这个数字
  • 就从字典里面出返回值
• 如果字典里没有这个数字
  • 就计算
  • 并把这个名值对加入字典

代码

fibonacci_cache = {}

def fibo_recur_cached(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        value =  fibo_recur_cached(n-1) + fibo_recur_cached(n-2)
        fibonacci_cache[n] = value
        return value

def fibo_get_series(n):
    """Return a list containing the Fibonacci series up to n."""
    i = 0
    result = 0
    l = []
    while result<n :
        l.append(result)
        i += 1
        result = fibo_recur_cached(i)
    return l

fibo_get_series(10000)

修改main.py

• 结果

• 差距被压缩到十以内

可视化

• 由于前面打好了铺垫
• 后面直接从cache里面得到相应的值就好了
• 不过这有点破坏函数的完整性
• 外面还得有一个字典
• 说好的封装性(encapsulation)呢?

lru_cache

新的方式

• 使用@lru_cache作为装饰器(decorator)

from functools import lru_cache

@lru_cache(maxsize = 1000)
def fibo_recur_lru_cached(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        value =  fibo_recur_lru_cached(n-1) + fibo_recur_lru_cached(n-2)
        return value

def fibo_get_series(n):
    """Return a list containing the Fibonacci series up to n."""
    i = 0
    result = 0
    l = []
    while result<n :
        l.append(result)
        i += 1
        result = fibo_recur_lru_cached(i)
    return l

fibo_get_series(10000)

• 这样就真的可以完成封装了
• 我们去测速度

测速

• 差距10以内
• 确实有优化
• 怎么优化的呢？

细节

• 调用函数对象的cache_info()

• 函数被调用38次
• 缓存里面没有的21次
• 最大大小1000
• 当前大小21
• 如何理解lru呢？

cache

• cache指的是缓存

• lru指的是一种缓存(cache)置换策略

• 就是把哪些缓存清空，哪些缓存留着的策略

• 有各种缓存置换算法

  • FIFO（First In, First Out）先進先出算法
  • LFU（Least Frequently Used）最近最不常使用算法
  • LRU（Least Recently Used）最近最少使用算法
  • NMRU（Not Most Recently Used）非最近使用算法

lru

• 在我们这里缓存的是函数运行的结果

• 总穿的衣服放前面
  • 有时会统计穿衣次数
• 不穿的衣服放后面

• 有新衣服的时候
• 最不长穿的衣服被替换出缓存

源码

• 具体实现是在_lru_cache

• 不过这个函数里面怎么还能定义函数呢？
• 这怎么理解呢？
• 我们先去总结一下

总结

• 这次研究了函数的缓存(cache)
  • 有些函数反复运行
  • 如果算法、参数都不变的话
  • 可以直接从缓存中取得运行结果
• 我们用的是functools中的lru_cache
  • lru指的是Least Frequently Used
  • 最不常穿的衣服被新衣服替换掉
• 不过查看源代码我们发现
• 函数里面还可以有函数？？
• 这怎么理解？？🤔
• 我们下次再说👋