最近我学到了使用装饰器的一种强大方式,可以用来实现记忆化递归函数。“嘿,这很棒,让我们试试!”
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
. "啊,太糟糕了.."
经过一番搜索,我找到了一个技巧,似乎解决了这个问题。
"这看起来也很不错!让我们试试它"
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)
好的,我有一种方法可以使用记忆化来加速我的斐波那契函数。我也有一种方法来推动递归限制。但是我无法想出如何同时实现这两个功能。
#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
失败了。
"什么情况?"
问题:
- 有没有办法将这些装饰器组合起来?如果有,如何组合?
- 为什么当组合时,似乎装饰器对较小的输入起作用?