Python Memoization Manual Caching

Question

I was building a manual cache version of a memoized Python Fibonacci function and I noticed I did not pass the cache as an argument in the recursive calls.

However, the function still works in the sense that it is much faster than a non-memoized version.

When I added the cache as a function argument, the algorithm was faster, but not significantly so.

Can someone please help me to understand why the first version works at all, and if/whether the second version is more correct?

import time


def fib_cache(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache(n - 1) + fib_cache(n - 2)
    cache[n] = result
    return result


def fib_cache2(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache2(n - 1, cache) + fib_cache2(n - 2, cache)
    cache[n] = result
    return result

start = time.perf_counter()
fib_cache(30)
end = time.perf_counter()
print("Version 1. Seconds taken: {:.5f}".format(end - start))

start = time.perf_counter()
fib_cache2(30)
end = time.perf_counter()
print("Version 2. Seconds taken: {:.5f}".format(end - start))

Does this answer your question? ["Least Astonishment" and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) — jasonharper, Nov 09 '20 at 13:20

score 1 · Accepted Answer · answered Nov 09 '20 at 13:22

This is because def in Python is executed only once and the default variables are intialized only once. In case of reference types this can lead to bugs/unexpected behaviour. One workaround is:

def fib_cache3(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache3(n - 1, cache) + fib_cache3(n - 2, cache)
    cache[n] = result
    return result

The advantage of this version is that it doesn't depend on the default initialization of reference type, and it allows garbage collections once the function is executed.

This is very helpful. It would be even more helpful to have an explanation as to how all 3 versions behave differently. — Robin Andrews, Nov 11 '20 at 13:08

Python Memoization Manual Caching

1 Answers1