The world’s leading publication for data science, AI, and ML professionals.

Memoization in Python: The Essence of Dynamic Programming

Explained with fibonacci numbers

Photo by Samsung Memory on Unsplash
Photo by Samsung Memory on Unsplash

Dynamic programming is a method developed by Richard Bellman in 1950s. The main idea behind the dynamic programming is to break a complicated problem into smaller sub-problems in a recursive manner.

In computer science and programming, the dynamic programming method is used to solve some optimization problems.

The dynamic programming is a general concept and not special to a particular programming language. But, we will do the examples in Python.

An optimization problem is maximizing or minimizing a cost function given some constraints. There are many different kinds of algorithms that are designed to solve optimization problems. For instance, gradient descent algorithm is used to find a local minimum of a differentiable function. It is widely-used in Machine Learning and deep learning.

Dynamic programming is applicable if an optimization problem has:

  • Optimal substructure. It means we should be able break up the problem into smaller sub-problems. The small problems are solved independently of each other and then combined to solve the bigger problem.
  • Overlapping sub-problems. It means some of the sub-problems are repeated multiple times. One of the strengths of dynamic Programming comes from storing the results of the repetitive smaller problems.

The optimal substructure and overlapping sub-problems will be more clear when we do the examples on calculating fibonacci numbers.

Fibonacci numbers form a sequence in which each number is the sum of the two preceding numbers.

  • Fib(0) is 0 and Fib(1) is 1. For n > 1, Fib(n) = F(n-1) + F(n-2)

The following figure shows how to break up the calculation of Fib(5) into smaller problems.

Breaking up Fib(5) (image by author)
Breaking up Fib(5) (image by author)

As you can see in the figure, even in the calculation of a small fibonacci number, we have many repeating elements. For instance, Fib(2) is calculated three times.

The following Python function breaks up the problem of calculating fibonacci numbers into smaller problems. Then, it does the calculation by following a bottom up approach.

Function to calculate fibonacci numbers (image by author)
Function to calculate fibonacci numbers (image by author)

Zero and one are the base cases. For any value of n greater than 1, the task of calculation fib(n) is divided into two parts, fib(n-1) and fib(n-2). After we reach fib(1) or fib(0), the called functions starts to return values to the previous function call. Eventually, we reach back to the top. Thus, this is a recursive function.

This function is compatible with the optimal substructure condition of dynamic programming. However, it is not done yet because we are not taking advantage of overlapping sub-problems.

Let’s implement another function that stores the result of calculations so that the repeating calculations are only done once. Storing the results of the calculations of sub-problems is known as memoization. We will then run experiments to compare the performance of these two functions with respect to time.

Another function to calculate fibonacci numbers (image by author)
Another function to calculate fibonacci numbers (image by author)

I called it memoFib because it saves the result of calculations in memory.

In addition to n, the function takes an empty dictionary as argument. Before doing any calculation, it checks if the result of that calculation is already in the dictionary. If not, the function performs the calculation and stores the result in the dictionary.

We are now taking advantage of the overlapping sub-problems.

Let’s run some tests to compare fib and memoFib functions. The time difference will be quite small with small fibonacci numbers.

fib(10) vs memoFib(10) (image by author)
fib(10) vs memoFib(10) (image by author)

The difference is 20 microseconds for fib(10) which is negligible.

fib(25) vs memoFib(25) (image by author)
fib(25) vs memoFib(25) (image by author)

Fib(25) is on milisecond level whereas memoFib(25) still takes microseconds to compute. Let’s try 40 now.

fib(40) vs memoFib(40) (image by author)
fib(40) vs memoFib(40) (image by author)

There is a significant difference now. Fib(40) takes 40 seconds to compute. On the other hand, memoFib(40) is still on microsecond level.

I don’t want to try bigger numbers because the waiting period will be exhaustive.


Conclusion

What we have done with storing the results is called memoization. We are basically trading time for space (memory). However, space is negligible compared to the time saved by memoization.

Dynamic programming is adapted in solving many optimization problems. However, not all optimization problems can be improved by dynamic programming method. As we also discussed earlier, there are two conditions to be met:

  • Optimal substructure
  • Overlapping sub-problems

Thank you for reading. Please let me know if you have any feedback.


Related Articles