什么是缓存机制
缓存是介于应用程序和物理数据源之间,其作用是为了降低应用程序对物理数据源访问的频次,从而提高了应用的运行性能。缓存内的数据是对物理数据源中的数据的复制,应用程序在运行时从缓存读写数据,在特定的时刻或事件会同步缓存和物理数据源的数据。
为什么要用缓存机制
目的就是为了降低数据源访问的频次,提高运行性能,例如在制作斐波那契数列这道算法题,有很多重复的数据,在使用适当的缓存机制,可以直接从缓存当中取,可以加快运行效率,拜托超时的烦恼。
如何运用lru_cache
在 Python的3.2版本中,引入了一个非常优雅的缓存机器,即 functool
模块中的 lru_cache
装饰器。如果要在 python2 中使用 lru_cahce 需要安装 functools32
。使用方式如下:
import functools
@functools.lru_cache
def fun(MaxSize):
pass
举例
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
代码如下:
import functools
class Solution:
@functools.lru_cache(100)
def climbStairs(self, n: int) -> int:
if n == 1: return 1
if n == 2: return 2
return self.climbStairs(n-1) + self.climbStairs(n-2)