A Practical Guide to Algorithms with JavaScript Generic Memoize Function Solution

[00:00:00]
>> Bianca: All right, so I'm gonna go over all of the exercises in one go, from task one through task four. And we'll talk about the different optimizations and then we're go even further and make it a little bit nicer, as well. So again, we started off with this times ten function, all it does is it takes input and returns that input times ten, it does some calculation, here.

[00:00:22] So when we hit play we can see we're console logging TASK 1, and times 10 returns 90. Referencing that. So our second task is to use an object to create a cache, so that we don't have to calculate times10 with the input 9 more than once. How do we do that?

[00:00:46] Well, first we want to call it with some value, nine, so n is nine. And since our cache is initialized as empty, we skip over that first case and we jump into this else. So in this else, we're gonna calculate the result for n, which is 9. And so 9 times 10, that's gonna be 90, right?

[00:01:11] Result is then 90. So cache of n is going to look something like this in our object. So we can move that up here just for our reference. You can imagine that this happening in the background, you can imagine that's what's happening and then we return the result.

[00:01:31] When we call again with 9, it's going to say, is 9 in the cache? And in fact, it is, right? And so we get to jump into this block. We're gonna do a little console.log, and we'll just return the cache. This is an optimization, because we are not having to do this calculation every single time.

[00:01:54] This is especially important for very expensive function calls. And so we're having a trade off here of space, right, we're going to be caching all these values, which is adding more data in memory, however, it can really speed up our time complexity.
>> Bianca: Great, so if we hit play, we can see,

[00:02:24]
>> Bianca: Let's just clear that, you can see that first,
>> Bianca: That's interesting, it's cause it already, hold on I need to, so the cache, since, this is the problem actually with having global, that's because I left that there, okay. It's like it's not clearing.
>> Bianca: Okay, there we go, so first, we calculate the results, which is 90, and then we'll fetch it from cache the second time that we call it.

[00:02:56] So these are just console logging here and hitting these different cases. Okay, so we have a global cache. Wanna avoid that, so how do we clean that up? We're gonna move it into a function. We just wrap our regular function in a parent function.
>> Bianca: We would change this earlier.

[00:03:26]
>> Bianca: I forgot what we called it.
>> Bianca: And,
>> Bianca: When we call this, so we're gonna initially call our parent function, it's gonna return this function that means this variable name is retaining a reference to this function. When we execute this function, down here, it also retains a reference to any variables saved or mutated in the parent scope, as well as, any variables that were passed in to the initial scope of the parent.

[00:04:03] In this case, we're not passing anything, so no big deal, but if we had, we could also retain access to those parameters in this scope, assuming that you didn't overwrite it. If you name this n, and then this one n, it's gonna override it, so just be careful of naming conflicts, but otherwise, you should have access.

[00:04:23]
>> Bianca: Okay, so then we can hit play.
>> Bianca: Great.
>> Bianca: Very cool. All right, and then we have our next one, which is, we want to make it generic. As programmers, a big part of going from a beginner programmer to an intermediate or advanced programmer is making things more generic, more reusable.

[00:04:56] And so with our minimalize function, we're making it much more reusable, because it doesn't rely, we're not hard coating that times10 operation. So this function, memoize, which is called memoize, cuz it doesn't have necessarily anything that it does. You pass in whatever function that you would like for it to run.

[00:05:17] And so the only difference between this one is, we have our times10 where we pass n, instead we just call it, call back, we pass n, and when we call this function we pass in a reference to this other function. So a little crazy, so first of all, we're returning a function, we're saving it in here, but we're also passing in a function, because in JavaScript functions are just data, we can do that.

[00:05:48] And it's kind of cool and fun, so why not? And so, and like I said, since we have access to our parent scope, because of closure, we have access to our call back here. And then we just call it right there.
>> Speaker 2: It's already expecting an argument, so that's why we could just pass n right into it.

[00:06:09]
>> Bianca: Mm-hm, and then we can make this more generic, so right now, this call back isn't so generic, this memoized function, because we can only call it with one argument. So down here, when we, so we call memoize times10, Memoized with times10. And then we call this memoizedTimes10, because it's a times10 method that is memoized.

[00:06:32] And then we passed the nine, this is gonna get memoized and saved into our cache. But we could call this with another function and it would do the same thing. That's why it's generic. Except that we're only allowing it to pass one argument to our callback. So if we wanted to make it a little more generic, you could have it pass multiple using a spread and rest operator.

[00:07:04] Just like that. So then, they can be a different variable amounts of arguments you could pass in. Mm-hm?
>> Speaker 3: Yeah, I'm mostly following you, but I'm having a little bit of friction trying to trace the passing of variables through the different functions.
>> Bianca: Mm-hm.
>> Speaker 3: Do you mind doing a trace?

[00:07:21]
>> Bianca: Yeah, absolutely, it's like my favorite thing. Okay, so let's start with, we always start with where the function is being called. So memoize, and we're gonna pass that function that we defined up here.
>> Bianca: No, I lost this [INAUDIBLE], here we go. So times10 is now cb, cache we initialize as empty.

[00:07:46] We return this function as empty. I'm sorry, wait, it's not empty, it's full of stuff. We return this function, it is not invoked, we just return the body. This check if else is not run yet, because we haven't run this function, we're just returning it, the definition. Just like when we define this function here, nothing actually runs until we make it down here and we invoke it.

[00:08:10] So similarly, where this is just a function definition, nothing is run yet. And we save it in this variable. Now, like any function that we wanna run, we're gonna call it, recall it down here with nine. So now, nine is our argument, and so really what this is gonna look like, is like an array with nine, that's what that args with the dot, dot, dot is doing.

[00:08:35] Do we have it in cache, no we don't, right, we haven't called this yet, cache is still empty. So, we're going to, do our calculation, this is going to do this.
>> Bianca: Whoops, excuse me.
>> Bianca: This is just gonna say, call back at nine. If there are multiple, like say, we did nine and ten, what it would do is it would just pass it as a series versus an array.

[00:09:02] That's what that's doing. So we're not doing that.
>> Bianca: But just so you know. So we're doing our calculation, storing it, caching it, returning it. Then when we get to this line we're gonna call it again, and this is when we're gonna hit that cache. So we have nine, again, we're jumping into the body of this function.

[00:09:29] When we run the body of this function all the variables in the scope are gonna be reinitialized, but the variables in this scope are gonna stay the same. That's very important when reasoning about a closure. The closure variables here stay the same, CB is the same, our cache is the same, but the arguments that we pass in are new.

[00:09:50] N is now, well, it's actually still nine, but it's a new version of nine you could think. So we're going to say, is nine in cache? Yeah, so we're gonna fetch it and return it. Or we're gonna console log in and then return it.
>> Bianca: Mm-hm.
>> Speaker 4: Just a question for the else statements.

[00:10:19] When you create that result variable does it serve any benefit other than just like readability as opposed to just assigning the cache?
>> Bianca: Yeah, yeah, it's just there to break out like the step by step, so when I explain it-
>> Speaker 4: Just curious.
>> Bianca: Yeah, yeah, yeah, no, yeah, good question.

[00:10:40]
>> Speaker 2: How does the first example greatly differ from the third example in terms of the space complexity and the time complexity?
>> Bianca: Mm, so for the different examples, the time and space complexity are consistent. In terms of using memoization versus not using memoization in a solution, for our specific case where our call back is really doing a constant time operation, the time complexity improvement is none.

[00:11:12] However, this technique is really important for when you're a call back is doing some very time expensive operations. And so, we'll see that when we get later on in this course, we'll see that sometimes our calculations can be very expensive.