Skip to content
← Back to Community
Speeding up code with memoization
Profile icon
h
has Hacker Plan
DynamicSquid

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:

image

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:

image

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
Profile icon
programmeruser
Profile icon
CodingGoose
Profile icon
WalkerFinlay1
Profile icon
wjnb
Profile icon
CodingWarrior
Profile icon
mkhoi
Profile icon
Viper2211
Profile icon
firefish
Profile icon
Highwayman
Profile icon
BryamLucas
Comments
hotnewtop
Profile icon
ThisUserTaken

I never knew a squid had such a big brain.

Profile icon
DynamicSquid

@ThisUserTaken lol thanks!

Profile icon
RohilPatel

I should give you more attention

Profile icon
DynamicSquid

@RohilPatel oh thank you!!

Profile icon
xxpertHacker

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.

Profile icon
DynamicSquid

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

Profile icon
DynamicSquid

@xxpertHacker Also I wanted a key-value container

Profile icon
xxpertHacker

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

Profile icon
DynamicSquid

@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

Profile icon
xxpertHacker

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

Profile icon
firefish

@StudentFires Ah! Name change I see...

Profile icon
xxpertHacker

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

Profile icon
xxpertHacker

@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.

Profile icon
DynamicSquid

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

Profile icon
xxpertHacker

@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.

Profile icon
DynamicSquid

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

Profile icon
DynamicSquid

@jakman should I learn rust?

Profile icon
firefish

@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

Profile icon
Jakman

@DynamicSquid yes. Become one of us.

Profile icon
DynamicSquid

@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?

Profile icon
firefish

@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

Profile icon
DynamicSquid

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

Profile icon
DynamicSquid

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

Profile icon
firefish

@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

Profile icon
firefish

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

Profile icon
DynamicSquid

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

Profile icon
DynamicSquid

@firefish I mean I could always do night

Profile icon
firefish

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

Profile icon
DynamicSquid

@firefish idc it's still the best language

Profile icon
firefish

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

Profile icon
DynamicSquid

@firefish idc it's still the best language

Profile icon
DynamicSquid

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

Profile icon
firefish

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

Profile icon
firefish

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

Profile icon
Jakman

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

Profile icon
DynamicSquid

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

Profile icon
DynamicSquid

@Jakman oh cool, could you give an example?

Profile icon
firefish

@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

Profile icon
firefish

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

Profile icon
DynamicSquid
Profile icon
firefish

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

image

dat big exe file, but it works

Profile icon
DynamicSquid

@firefish ah okay

Profile icon
firefish

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

Profile icon
Jakman

@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

Profile icon
firefish

@DynamicSquid it works: proof:
image

Profile icon
Jakman

@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

Profile icon
DynamicSquid

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

Profile icon
Jakman
Profile icon
DynamicSquid

@Jakman oh ok

Profile icon
xxpertHacker

@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.

Profile icon
HahaYes

ohhh its supposed to be momoization * facepalm *

Profile icon
DynamicSquid

@HahaYes yeah, not memor

Profile icon
HahaYes

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

Profile icon
xxpertHacker
Profile icon
HahaYes

@xxpertHacker yes I know XD

Profile icon
HahaYes

yay this is #1 on hot!

Profile icon
firefish

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

Profile icon
HahaYes

erm memoization? hehehe

Profile icon
HahaYes

noice memoziation

Profile icon
firefish

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

Profile icon
DynamicSquid

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

Profile icon
xxpertHacker

@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...

Profile icon
xxpertHacker

@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

Profile icon
DynamicSquid

@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

Profile icon
xxpertHacker

@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.

Profile icon
DynamicSquid

@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

Profile icon
xxpertHacker

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

Profile icon
DynamicSquid

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

Profile icon
firefish

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