Memoization python function

Question

Here's a little piece of code which converts every function to its memoization version.

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

For instance, if we have a function fib as follows which returns the nth Fibonacci number:

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

Now, the above function can be memoized by using

fib = memoize(fib)

Everything is fine up to this point but what I can't understand is that if we do something like this, instead of:

fib = memoize(fib)

we instead do:

fib2 = memoize(fib)

the function fib2 isn't a memoized function of fib. When we run fib2 it runs like ordinary fib. Please explain why this memoize function gets applied to say a function f if and only if we use:

f = memoize(f)

The memoization code is taken from 6.00x a MOOC provided by edx.org. It's not running right now that's why I have come here to ask.

This question is relevant: stackoverflow.com/questions/20909200/… — jonrsharpe
– jonrsharpe, Commented Apr 18, 2014 at 10:33

jonrsharpe · Accepted Answer · 2014-04-18 10:54:57Z

6

Because when fib2 recursively calls

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

that is the original, un-memoized version; you only get the benefit of the decorator on the first call to fib2, not all the recursive calls to vanilla fib.

Here's what happens:

When you call fib2, you are really calling memf, which
calls fib in turn if the arguments aren't in the cache (as they won't be on the first call), then
fib, being recursive calls fib. This is not the decorated version fib2, so all of the rest of the recursive calls aren't being memoized.

If you call fib2 again with the same arguments, that will be returned from the cache, but you have lost most of the benefit.

You can create decorated functions in general using:

decorated = decorator(original)

but as your function being decorated is recursive, you run into problems.

Below is a demo example. Create two identical fib functions, fib_dec and fib_undec. Modify the decorator to tell you what it's doing:

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

Then run:

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))

This will give:

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

edited Apr 18, 2014 at 10:54

answered Apr 18, 2014 at 10:23

jonrsharpe

123k31 gold badges278 silver badges488 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user3544994 Over a year ago

Could you please elaborate. I couldn't make much sense of it right now.

user3544994 Over a year ago

Thanks for elaborating but its still unclear to me. Suppose we use the correct thing that is fib = memoize(fib) then fib will call fib which will next call fib. In this way they will never make it to the definition that fib = fib(n-1) + fib(n-2) so how will I get my answer?

user3544994 Over a year ago

What I am trying to say is that fib will call memoize(fib) but since fib inside of memoize is indeed fib that's why memoize(fib) will call memoize(fib)(n-1) and memoize(fib)(n-2). This will go on forever and fib definition that when n<= 1 return 1 will never be reached.

jonrsharpe Over a year ago

Yes it will - at some point you will call memoize(fib)(1). The first time that happens, memf will call fib(1) and cache the result (effectively cache.update({1: 1})) after that it will be retrieved from the cache like any other value.

user3544994 Over a year ago

Please explain how the thing works when we use fib = memoize(fib).

|

Collectives™ on Stack Overflow

Memoization python function

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related