CODEWITHSUNDEEP
python
Joni
Joni

Reputation: 215

Memoization In Python

I'd really love your help with understanding this using of Memoization in Python. I'm new to Python and I'm not quiet sure how to understand this syntax.

def fib_mem(n):
    return fib_mem_helper(n,[0,1]+[-1]*(n-1))

def fib_mem_helper(i,mem):
    if mem[i] == -1:
        mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem)
        return mem[i]

This is a code I saw for avaluating fibonacci number using memoization, what does [0,1]+[-1]*(n-1) mean? Can you please explain me what does this type of writing represent?

Upvotes: 0

Views: 606

Answers (6)

Stefan Gruenwald
Stefan Gruenwald

Reputation: 2640

The speed-up in python can be a million fold or more, when using memoization on certain functions. Here is an example with the fibonacci series. The conventional recursive way is like this and takes forever.

def recursive_fibonacci(number):
    if number==0 or number==1:
        return 1
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2)

print recursive_fibonacci(50),

The same algorithm with memoization takes a few milli seconds. Try it yourself!

def memoize(f):
    memo={}
    def helper(x):
        if x not in memo:
            memo[x]=f(x)
        return memo[x]
    return helper

@memoize
def recursive_fibonacci(number):
    if number==0 or number==1:
        return 1
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2)

print recursive_fibonacci(50),

Upvotes: 0

Hui Zheng
Hui Zheng

Reputation: 10222

First, I have to say that even after editing, your code still has a wrong indentation: return mem[i] should be unindented.

Among list operations, "+" means concatenation, "*" means repetition, so [0,1]+[-1]*(n-1) means a list: [0, 1, -1, ..., -1](totally (n-1) negative 1's).

More explanation:

List [0, 1, -1, ..., -1] stores calculated fibonacci sequences(memoization). Initially it only contains two valid values: 0 and 1, all "-1" elements mean the sequence at that index has not been computed yet. This memo is passed as the 2nd parameter to function fib_mem_helper. If the specified index(i.e. i)'s fibonacci number hasn't been computed(test if mem[i] == -1), fib_mem_helper will recursively compute it and store it to mem[i]. If it's been computed, just return from the memo without recomputing.

That's the whole story.

Final word:

This code is not efficient enough, although it takes use of memoization. In fact, it creates a new list each time when fib_mem is called. For example, if you call fib_mem(8) twice, the second call still has to recreate a list and recompute everything afresh. The reason is that you store the memo inside the scope of fib_mem. To fix it, you could save memo as a dictionary that's outside fib_mem.

Upvotes: 0

siddharthlatest
siddharthlatest

Reputation: 2257

Memoization is a technique to avoid re-computing the same problem. I will come back to your question but here is an easier to understand solution.

mem = {0:0, 1:1}

def fib(n):
    global mem
    if mem.get(n,-1) == -1:
        mem[n] = fib(n-1) + fib(n-2)
    return mem[n]

By making mem a global variable, you can take advantage of memoization across calls to fib(). The line mem.get(n,-1) == -1 checks if mem already contains the computation for n. If so, it returns the result mem[n]. Otherwise, it makes recursive calls to fib() to compute fib(n) and stores this in mem[n].

Let's walk through your code. The second argument here fib_mem_helper(n,[0,1]+[-1]*(n-1)) passes a list of the form [0,1,-1,-1,...] with a length of (n+1). Within the fib_mem_helper function, this list is referenced by variable mem. If mem[i] turns out be -1, you compute m[i]; otherwise use the already computed result for mem[i]. Since you are not persisting mem across the calls to fib_mem(), it would run an order of magnitude slower.

Upvotes: 0

Anil
Anil

Reputation: 588

[-1]*5 will create a new list with five elements being -1,i.e [-1 -1 -1 -1 -1]

[0 1]+[-1]*5 will append the two lists becoming [0 1 -1 -1 -1 -1 -1]

Upvotes: 1

user1887276
user1887276

Reputation:

Strange coding, though. Looks like syntax errors. But according to your question:

[0,1] is a list with two elements, the first is an integer 0 and the second one is an integer 1.

A sensible implementation of such a function with memoization in Python would be:

def fib(i):
    try:
        return fib._memory[i]
    except KeyError:
        pass
    if i == 1 or i == 2:
        return 1
    else:
        f = fib(i-1) + fib(i-2)
        fib._memory[i] = f
        return f
fib._memory = {}

Upvotes: 0

Pavel Anossov
Pavel Anossov

Reputation: 62948

[0, 1] + [-1] * (n - 1) means "concatenate two lists, one is [0, 1], the other one is a -1 repeated n-1 times".

Upvotes: 1

Related Questions