Check out a free preview of the full A Practical Guide to Algorithms with JavaScript course

The "Caching with Memoization" Lesson is part of the full, A Practical Guide to Algorithms with JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

Bianca discusses the difference between memoizing and the breadcrumbs caching technique.


Transcript from the "Caching with Memoization" Lesson

>> Bianca: We were talking about using the breadcrumbs method to cache values that we've seen before to optimize our unique function. Memoization is a type of caching, as well, and so the difference between memoization and the breadcrumbs method is that the value that we're getting to cache, so we rooted array at i and saved that into our breadcrumbs object, is not the result of a function.

If you're caching the result of a function we call that memoization, and you can think of it as memorization, remembering things. The concept of cashing in memoization are often conflated. Memoization is a type of cashing. Cashing really, in the simplest form in a JavaScript environment, is saving something into an object or an array.

Or even a variable, more like an object and array actually. That's all caching, so if you refresh the page, that's gonna be erased, it's not saved on discs, that's caching. Same with Node, if you're gonna cache it you're saving it into an object that's just on the server.

So if you shut off that server and restart it, you're gonna lose that cache unless you're syncing it to a database somewhere. So that's what caching is, and then there's types of caching, right? We cache HTTP requests and things in the browser, which is a little bit different execution environment than the JavaScript execution environment.

Anyway, we're gonna talk about factorial. So, factorial is the one were it's like, like n to the bang, bang is the exclamation point. That's how we say it in programming speak, bang. So what that looks like, so 5 factorial is 5 with a bang, which is just 5 x 4 x 3 x 2 x 1.

>> Bianca: Cool. So with factorial, we're doing a lot of the same calculations over and over and over again. And so instead of re-calculating the result of this, it's actually a recursive function. We could just memoize it, which means we're going to save the results of the factorial function into an object.

Just like in the breadcrumbs version, except that the value that we're caching is gonna be returned from a function. This is very very similar, just where the value comes from is what differs.
>> Bianca: Cool. And so you can see they're repeated here so it just keeps getting concatenated.

And so instead of calculating 36 again, if we just save 35, then we don't have to go through all of the decision trees of calculating the recursion of a factorial.
>> Speaker 2: Are you missing some level, and you have sudo code. Is there some kind of code that's supposed to go there, you're just not writing it?

>> Bianca: Yeah.
>> Speaker 2: The assumption is that there's gonna be code there.
>> Bianca: Yeah, there's some code there, it takes away from the point because it's a little confusing. But the point is is that factorial of 36 is just factorial of 35 times 36. So instead of every time we calculate, if we already calculated a factorial of 35, we don't need to recalculate it all over again, right?

Because I mean you got to do 35 times 34 times 33 all the way down to 1. So, do you have a question? Okay.
>> Speaker 3: When you talk about caching and memoization?
>> Bianca: Mm hm?
>> Speaker 3: Could that relate back to space complexity which you mentioned earlier along the time complexity.

>> Bianca: Yeah.
>> Speaker 3: Is this more an example that it's gonna affect space complexity?
>> Bianca: Absolutely. So yeah. With caching you're always making the trade-off between time complexity and space complexity. So it's faster but it takes up more space. In the browser environment, where a lot of us JavaScript engineers live, it's typically the obvious trade-off is time complexity for us and other environments where memory constraints are more relevant.

It's something you want to think about more, but in Java Script world, you can always memoize, always cache. It's always a good idea, unless you are getting into big data stuff then that's something that most of us don't deal with on the day to day.

Learn Straight from the Experts Who Shape the Modern Web

  • In-depth Courses
  • Industry Leading Experts
  • Learning Paths
  • Live Interactive Workshops
Get Unlimited Access Now