Using Memoization to Speed Up Code
xxpertHacker (614)

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


Some links I looked at:
https://www.freecodecamp.org/news/understanding-memoize-in-javascript-51d07d19430e
https://dictionary.babylon-software.com/dynamic%20optimization

You are viewing a single comment. View All
AmazingMech2418 (992)

Is this supposed to happen?

xxpertHacker (614)

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

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

What did you use?

AmazingMech2418 (992)

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

xxpertHacker (614)

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

AmazingMech2418 (992)

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

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

xxpertHacker (614)

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

I already wrote that I planed on using it in Adapt.

AmazingMech2418 (992)

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

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

xxpertHacker (614)

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

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

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

@StudentFires Yes, but what about buffer overflows?

xxpertHacker (614)

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

xxpertHacker (614)

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

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

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

xxpertHacker (614)

@AmazingMech2418 You made a memory save version?

AmazingMech2418 (992)

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

xxpertHacker (614)

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

xxpertHacker (614)

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

AmazingMech2418 (992)

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

xxpertHacker (614)

@AmazingMech2418 Did you use a minifier or what?

Don't forget to upvote the post!

AmazingMech2418 (992)

@StudentFires What do you mean by general wrapper?

xxpertHacker (614)

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

@StudentFires By general, do you mean like

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

?

xxpertHacker (614)

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