python - 为什么 Python 的装饰器语法比普通包装器语法提供更快的内存代码？

Question

我一直在努力理解 Real World OCaml (RWO) 第 8 章中关于内存的部分。我不明白，所以我决定将 OCaml 代码翻译成 Python。结果证明这个练习很有用，因为 (1) 我终于理解了 RWO 的意思，并且 (2) 我写了一些看起来可以工作的更快的 Python 代码。然而，在编写 Python 代码时，我尝试以两种不同的方式执行内存:一种是使用对包装函数的普通调用，另一种是使用 Python 的装饰器语法。

我用三种不同的方式内存了斐波那契函数，并测量了在我的 2.9 GHz 英特尔酷睿 i7 MacBook Pro 上，配备 8 GB RAM 和操作系统 10.9.2，运行 Python 2.7，每种方式计算第 32 个斐波那契数两次所花费的时间。这给了我一个令人惊讶的结果:

1. 完全没有内存:2秒
2. 常规内存:1 秒
3. 使用普通语法的 RWO 风格的相互递归内存:2 秒
4. 使用修饰符语法的 RWO 风格相互递归内存:0.0001 秒

我读过的所有内容都说装饰器语法实际上只是语法糖:

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生成的函数，但是local namef仍然指的是定义的非memoized函数在上面的代码片段中，因此没有任何递归调用受益于内存。调用图是这样的:

<memoized f>
  f
    f_noref
      f
        f_norec
          ...

另一方面，

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

本地名称 f 指的是内存函数，所以你会得到这样的调用图:

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

(看起来调用更多，确实如此。我只显示每个级别的两个递归调用中的第一个，所以您看不到内存如何缩短第二个。)

如果您手动编写装饰器语法 实际上 去糖为 (f = memoize(f); return f)，您会看到相同的行为和性能。