Dlaczego składnia dekoratora języka Python zapewnia szybszy kod do zapamiętania niż zwykłą składnię opakowania?

Question

Próbuję zrozumieć rozdział poświęcony memoizacji w Rozdziale 8 Real World OCaml (RWO). Nie dostałem tego, więc postanowiłem przetłumaczyć kod OCaml na Python. To ćwiczenie okazało się przydatne, ponieważ (1) w końcu zrozumiałem, co powiedział RWO, i (2) napisałem szybszy kod Pythona, który wydaje się działać. Jednak, pisząc kod Pythona, próbowałem wykonać tę funkcję na dwa różne sposoby: raz używając zwykłego wywołania funkcji owijania i raz używając składni Pythona.

Zapamiętywałem funkcję Fibonacciego na trzy różne sposoby i mierzyłem, ile czasu zajęło obliczenie 32. liczby Fibonacciego dwa razy na moim komputerze Macintosh Intel Core i7 2,9 GHz z 8 GB pamięci RAM i systemem OS 10.9.2, z uruchomionym Pythonem 2.7. To dało mi zaskakujący wynik:

1. Nie memoization w ogóle: 2 s
2. Regularne memoization: 1 s
3. RWO-style wzajemnie rekurencyjne memoization użyciu zwykłego składnię: 2 s
4. RWO stylu wzajemnie rekurencyjne memoization użyciu dekorator składni: 0.0001 s

Wszystko Czytałem mówi, że składnia dekorator jest naprawdę po prostu cukier syntaktyczny dla mówiąc:

memoFib = memoize(Fib)

Dlaczego więc numer 4 jest o wiele szybszy niż numer 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) 

Tutaj funkcja zwrócony jest produkowany przez memoized, ale lokalna nazwaf nadal odnosi się do non-memoized funkcji określonej w powyższym fragmencie, stąd żadne z połączeń rekurencyjnych korzyści z pamiętania. Wykres wywołanie wygląda tak:

<memoized f> 
    f 
    f_noref 
     f 
     f_norec 
      ... 

Tutaj drugiej strony,

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

lokalna nazwaf odnosi się do funkcji memoized, więc masz wykres wywołania takiego:

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

(Wygląda na to, że jest więcej połączeń, i to jest. Pokazuję tylko pierwsze z dwóch wywołań rekursywnych na poziom, więc nie widzisz, w jaki sposób zację skraca sekundę).

Jeśli ręcznie napisał, że składnia dekorator faktycznie desugars do (f = memoize(f); return f), to nie zobaczy identycznego zachowania i wydajności.