为什么Python的decorator语法比普通包装语法提供更快的记忆化代码？

Question

我一直在试图理解真实世界OCaml（RWO）第8章中关于记忆的部分。我不明白，所以我决定把OCaml代码翻译成Python。这个练习结果很有用，因为（1）我终于理解了RWO的意思，（2）我编写了一些似乎可以工作的更快的Python代码。然而，在编写Python代码时，我尝试了两种不同的方法来执行记忆：一种是对包装函数的普通调用，另一种是使用Python的decorator语法。在

我记下了Fibonacci函数的三种不同方法，并测量了在我的2.9ghz英特尔酷睿i7macbookpro上用8gbram和操作系统10.9.2运行python2.7时，每种方法计算第32个Fibonacci数的时间。这给了我一个令人惊讶的结果：

1. 完全没有记忆：2秒
2. 常规记忆：1s
3. 使用简单语法的RWO风格的相互递归记忆：2s
4. 使用decorator语法的RWO风格的相互递归记忆：0.0001s

我所读到的所有内容都表明decorator语法实际上只是用来表示以下内容的语法糖分：

memoFib = memoize(Fib)

那么为什么4比3快那么多呢？在

from time import time

def unfib(n):
    '''Unmemoized Fibonacci'''
    if n <= 1: return 1
    else: return unfib(n-1) + unfib(n-2)

def memoize(f):
    '''A simple memoization function'''
    hash = {}
    def memo_f(x):
        if not hash.has_key(x):
            res = f(x)
            hash[x] = res
        return hash[x]
    return memo_f

# Simple approach to memorizing Fibonacci (#2 from the list above)
memoFib1 = memoize(unfib)

# Simple approach to timing functions
def timeit(its,f,arg):
    zero = time()
    for i in range(its):
        res = f(arg)
    one = time()
    print res, one - zero

# A non-recursive form of Fibonacci
# that expects the remainder of the 
# function to be passed as an argument.
# Together, they make a pair of mutually
# recursive functions. Real World Ocaml
# refers to this as 'tying the recursive
# knot' (Ch. 8, Imperative programming).
def fib_norec(fib,x):
    if x <= 1: return 1
    else: return fib(x-1) + fib(x-2)

def memo_rec(f_norec):
    '''A memoizing version of make_rec,
    but using the plain wrapper
    syntax of the memoize function'''
    def f(x):
        return f_norec(f,x)
    return memoize(f)

# #3 from list above: memoized using plain call to wrapping function
memoFib2 = memo_rec(fib_norec)

def memo_rec2(f_norec):
    '''A second memoizing version of
    make_rec (from RWO), but using 
    the decorator syntax'''
    @memoize
    def f(x):
        return f_norec(f,x)
    return f

# #4 from list above, memoized using decorator syntax
memoFib3 = memo_rec2(fib_norec)

print 'no memo\t\t\t\t\t',
timeit(2,unfib,32)
print 'basic memo\t\t\t\t',
timeit(2,memoFib1,32)
print 'mutually recursive memo, plain wrapper syntax',
timeit(2,memoFib2,32)
print 'mutually recursive memo, decorator syntax',
timeit(2,memoFib3,32)

Answer 1

def f(x):
    return f_norec(f,x)
return memoize(f)

在这里，返回的函数是memoized生成的函数，但是本地名称f仍然引用上面代码段中定义的非记忆化函数，因此没有任何递归调用从记忆化中受益。调用图如下所示：

^{pr2}$

另一方面

@memoize
def f(x):
    return f_norec(f,x)
return f

本地名称f引用了记忆化的函数，因此可以得到如下调用图：

<memoized f>
  f
    f_norec
      <memoized f>
        f
          f_norec
            <memoized f>
              ...

（看起来好像有更多的电话，而且确实如此。我只在每个级别显示两个递归调用中的第一个，因此您看不到记忆是如何缩短第二个调用的。）

如果您手动编写decorator语法实际上去糖到（f = memoize(f); return f），您将看到相同的行为和性能。在