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

Question

我一直试图理解Real World OCaml(RWO)第8章中关于memoization的部分.我没有得到它,所以我决定将OCaml代码翻译成Python.这个练习结果证明是有用的,因为(1)我终于明白了RWO在说什么,(2)我写了一些似乎有用的更快的Python代码.但是,在编写Python代码时,我试图以两种不同的方式执行memoization:一次使用对包装函数的普通调用,一次使用Python的装饰器语法.

我用三种不同的方式记住了Fibonacci函数,并测量了我的2.9 GHz Intel核心i7 MacBook Pro(8 GB RAM和OS 10.9.2,运行Python 2.7)两次计算第32个Fibonacci数的时间.这给了我一个惊人的结果:

1. 完全没有记忆:2秒
2. 定期记忆:1秒
3. 使用普通语法的RWO样式的相互递归memoization:2秒
4. 使用装饰器语法的RWO风格的相互递归memoization:0.0001 s

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

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仍然引用上面片段中定义的非memoized函数,因此没有一个递归调用受益于memoization.调用图如下:

<memoized f>
  f
    f_noref
      f
        f_norec
          ...

另一方面,

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

在本地名称 f是指memoized功能,让您得到调用关系图如下:

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

(它看起来像更多的调用,它是.我只显示每个级别的两个递归调用中的第一个,所以你不会看到memoization如何缩短第二个.)

如果您手动写入装饰器语法实际上是 desugars to(f = memoize(f); return f),您会看到相同的行为和性能.