python - 结合内存和尾调用优化

Question

我最近了解到一种使用装饰器的强大方法 memoize recursive functions .
“嘿，太棒了，我们来玩玩吧!”

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。 “啊啊啊……”

经过一番搜索我found a 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 失败了。“什么……？”

---

问题:

1. 有没有办法组合这些装饰器？如果是，怎么做？
2. 为什么合并后装饰器似乎在为较小的输入工作？

Answer 1

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

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

所以这个故事的士气是尾调用优化和内存不会混合。

当然，对于这个特定的问题，有一种方法可以用对数步数解决问题(有关更多详细信息，请参阅 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4 的 SICP 练习 1.19)，使得这个问题在这种情况下非常没有实际意义。但这不是这个问题的目的。