CODEWITHSUNDEEP
pythondictionaryfibonaccimemoization
S.A.
S.A.

Reputation: 2151

Memos in python (Think Python exercise 11.6)

In the Think Python book Chapter 11, Allen Downey mentions that "... a previously computed value that is stored for later use is called a memo" (p. 107).

The following function is then re-written to improve it by using memos:

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

The re-written function looks like the following:

known = {0: 0, 1: 1}

def memoized_fibonacci(n):
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

I am wondering, why it is necessary to add the recursion call (here: 'res') to the dictionary (memo) before returning it.

If I print the dictionary after any call of fibonacci, the dictionary just contains the information that has been there before (0:0, 1:1) as well as the information for n:

>> memoized_fibonacci(7)
>> print known
>> {0: 0, 1: 1, 7: 13}

so no intermediate results are being saved that could be helpful to save time (memo). Using the time module, I furthermore can only gain a minimum time advantage of the memoized_fibonacci function over the simpler fibonacci function. (I.e. for memoized_fibonacci(40) I take 58.1 seconds and for fibonacci(40) I take 58.8 seconds)

Deleting the known[n] = res call does not slow the memoized function down either.

known = {0: 0, 1: 1}

def memoized_fibonacci(n):
    if n in known:
        return known[n]
    return fibonacci(n-1) + fibonacci(n-2)    # Not slower!

Am I missing the point here? Could somebody explain to me, why calling known[n] = res is important? Thanks!

Upvotes: 2

Views: 2364

Answers (2)

user1514631
user1514631

Reputation: 1222

known[res] = n

is needed otherwise you wont store the result in "known" and you will need to recalculate all the elements of the progression every time.

If you start with known = {0:0, 1:1}, after fibonacci(29) known will be populated with: 

{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229}

Then moving to fibonacci(30) is almost instantaneous because both fibonacci(29) and fibonacci(28) are in known.

Upvotes: 1

jonrsharpe
jonrsharpe

Reputation: 122136

You have made a typo. The code from the book is:

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)  # note same name
    known[n] = res
    return res

If you rename the function (to memoized_fibonacci) you need to change the recursive calls, too. Otherwise the memoized version is calling the un-memoized version, and you don't get any benefit.

Upvotes: 4

Related Questions