结合memoization和尾调用优化

Question

我最近了解了一种使用装饰器来记忆递归函数的强大方法.
"嘿,这很整洁,让我们玩吧!"

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)

好的,所以我有办法用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失败了. "什么......？"

---

题:

1. 有没有办法组合这些装饰？如果是这样,怎么样？
2. 为什么在组合时看起来装饰器正在为较小的输入工作？

Answer 1

这里有两个问题：第一个问题是，正如 @badcook 指出的那样，memoize 装饰器从技术上将您的函数转换为非尾递归函数。然而， tail_call_optimized 装饰器并不关心这一点。

第二个问题，也是它不起作用的原因，是每次调用 fibb 时，memoize 装饰器都会向堆栈添加一个额外的帧。因此，它不是自己的祖父母，而是更像自己的曾祖父母。您可以修复该检查，但请注意 memoize 装饰器将被有效绕过。

所以这个故事的主旨是尾调用优化和记忆不能混合。

当然，对于这个特定问题，无论如何都有一种以对数步数解决问题的方法（参见 SICP 练习 1.19，网址为：http ://mitpress.mit.edu/sicp/full-text/book/book-ZH -11.html#%_sec_1.2.4了解更多详细信息），在这种情况下使问题变得毫无意义。但这不是这个问题的目的。