# Memoization in short

Originally posted on dev.

### python-journey (3 Part Series)

What problem does memoization solve?
In a nutshell, it prevents ineffectiveness.

## Why

The code is not as brilliant as you might think. Sometimes, it needs to repeat stuff over and over to do its job.

The great idea with memoization is to avoid unnecessary calculations. The program has already done the job, so let’s save the results. Instead of computing the same things in memory repeatedly, you store them for later use.

It’s the very concept of caching. If your script needs previous operations results in the next operations, it’s the right candidate for memoization.

## Pure functions and disclaimer

You need pure functions to apply memoization techniques. Those functions don’t manipulate any state, and they have no side effects. They always return the same results for the same inputs, nothing more.

It’s important to note that not all functions must be pure. There are some cases where memoization is even counterproductive.

## Simple pattern

Here is a very simple example in JavaScript :

``````const myFunction = function(param) {
if (!myFunction.memo[ param ]) {
myFunction.memo[ param ] = outcome;
}
return myFunction.memo[ param ];
};

myfunction.memo = {};
``````

The code skips computation if the result is already available.

## Recursion

Recursion is a little more complicated, but it can leverage the benefits of memoization techniques.

As you may already know, recursive functions call themselves. They usually have a condition that ends the recursion in a specific case. The recursive part happens in all other cases.

Here is an example in Python:

``````def fibo(n):
if n <= 1:
return n
else:
return fibo(n - 1) + fibo(n - 2)
``````

The calculation is expensive. It happens because it executes several operations multiple times.

Why is that so?

`fibo(2)` executes `fibo(1)``fibo(3)` executes `fibo(2)` and `fibo(1)`, but `fibo(2)` executes `fibo(1)` too, etc.
In those conditions `fibo(2000)` is gonna take like forever…

Let’s cache it :

``````fiboCache = {}

def fibo(n):
if n in fiboCache:
return fiboCache[ n ]
if n < 2:
value = 1
else:
value =  fibo(n - 1) + fibo(n - 2)
fiboCache[ n ] = value
return value
``````

We use a dictionary to store values. This optimization is massive. Without it, the script would take a lot of time and memory to execute. It would probably kill memory unless you use tiny numbers as input, but in this case, using a function has very little interest.

You can test the boosted `fibo` with a crazy range:

``````for i in range(1, 2000):
print(fibo(i))
``````

## Wrap

I hope you enjoy this short introduction to memoization. It’s available in the vast majority of languages, so do not hesitate to use it appropriately.

Source: dev

Share :