我不明白为什么以下代码使得
例如,
我的理解是
fib
函数的运行时间是线性,而不是指数级。def memoize(obj):
"""Memoization decorator from PythonDecoratorLibrary. Ignores
**kwargs"""
cache = obj.cache = {}
@functools.wraps(obj)
def memoizer(*args, **kwargs):
if args not in cache:
cache[args] = obj(*args, **kwargs)
return cache[args]
return memoizer
@memoize
def fib(n):
return n if n in (0, 1) else fib(n-1) + fib(n-2)
例如,
fib(100)
并没有像我预期的那样完全崩溃。我的理解是
@memoize
设置了fib=memoize(fib)
。因此,当您调用fib(100)
时,会发现100
不在缓存中,它将在100
上调用obj
。但是obj
是原始的fib
函数,所以它是否需要像没有记忆化一样花费同样长的时间(第一次评估)?