Speeding up code with memoization

Learn to Code via Tutorials on Repl.it!

Speeding up code with memoization

I was debating whether I should've named this:

"When you're a level 99 speed demon"

"Speeding up code with memoization"

Like the latter is more interesting, but I don't want too be too silly with this :)

Anyway (is it 'anyways' or 'anyway'? does anyone care?),

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:

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

Take a look at this diagram:

https://java2blog.com/wp-content/uploads/2018/08/FibonacciMemoizationExample.jpg

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

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

me when I got rid of my report card letter before my parents could look at it: I am S P E E D

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

4 more...

Comments

hot new top

I never knew a squid had such a big brain.

@ThisUserTaken lol thanks!

I should give you more attention

@RohilPatel oh thank you!!

Why would you use std::map<int, int> instead of std::unordered_map or even, dare I say it... a std::vector<int>, or even int(&)[], or even int*.
But seriously std::map<int, int> is as good as an array, just with a whole lot of overhead, and heap-allocated.

@xxpertHacker Well, yeah i guess you have a point. I guess I only used map since it's like the "standard" key-value container.

@xxpertHacker Also I wanted a key-value container

@DynamicSquid Any reason in particular? Index an array with a number, get a number out. Same thing with a map.

@xxpertHacker yeah true I guess, but what about if your keys are: 1 2 7 9, you'd still have to create an array of 9 elements, but only use 4

@DynamicSquid Well... you wait for the user to input the rest?

@StudentFires Ah! Name change I see...

@firefish Whoa, we don't talk about that... lol, but yeah, changed everything.

@DynamicSquid

if your keys are: 1 2 7 9, you'd still have to create an array of 9 elements, but only use 4

super late, but I just saw this post was featured in the monthly repls, (yeah, I'm behind on Repl).

int squareMap[] = {
    [1] = 1,
    [2] = 4,
    [7] = 49,
    [9] = 81
};

Almost a map.

@xxpertHacker wait that syntax is a allowed in C++?

@DynamicSquid Bet you wanna ditch C++ even more now, huh? Way too much to learn; eventually, you'll encounter C++ that you can't even recognize, but it'll compie just fine.

@xxpertHacker yeah I'm really starting to not like C++

@jakman should I learn rust?

@DynamicSquid yep, I started, just repl.it doesn't have a lot of crates, so you'd probably be needing cargo installed locally before you can do much

@DynamicSquid yes. Become one of us.

@Jakman, @firefish I'm starting to not like C++ that much since it's jam packed with features. I'm looking for a language similar to C, like not too many features, and low level. Is rust good for that?

@DynamicSquid Well if you wanna have to do the garbage collecting yourself, go with C, if you want to do it yourself to a lesser extent, go for Rust

@firefish well, I kinda like having to do the garbage collection by myself since I kinda like that control.

@firefish also yeah, I'l doing C right now, but I'm looking for a new langauge

@DynamicSquid C it is. I'd suggest first learning malloc(), calloc(), realloc(), and free(), all of which I've played with, so you can do too...
~~if you want some inspiration here's my ever-growing first program in C: https://www.repl.it/@firefish/myMem~~

@DynamicSquid Uh... The non-existent C+? I don't know

@firefish well no, I already know C, but I want to do something different, but also low level

@firefish ~~I mean I could always do night~~

@DynamicSquid ~~night is basically the revival of csh, not low level at all~~

@firefish ~~idc it's still the best language~~

@DynamicSquid ~~but too high level for your liking, you said you wanted low level.~~

@firefish ~~idc it's still the best language~~

@firefish I should make a compiled lang sometime...

@DynamicSquid ~~At least you're realising that C++ is in fact a pig's breakfast~~

@DynamicSquid By that I hope you mean transpiled to assembler, because machine code is no man's land

@DynamicSquid it is exactly what you want. The best part is that you can do low level C tricks with Java level abstractions

@firefish yeah I heard that before, but it'd be kinda cool to learn

@Jakman oh cool, could you give an example?

@DynamicSquid I'd rather make my own blasted op-codes tbh

~~WAIT! I've always wanted to learn the C# bytecode. (It's similar to the JVM bytecode so there). MSIL always intrigued me~~

@DynamicSquid If you do learn machine code.... try doing some memoisation in it hehe

@firefish lol

@DynamicSquid If you want to know, I did this in MinGW:

dat big exe file, but it works

@firefish ah okay

@DynamicSquid about 900KiB more, I'm switching to Visual Studio's cl

@DynamicSquid

fn main() {
  let this_fib = Fib{0,1};
  println!("{:?}",this.next().unwrap().next());   
}
struct Fib {
    first: usize, // usize is the unsigned integer type
    second:usize
}
impl Iterator for Fib {
    type Item = Fib;
    fn next(&self) -> Option<Self::Item> {
        let new_next = self.first + self.second;
        return Some(Fib{first:self.second,second:new_next});
    }
}

This is a functional Fib in Rust

@DynamicSquid it works: proof:

@DynamicSquid

fn main() {
  let mut this_fib = Fib{first:0,second:1};
  println!("{}",this_fib.next().unwrap().next().unwrap().second);
}
struct Fib {
    first: usize, // usize is the unsigned integer type
    second:usize
}
impl Iterator for Fib {
    type Item = Fib;
    fn next(&mut self) -> Option<Self::Item> {
        let new_next = self.first + self.second;
        return Some(Fib{first:self.second,second:new_next});
    }
}

This one has no errors that other one was just to show concept

@Jakman ah okay, I see. definitely going to take a look at it, thanks!

@DynamicSquid ok cool

@Jakman oh ok

@DynamicSquid If you like control, you might like Facilis in a few months when it has allocation and deallocation built-in, if it doesn't die soon.

ohhh its supposed to be momoization facepalm

@HahaYes yeah, not memor

@DynamicSquid ah ok me dumbo. Also what is mech doing?

@HahaYes Nope, there's a difference: https://en.wikipedia.org/wiki/Memoization.

@xxpertHacker yes I know XD

yay this is #1 on hot!

@HahaYes YOU aren't getting those cycles back, don't spam

erm memoization? hehehe

noice memoziation

@HahaYes Don't spam comments, you're not getting those cycles back

@xxpertHacker okay I just realized that I titled this is exact same title as your tutorial, that wasn't intentional at all lol

@DynamicSquid Umm... copyright, plagiarism, (insert reason why this is illegal here). You even quoted me and linked my ancient post. I know of thousands of hyper optimizations over this. There are some cases in which memoization slows down execution.

I kinda wanna go make a quick C++ memoization wrapper using lambdas and templates now...

@xxpertHacker There, I threw together a quick wrapper for unary functions, I can't think of how to make it work with variardic arguments for this.
https://repl.it/@xxpertHacker/wrapper

@xxpertHacker oh interesting! but what does the [[ no discard ]] do? I think I saw it in your language as well. I've never seen anything like it

@DynamicSquid Ooh, those are just standard C++ attributes, I didn't need it there, more important for stuff that is absolutely critical that is not discarded, like heap-allocated memory, since it would cause a memory leak otherwise.
Better example of their usage: https://repl.it/@xxpertHacker/alloc. I was thinking about using this Repl in Facilis for heap allocation while using a whole different syntax within Facilis itself.

@xxpertHacker ugh, I'm starting to not like C++ since it's jam packed with so many features. like I do prefer C++ over C since templates, classes, namespaces, but, other than that, C++, especially 17 and 20 are just too much. might start learning python ~~or maybe Night~~

@DynamicSquid If you're going to look at anything, I'd highly recommend looking into Rust!
Good luck learning whatever you may choose to actually learn.

(Btw, attributes are C++11, not even 17 or 20)

@xxpertHacker oh wow, earlier than I thought, but yeah, still haven't decided yet

@DynamicSquid or maybe learn golang, It's amazing how easy it is to learn in 5 hours ~~clue to how dusk was made~~