Speeding up code with memoization

Hey guys! I got a tutorial for you. A while back, @xxpertHacker made a tutorial on memoization, and since I'm doing a bunch of practice on competitive coding, I thought it would be an interesting topic to learn, so I learned the basics of it.

Memoization is a way of doing things that is most helpful in recursive functions, as it can save time and space. It's basically storing previous results of the function so they don't have to be calculated again.

To understand this, we must first look at some code without memorization. Let's use the classic recursive Fibonacci sequence as an example:


int fib(int num)
{
	if (num <= 1)
		return num;

	return fib(num - 1) + fib(num - 2);
}

printf("%d", fib(10));

That's a pretty simple recursive function that prints out the nth number of the fibonacci sequence.

For example:


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

fib(5) --> 5
fib(7) --> 13
fib(10) --> 55

For anyone new to this, here's a diagram I found of how it works:

Pretty simple stuff. But how fast is it? Well, let's try fib(15), and we'll also print out all the numbers that get passed into the fib() function, so our function now looks like this:


int fib(int num)
{
    printf("%d ", num);

    if (num <= 1)
        return num;

    return fib(num - 1) + fib(num - 2);
}

Okay, let's try fib(15). It should equal 610, and if everything's correct, you should see 610 as the last number in the console. Okay, here we go:

without_memo

WOW, that's a lot for a small number!! What's happening here?

Take a look at this diagram:

Notice the red parts. All those, and all those numbers below it are all duplicates! So we're wasting a lot of time recalculating duplicates.

This is where memoization comes in.

Remember, memoization is saving the result of a function call so we don't have to calculate it again. We could potentially store a result in a map, and every time we call a function, we could check if that value has been calculated before. Maybe something like this:


map<int, int> storedNums;

function fib(int num):
	if 'num' is in 'storedNums':
		return 'storedNums[num]'

	if 'num' is less than '0':
		return 'num'

	caclculate the result of 'fib(num - 1) + fib(num - 2)'
	store that value in 'storedNums'
	return that value

And in code:


#include <stdio.h>
#include <map>

// map container to store 'num', and the fib result
std::map<int, int> storedNums;

int fib(int num)
{
	printf("%d ", num);

	// if 'num' has already been calculated, return that result
	if (storedNums.find(num) != storedNums.end())
		return storedNums[num];

	if (num <= 1)
		return num;

  // otherwise, store the result of 'num'
  storedNums[num] = fib(num - 1) + fib(num - 2);
  return storedNums[num];
}

Okay, let's try it out! Remember, using plain old recursion, we get this result for fib(15):

without_memo

And now, if we use this memoization on fib(15), we get:

with_memo

Old fashion recursion's a joke! I like @xxpertHacker's quote on this:

I then laughed at the speed differences

You can try out the below program to see some more differences between standard recursion, and memoization.

And for a more technical difference, let's take a look at the time complexity for each algorithm. So to calculate time complexity for recursive functions, there's actually a really easy formula that you can use. It's called Stack Overflow:


bigger the number, the slower it is
Normal Recursion: O(2^N)  2 4 8 16 32 64 128
Memoization:      O(N)    1 2 3 4  5  6  7

Any questions? Leave them down below!

Next tutorial I make might be about dynamic ~~squids~~ programming.

Hope you learned something :)

Voters

Speeding up code with memoization

Comments