CODEWITHSUNDEEP
pythonalgorithmrecursiondynamic-programmingmemoization
Shivanand THANGALAPALLI
Shivanand THANGALAPALLI

Reputation: 149

memoization not working as expected

I am new to algorithms and so I was experimenting with several possibilities of algorithms, specially memoisation

I have a simple Fibonacci series recursive function using memoisation

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
            print args
        print self.memo
        return self.memo[args]

def fibbo3(n):
    if n==1:
        return 1
    elif n==0:
        return 0
    else:
        return fibbo3(n-1) + fibbo3(n-2)

m = Memoize(fibbo3)

m(4)
print "check the memo"
print m.memo

(4,)
{(4,): 3}
check the memo
{(4,): 3}

But if I call 

fibbo3 = Memoize(fibbo3)
fibbo3(4)
print 'ckeck the memo'
fibbo3.memo

(1,)
{(1,): 1}
(0,)
{(0,): 0, (1,): 1}
(2,)
{(2,): 1, (0,): 0, (1,): 1}
{(2,): 1, (0,): 0, (1,): 1}
(3,)
{(2,): 1, (0,): 0, (3,): 2, (1,): 1}
{(2,): 1, (0,): 0, (3,): 2, (1,): 1}
(4,)
{(2,): 1, (0,): 0, (3,): 2, (1,): 1, (4,): 3}
ckeck the memo
Out[524]:
{(0,): 0, (1,): 1, (2,): 1, (3,): 2, (4,): 3}

I see the entire memoised dictionary. WHy does changing the name of variable from 'm' to 'fibbo3' (i.e the name of the function) results in such a behavior

Upvotes: 4

Views: 443

Answers (1)

jq170727
jq170727

Reputation: 14645

The reason is m = Memoize(fibbo3) does not affect the recursive references to fibbo3 made from fibbo3 whereas fibbo3 = Memoize(fibbo3) does.

You might also want to consider using one of the memoizing decorators in the Python Decorator Library.

Upvotes: 4

Related Questions