我最近了解了一种使用装饰器来记忆递归函数的强大方法。
“嘿嘿，好巧，我们一起玩吧！”
class memoize:
"""Speeds up a recursive function"""
def __init__(self, function):
self.function = function
self.memoized = {}
def __call__(self, *args):
try:
return self.memoized[args]
except KeyError:
self.memoized[args] = self.function(*args)
return self.memoized[args]
#fibmemo
@memoize
def fibm(n, current=0, next=1):
if n == 0:
return current
else:
return fibm(n - 1, next, current+next)
这timeit表明这确实加速了算法：
fibmemo 0.000868436280412
fibnorm 0.0244713692225
“哇，那真的很有用！不知道我能推多远？”
我发现当我开始使用高于 140 的输入时，我很快就遇到了RuntimeError: maximum recursion depth exceeded. “啊呸呸呸。”
经过一番搜索，我发现了一个似乎可以解决问题的 hack 。
“这看起来也很整洁！让我们一起玩吧”
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such exceptions to fake the tail call optimization.
This function fails if the decorated function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
#fibtail
@tail_call_optimized
def fibt(n, current=0, next=1):
if n == 0:
return current
else:
return fibt(n - 1, next, current+next)
好的，所以我有一种方法可以使用 memoize 来加速我的斐波那契函数。我有办法推动递归限制。我无法弄清楚如何做到这两点。
#fibboth
@memoize
@tail_call_optimized
def fibb(n, current=0, next=1):
if n == 0:
return current
else:
return fibb(n - 1, next, current+next)
fibboth 0.00103717311766
fibtail 0.274269805675
fibmemo 0.000844891605448
fibnorm 0.0242854266612
我已经尝试结合看起来像它适用于低于 140 的输入的装饰器，但是当我超出这个范围时，RuntimeError: maximum recursion depth exceeded就会发生。这几乎就像@tail_call_optimized失败一样。
“什么……？”
问题：
- 有没有办法组合这些装饰器？如果是这样，怎么做？
- 为什么结合起来看起来装饰器正在为较小的输入工作？