Using Memoization to Speed Up Code
xxpertHacker (627)

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
DynamicSquid (4550)

Wow, there is a huge speed difference!

xxpertHacker (627)

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

xxpertHacker (627)

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

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

xxpertHacker (627)

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

DynamicSquid (4550)

@StudentFires Are you talking about variadic functions?

xxpertHacker (627)

@DynamicSquid Yeah. Having a variable "arity"

DynamicSquid (4550)

@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()
{
	int answer = 0;
	Sum(answer, 10, 20, 30);
	cout << "The answer is " << answer;
}

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 (4550)

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 (627)

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

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

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

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

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

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

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

Highwayman (1442)

@StudentFires

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 (4550)

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