Memoization python function

Question

Вот небольшой фрагмент кода, который преобразует каждую функцию в свою версию memoization.

def memoize(f): # Memoize a given function f 
    def memf(*x): 
     if x not in memf.cache: 
      memf.cache[x] = f(*x) 
     return memf.cache[x] 

    memf.cache = {} 
    return memf 

Например, если мы имеем функцию fib следующим которая возвращает n-е число Фибоначчи:

def fib(n): 
    if n < 2: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

Теперь данная функция может быть memoized с помощью

fib = memoize(fib) 

Все в порядке до этого момента, но я не могу понять, что если мы сделаем что-то подобное, вместо:

fib = memoize(fib) 

мы вместо того, чтобы сделать:

fib2 = memoize(fib) 

функцию fib2 isn't a memoize d function of выдумка . When we run fib2 it runs like ordinary fib. Please explain why this memoize function gets applied to say a function f` тогда и только тогда, когда мы используем:

f = memoize(f) 

Код запоминанием берется из 6.00xa MOOC предоставлено edx.org. Это не работает прямо сейчас, поэтому я пришел сюда, чтобы спросить.

Answer 1

Потому что когда fib2 рекурсивно вызывает

return fib(n-1) + fib(n-2) 

, который является оригинальным, не- memoize д версии; вы получаете только выгоду от декоратора при первом вызове fib2, а не во всех рекурсивных звонках на ваниль fib.

Вот что происходит:

1. Когда вы звоните fib2, вы действительно вызывая memf, которые
2. звонки fib в свою очередь, если аргументы не в кэше (так как они не будут первый звонок), затем
3. fib, будучи рекурсивным звонки fib. Это не оформленная версия fib2, поэтому все остальные рекурсивные звонки не являются memoize d.

Если вы звоните fib2 снова с теми же аргументами, что будет быть возвращен из кэша, но вы потеряли большую часть выгоды.

Вы можете создать украшенные функции в общем с помощью:

decorated = decorator(original) 

но ваша функция украшаются является рекурсивный, вы столкнетесь с проблемами.

---

Ниже приведен пример демонстрации. Создайте две идентичные функции fib, fib_dec и fib_undec. Измените декоратора, чтобы сказать вам, что это делает:

def memoize(f): # Memoize a given function f 
    def memf(*x): 
     print("Memoized call.") 
     if x not in memf.cache: 
      print("Filling cache.") 
      memf.cache[x] = f(*x) 
     else: 
      print("Cache retrieve.") 
     return memf.cache[x] 
    memf.cache = {} 
    return memf 

Затем запустите:

fib_dec = memoize(fib_dec) # fully memoized 
fib_undec_1 = memoize(fib_undec) # not fully memoized 

print("Calling fib_dec(2)") 
print(fib_dec(2)) 
print("Calling fib_dec(1)") 
print(fib_dec(1)) 
print("Calling fib_undec_1(2)") 
print(fib_undec_1(2)) 
print("Calling fib_undec_1(1)") 
print(fib_undec_1(1)) 
print("Calling fib_undec_1(2)") 
print(fib_undec_1(2)) 

Это даст:

Calling fib_dec(2) # fully decorated 
Memoized call. 
Filling cache. 
Memoized call. 
Filling cache. 
Memoized call. # recusive calls all memoized 
Filling cache. 
2 
Calling fib_dec(1) 
Memoized call. 
Cache retrieve. # previous recursive result cached 
1 
Calling fib_undec_1(2) # not fully memoized 
Memoized call. # only one memoized call, recursion not memoized 
Filling cache. 
2 
Calling fib_undec_1(1) 
Memoized call. 
Filling cache. # recursive result not cached 
1 
Calling fib_undec_1(2) 
Memoized call. 
Cache retrieve. # but original call is cached 
2