Memoization In Python

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

[-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]

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 = {}

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.

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.

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),