2
\$\begingroup\$

This is an algorithm that I wrote to get the nth Fibonacci number using bottom-up dictionary. How can I make this better/more efficient?

memo={1:1,2:1}
f=0

def Fib(n):
    for i in range(3,n+1):
        memo[i]=memo[i-1]+memo[i-2]


    f=memo[n]
    print(f)
    return f


Fib(15)
\$\endgroup\$
2
\$\begingroup\$

Before we come to the actual algorithm: python has an official style-guide, PEP8. It recommends using lower_case for variable and function names (and PascalCase for classes). It also recommends avoiding unnecessary blank lines, which means having exactly two blank lines before a function definition (one if it is a class method) and only a single blank line to separate logical code blocks if necessary. Lastly, you should put a blank after the comma in an argument list or a colon ({1: 1, 2: 1} and not {1:1,2:1})


You should learn about decorators!

In the most simple way you could use it like this:

def memoize(func):
    func.memo = {1: 1, 2: 1}
    return func


@memoize
def Fib(n):
    for i in range(3, n+1):
        Fib.memo[i] = Fib.memo[i-1] + Fib.memo[i-2]
    return Fib.memo[n]

print Fib(15)

This makes a memo object bound to the func.

What you really want, though, is a decorator that silently caches every result, whenever you call your function. As it stands, you are also wasting cycles. If you calculate Fib(15) and after that Fib(16) it would be nice if the code took the already computed values of Fib(14) and Fib(15). Your code calculates all intermediate values for every n, though.

Here are two memoization decorators that can do what you need:

import functools

def memoize(func):
    cache = func.cache = {}

    @functools.wraps(func)
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper


def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class MemoDict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return MemoDict().__getitem__

@memodict
def fib(n):
    if n == 0:
        return 0
    if n in (1, 2):
        return 1
    return fib(n-1) + fib(n-2)

The first decorator is a bit easier to understand, as it does a bit what you started out doing already. It defines a cache for the function and stores the result of the function in the cache if it is not already in there. It returns the value in the cache.

The second is a more optimized and is slightly faster. It only works with single-valued functions (as yours is). It uses the fact that the magic method __missing__ is called for a dict if a requested key does not exist, before raising a KeyError. In this method the cache is populated.

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away (where too big is already somewhere between 250 and 300). Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

for n in xrange(large_number):  # Use range in python 3.x
    fib(n)
print fib(large_number)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.