Bombolom.com : /python/CreateMemoizer-2007-09-11-04-30.html

`(python)` Create Memoizer

Posted by José Lopes

If you are doing a lot of calculations with one specific function, it may be interesting that it remembers the previous results so it may return them once asked gaining considerable computation time.

To do this we can do what is called memoization. This concept has nothing to do with memory in the sense of hardware but with the capacity to recall already calculated results.

First of all lets create a function to execute some calculations.
For academic reasons lets calculate the Fibonacci numbers, that are a sequence starting with 0 and 1, with the next numbers being the sum of the previous two numbers of the sequence itself.

There is no particular reason for choosing this sequence, it's just a good example to show this method potencial.

Writing the function to give us the n order fibonacci number:

def fibonacci(n):
    if n < 2:
      return n
    else:
      return fibonacci(n-1) + fibonacci(n-2)

Now let's write the memoizer. I define it with a class in order to be generic, so you may use it anywhere.

class memo:

    def __init__ (self, f):
      self.result = {}
      self.f = f

    def __call__ (self, *args):
      if not self.result.has_key(args):
        self.result[args] = self.f(*args)
      return self.result[args]

As you can see on the code, this class will store the results on a dictionay.
When a calculation is asked it checks first if the dictionary has already the result:
- if it exists it returns the value and taking virtually zero seconds - if not it calculates, returns the value and stores it on the dictionary

To see all this in action I'll make use of a temporizer, like the one described on the post Checking a function execution time, and so we have the function timer.

test = memo(fibonacci)
   timer (fibonacci, 50)
   timer (fibonacci, 50)

The first timer will calculate the fibonacci number while the second just returns it since its already calculated.
Please note that if you what to calculate for n=30, as the next call, the number doesn't exist in the memoizer so it will be calculated.

Nevertheless we can do the following magic:

fibonacci = memo(fibonacci)
   timer (fibonacci, 50)
   timer (fibonacci, 50)

The first timer will be much more faster that the one in the first case, while the second timer is even faster.

The explanation for this is that the fibonacci function stops being a normal recursive function, using the same principle but making use of the class memo cash, so that to return the n order value it will store the lower order values only once.
We stop having an exponential algorithm to have a n order algorithm.
For the second timer the value already exists so its returned in a lesser time and if we ask for the n=49 it also exists.

Well I was a bit naughty when I choose the Fibonacci numbers, because this magic that I described only works with recursive functions.

As you can see this is very powerful and spares you a lot of computation time.

2007.09.11 | There's more... | Comments 0 | Tags python, memoizer

(python) Create Memoizer

`(python)` Create Memoizer