Learn to Code via Tutorials on Repl.it!

← Back to all posts
Using Memoization to Speed Up Code

# What is memoization?

Yeah, that's right, memo, not memor. I asked my self this when I first saw it. Simply put, memoization can be described as the caching of the results of a sub-step within an algorithm.

That makes it perfect for recursive functions, as they waste plenty of time recomputing everything, so that's what I tried it on, a recursive function.

And what recursive function is better known than a function to calculate the Fibonacci sequence?

After learning about memoization and how to do it, I spent hours perfecting a memoization wrapper which I then used on a JavaScript bigInt Fibonacci function.

I then laughed at the speed differences.

I calculated 1000 iterations of the Fibonacci sequence in 1 second. Without it, it took forever. You can try any number less than 200,000 without choosing to loop, and you'll receive an answer within 10 seconds, guaranteed or I'll refund you.

Try it out yourself!
https://MemoizedFibonacci.studentfires.repl.run

bgrubert (177)

I put in 199,999 on the memoized option and it's taken longer than a minute - do I get my refund?

[deleted]

@bgrubert With or without the loop option? (I'm an associate of SF)

[deleted]

@bgrubert 200k was an estimate at when it crashes. It crashes on 199,999. But... I guess you deserve a full refund. How much did it cost you to push "Run"? (Now you see our loophole)

bgrubert (177)

@JadenGarcia It costed valuable food to give my finger the energy to press run

[deleted]

@bgrubert How much? How many milligrams? 1, 2?

DynamicSquid (4547)

@bgrubert, Well, according to this, the average "flick" wastes 0.15J of energy. So you burned 0.04 calories. Which means, @JadenGarcia, you owe @bgrubert 1/2375 of an apple xD

bgrubert (177)

@DynamicSquid So if the apple's price was \$.44, @StudentFires would owe me 0.018 cents

xxpertHacker (626)

@bgrubert Yes, as my associate wrote, when the global pandemic is over, we will refund you in full. As of right now, any more runs will no longer be refunded. In order to refund you in full, we need to request that you provide us with the following information: to know where to send your refund: the planet where you're home is located (if applicable), the country (if applicable), the state (if applicable), providence (if applicable), region (if applicable), city / town, (if applicable), street (if applicable), mailbox (if applicable), home address (if applicable), and, preferably, some details about the external part of your house (if applicable) that distinguishes it from any nearby houses (if applicable). If none of the information requested is applicable to your current situation, please provide an address where you would like us to send your refund. And once again, this will only happen if and when the quarantines end, in both, the city that © StudentFires is located, and in the requested delivery area.

xxpertHacker (626)

@DynamicSquid ©StudentFires will be taking full responsibility for refunding @bgrubert. @JadenGarcia is in no way whatsoever involved in the refund guarantee, other than that he is indeed an associate of ©SF.

Also, totally unrelated, but can you give us an upvote on the post?

xxpertHacker (626)

@bgrubert Our email, or what method did you use to inform us?

xxpertHacker (626)

@bgrubert Oh, the upvote! The good folks at StudentFires thank you!

xxpertHacker (626)

@DynamicSquid You're assuming he even eats apples. This may not entirely be true, instead he may eat much more (or less) expensive food, depending on his lifestyle.
It is uncommon for someone to be a vegetarian, much less a vegan, so he may have eaten some expensive steak, or simply a McDonald's burger. He may have eaten a can of beans, he may have sat around eating chips, we cannot simply assume such events occurred (or didn't).

DynamicSquid (4547)

@StudentFires lol, also, why do you unvote your own posts?

xxpertHacker (626)

@DynamicSquid Psychology? You see someone who has 0 votes, don't you want to give them a vote?

DynamicSquid (4547)

@StudentFires Interesting... I've never thought of it that way, you know, I'm going to give it a try and see how it goes. I'll let you know next week if it works

xxpertHacker (626)

@DynamicSquid Where better to start than right now, here?

xxpertHacker (626)

@DynamicSquid See! I just had to give you that upvote!

firefish (886)

@bgrubert Wow, have your 2 cents and leave, keep the change

bgrubert (177)

@firefish It's actually less than 2% of a cent lol

firefish (886)

@bgrubert oh wait... I though he said 0.018 dollars...
then take your cent, keep the change

xxpertHacker (626)

@firefish It's less than half of a cent; we round down :)

firefish (886)

@xxpertHacker Take your air, keep the change.

firefish (886)

@xxpertHacker It's so cheap in the weakest currency in the world as well

xxpertHacker (626)

@firefish I almost want to say that you can't legally own air, but I guess people have canisters of gas, so I guess it is.

Well, at least no one will argue that I need to refund them for the amount of energy it took them to press a button.

bgrubert (177)

@firefish Yeah it's about the price of 1 cup of tap water

firefish (886)

@bgrubert Wow your water is cheap

finlay44111 (77)

what's wrong with something like:

``````int a = 1;
int b = 1;
for (int i = 0; i < 1000; i++)
{
int c = b;
b += a;
a = c;
}``````

that would calculate the 1000th fibonacci number and it would be way faster.

xxpertHacker (626)

@finlay44111 Yeah ik, this practically isn't recursive anymore either. But this is a general wrapper than can be applied to any pure function.

xxpertHacker (626)

@finlay44111 Also, as I told Mr. Economical, this doesn't need to be used on recursive functions, it can be used on any function. It's best to be used on functions that are called often and are very expensive to compute or inefficient at computing.

MrEconomical (2256)

dynamic programming FTW dynamic programming > memoization technically memoization is part of dynamic programming but we can do memory optimizations in bottom-up construction! that part of the tutorial is coming soon btw ^ ^ anyways nice tutorial

xxpertHacker (626)

@MrEconomical So what I'm getting, is that I beat you to it? Also, this isn't even a tutorial yet, really look at it and you'll see I don't explain much.

MrEconomical (2256)

@StudentFires no, I'm writing my tutorial series on dynamic programming as tabulation (a bottom-up construction) and you have written yours on the other method, memoization

xxpertHacker (626)

@MrEconomical As far as I know, they're different words for the same idea with in contexts.

MrEconomical (2256)

@StudentFires not really, because tabulation isn't recursive

xxpertHacker (626)

@MrEconomical What makes this recursive, other than I chose a recursive function? This can be applied to any pure unary function, recursive or not.

MrEconomical (2256)

@StudentFires traditionally, memoization is applied to recursive functions as an optimization by storing previous solutions to not need to calculate them again. however, you can use this in an iterative manner at which point it becomes tabulation, so yes they are similar

xxpertHacker (626)

@MrEconomical Well, good luck teaching dynamic programming in your tutorial!

MrEconomical (2256)

@StudentFires memoization is definitely an important concept in programming and can usually be trivially implemented in recursive algorithms for a huge performange gain. I just wanted to say, great tutorial!

firefish (886)

@MrEconomical In other words Idempotency.

DynamicSquid (4547)

Wow, there is a huge speed difference!

xxpertHacker (626)

@DynamicSquid Like I said, I literally laughed at how insane the difference is.

xxpertHacker (626)

@DynamicSquid And if you know JavaScript and understand my wrapper function, you can apply it to whatever code you have too. I'm preparing to implement in C++ using lambdas. Since you know C++, thought you'd be interested

DynamicSquid (4547)

@StudentFires If you implement it in C++ that would be great!

xxpertHacker (626)

@DynamicSquid Do you know how to make variable argument functions? If you could help me with that, that'd sure speed things up.

DynamicSquid (4547)

xxpertHacker (626)

@DynamicSquid Yeah. Having a variable "arity"

DynamicSquid (4547)

@StudentFires Yeah, now that I think about it, there isn't anything else you could be referring to when you said "variable argument functions". So anyway, I wrote this example:

``````#include <iostream>
using namespace std;

template<typename Result, typename ValueType>
void Sum(Result& result, ValueType& valueType)
{
result += valueType;
}

template<typename Result, typename Current, typename... Next> // variadic template
void Sum(Result& result, Current currentValue, Next... valueN) // make sure the two functions have the same name
{
result += currentValue;
return Sum(result, valueN...);
}

int main()
{
}``````

So that's basically how to use a variadic function. I don't know how you're going to implement that, so this is all I can help with. Let me know if you have any questions.

Oh, and sorry for the massive indents, I wrote this on VS

DynamicSquid (4547)

You can visualize it better if you put a `cout` statement in each function. Perhaps for the first function we include `cout << "1";` and for the second we have `cout << "2";`.

The output would be 221. Since at the very end when we have two arguments, "answer" and "30", it will call the first one.

xxpertHacker (626)

@DynamicSquid Is it possible to do this using `auto` lambdas?
I'm trying here:
https://repl.it/@StudentFires/VarardicFunc

Should I just invite you?

DynamicSquid (4547)

@StudentFires Well it's actually getting pretty late for me, and I have Online School tmr morning, so unfortunately I can't be much help to you right now...

DynamicSquid (4547)

@StudentFires I've never tried it with auto lambdas, but I think I read about it somewhere, so it should work

Highwayman (1442)

@DynamicSquid and 4 days later you answer one of my biggest questions about programming in only 6 lines of code.

Edit: oh wait.
God dammit

xxpertHacker (626)

@Highwayman You talkin about his tutorial on templates?

Highwayman (1442)

@StudentFires nah, I was talking about variadic arguments in C++ (the example he gave above).
I just can’t wrap my head around that type of thing. :(

xxpertHacker (626)

@Highwayman Oh, honestly I was just about to ask for your help w/ it, because I made progress... I have the variadic lambda... but I don't know how to use the arguments now.

Highwayman (1442)

@StudentFires basically you a
Expand the arguments using the ... operator which makes it into a list of the arguments, separated by commas. Maybe you could just toss that in a tulple?

xxpertHacker (626)

@Highwayman I've only read about tuples, I don't understand them and I sure don't how to use them. Also, that's what happens with JavaScript, not C++.

Highwayman (1442)

@StudentFires it’s also what happens in C++. Let me see if I can dig something up for you...

Highwayman (1442)

@StudentFires alright, got it. I’ll post code in one sec...

xxpertHacker (626)

@Highwayman Can I just invite you to my C++ variadic lambda Repl?

Highwayman (1442)
``````template <typename... Ts>
void nothing(Ts... args) {
unsigned long len = sizeof... Ts; // sizeof... will tell me how long the list is.
std::tuple<Ts...> x(args...);
}``````
Highwayman (1442)

@StudentFires I may have figured something out last night with the variadic argument list. I put some code in the repl you shared with me for you.

[deleted]

@Highwayman I'm sending the message on behalf of SF: If you're done w/ the Repl, just post it (if you want), and give some partial credit to SF.

Looking at how much more you added, lines 51-53 are practically useless.

Highwayman (1442)

@JadenGarcia Hm, it’s not really finished yet(I’m not sure how I’ll add in the function, still working on that.... ) 51-53 and all the others like them are redundancies in case of someone else trying to use the class who’s not as well acquainted with how it works like if they accidentally pass the wrong cache to the memoizer func. Are you the same person who I worked with?

[deleted]

@Highwayman You remember the link SF gave you to breach the your internet blockers? It opens 3 pages. Read the first page it opens. You'll find this name, actually, I forgot about my account's bio read that too. Or even my Repls too, I made this memoization Repl before this tutorial post was even made.

Highwayman (1442)

@JadenGarcia ah, ye I see the bio now lol noice. XD

DynamicSquid (4547)

@JadenGarcia Wait a minute, so StudentFires is a shared account that is controlled by people that got fired from StudentHires?

[deleted]

@DynamicSquid Eh, some of 'em. Like me.

Is dynamic programming and memoization the same?

xxpertHacker (626)

@AdarshKumar5 I believe that memoization falls under dynamic programming. There was actually a dynamic programming tutorial series made around the same time that I posted this, if you can find it, it goes into much greater depth and actually explains stuff.

SpaceFire (117)

Complaint: I requested the 69420th number of fibonacci yet here i am precicely 531 seconds later still waiting for my answer. i would like a full refund.

xxpertHacker (626)

@SpaceFire Unfortunately, StudentFires © isn't in a good position financially, due to a certain virus. Also:

You can try any number less than 200,000...

You must choose the memoized option. Also, the memoized option was made into a module too!

SpaceFire (117)

You can try any number less than 200,000 without choosing to loop, and you'll receive an answer within 10 seconds, guaranteed or I'll refund you.

xxpertHacker (626)

@SpaceFire It's expected that you had used the memoizer, not the normal function.

Okay okay, retest the normal version, it's non-exponentially growing now.

AmazingMech2418 (994)

Is this supposed to happen?

xxpertHacker (626)

@AmazingMech2418 Yeah, that's expected. I explicitly wrote:

You can try any number less than 200,000...

What did you use?

AmazingMech2418 (994)

@StudentFires Also took longer than 10 seconds. Actually 19...

xxpertHacker (626)

@AmazingMech2418 I had a whole debate with someone here about that number. Find it. DynamicSquid got involved.

AmazingMech2418 (994)

@StudentFires It's at the top. I already saw it. I saw it in the 19 seconds that I was waiting for it to return what seems to be an error.

xxpertHacker (626)

@AmazingMech2418 Find the conversation with bgrubert, it's literally at the top.

xxpertHacker (626)

@AmazingMech2418 Ha, nice. What brought you here, to this ancient post? Plan on using it?

AmazingMech2418 (994)

@StudentFires I'm trying to figure out what it really is right now. I found it just looking through your posts because I read a comment from you saying that a graph from Wolfram Alpha would be in learn or whatever and then I went to your posts and this is the first learn post I saw. Is this really just caching the data to prevent it from taking too long by repeating the same functions over and over?

AmazingMech2418 (994)

@StudentFires Also, wouldn't this only be useful if values were repeated?

xxpertHacker (626)

@AmazingMech2418 Yeah, all it does is cache the results. That's the whole idea: larger binary, but faster execution speed.

But what do you mean:

[A] graph from Wolfram Alpha would be in learn

I asked someone to graph the Pi formula I used for me, because I was lazy, but they never did. And the post didn't blow up anyway.

AmazingMech2418 (994)

@StudentFires Shouldn't you add a way to process the memory stack to make sure it doesn't use too much data? In a low-memory device, this would just crash it and, if done in C or C++, could cause a buffer overflow as well.

xxpertHacker (626)

@AmazingMech2418 Pure functions. Any mathematical function that has a 1 to 1 input - output ratio. Think `f(x, y) = x ^ y` That can be a slow calculation for large numbers, but by caching say, `20 ^ 20` it can be much faster upon second calls.

AmazingMech2418 (994)

@StudentFires Yes, but what about buffer overflows?

xxpertHacker (626)

@AmazingMech2418 Functions that have side effects won't work, read the code comments and the post thoroughly.

xxpertHacker (626)

@AmazingMech2418 Umm... that's not a problem with my caching system. That's a problem with the function being input into the memoizer.

Oh, nevermind... umm... idk, I guess, but the extra checks would slow down the function. In the C++ the check-less version would be preferred over the "safe" version, for performance. But then again, I've updated my memoization wrapper since this post anyway.

xxpertHacker (626)

@AmazingMech2418 This is JavaScript, a buffer overflow shouldn't occur in an array. In other languages, C++ for example, this is a major problem. I was to lazy to finish porting this to C++ using lambdas. Wanna help me?

AmazingMech2418 (994)

@StudentFires Yes. Sure! I just ran a benchmark test and the memory-safe version seems to be 1 ms off.

xxpertHacker (626)

@AmazingMech2418 You made a memory save version?

AmazingMech2418 (994)

@StudentFires Actually, memory-safe: 5ms, normal: 9ms

xxpertHacker (626)

@AmazingMech2418 I'm getting different results when running your memory safe code. 9ms and 5ms, not the other way around.

xxpertHacker (626)

@AmazingMech2418 Your code is the specialized wrapper for unary functions, yes? Can you make an optimized general wrapper?

AmazingMech2418 (994)

@StudentFires I'm running a different version now that should get a better result.

xxpertHacker (626)

@AmazingMech2418 Did you use a minifier or what?

Don't forget to upvote the post!

AmazingMech2418 (994)

@StudentFires What do you mean by general wrapper?

xxpertHacker (626)

@AmazingMech2418 Wanna talk in a Repl to explain the problems I've had with this? and how to optimize it? The general wrapper is impossible to port to statically typed languages.

By wrapper I'm referring to the memoization function.

AmazingMech2418 (994)

@StudentFires By general, do you mean like

``let memoize = (f,c)=>(...a)=>c.hasOwnProperty(a)?c[a]:(c[a]=f(...a));``

?

xxpertHacker (626)

@AmazingMech2418 That's not even the true general version.

shaunakg2011 (2)

function cool()
console.log(nice)

cool()

xxpertHacker (626)

@shaunakg2011 That code is improper., that will fail for multiple reasons.

It'd be great if you can build a visualization for this.

xxpertHacker (626)

@amasad Umm... any ideas on how I should implement that?

TomoIshigami (0)

Wow what a difference ...

xxpertHacker (626)

@amasad Since you're the "ceo" of repl (but not marked as mod), can you move this to the "learn section"? If you deem it appropriate.

Highwayman (1442)

# YEAS

t

Highwayman (1442)

xxpertHacker (626)

@Highwayman
1) I'm quoting you on that.
2) Can you ping an admin/mod to move this?
3) Thanks!

xxpertHacker (626)

@Highwayman The "t" is on the next line, was that an accident?

Highwayman (1442)

@StudentFires
2) hmm ngl I have no idea who’s actually a mod on this site,
Uhhhmmm @theangryepicbanana
3) yw!

Highwayman (1442)

@StudentFires no, it was not. The t makes the YEAS into YEAST :P

xxpertHacker (626)

@Highwayman I know that, that's why I asked if it was an accident that it was on the next line, not that there was a random t.

Highwayman (1442)

@StudentFires ahh, well then in that case yea I put the t for the yeast XP

Highwayman (1442)

@StudentFires also thank you for noticing the t lol

SixBeeps (3757)

Hmm, interesting idea. Might wanna put it on the Learn board, though ;)

xxpertHacker (626)

@SixBeeps Can I simply move it over? If so, how?

SixBeeps (3757)

@StudentFires I believe a mod has to do it.

xxpertHacker (626)

@SixBeeps Should I just ping a random mod and hope for the best?

xxpertHacker (626)

@SixBeeps To a certain degree I am teaching, but my code isn't well explained or commented on. Also, I'm primarily showing off.