Memoization And Dynamic Programming Explained

Подписаться 1,6 млн

Просмотров 94 тыс.

50% 1

Memoization is a big complicated word that you may have never even heard before, but you may be surprised to know that you are most likely already using memoization without even realizing it. Memoization is just the act of caching values so that they can be calculated quicker in the future. Memoization is really useful in all parts of programming, but where it is most useful is in dynamic programming. In this video I will explain what memoization is, how to use it, and why it is so useful especially in dynamic programming.
📚 Materials/References:
Recursion Tutorial: • What Is Recursion - In...
🧠 Concepts Covered:
- What memoization is
- When you should use memoization
- How to use memoization
- What dynamic programming is
- How to use memoization in dynamic programming
🌎 Find Me Here:
My Blog: blog.webdevsim...
My Courses: courses.webdev...
Patreon: / webdevsimplified
Twitter: / devsimplified
Discord: / discord
GitHub: github.com/Web...
CodePen: codepen.io/Web...
#Memoization #WDS #DynamicProgramming

Опубликовано:

29 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 147

@SathishKumar-ot5kt 4 года назад

Great demonstration of memoization using Fibonacci function. I would have never realized the importance of memoization without this example. Thanks!

@MajorasMaskMailman 2 года назад

The Fibonacci thing was so cool!

@thatsalot3577 2 года назад

you can create a higher order function to memoize any function by doing this const heavyFunction = (input) => { let output = 0; for (let i = 0; i < input; i++) { for (let j = 0; j < input; j++) { output += 1; } } return output; }; const previousValue = [ ]; const memoize = (func) => { const memoized = (a) => { if (previousValue[a] != null) return previousValue[a]; previousValue[a] = func(a); return previousValue[a]; }; return memoized; }; const memoizedHeavyFunction = memoize(heavyFunction); console.log(heavyFunction(100000));

@HologramJay 3 года назад

Quick question: How in the world are you able to access the value in the array by prevValues[n]? The syntax you use works for objects by accessing the value via keys, but I've never seen values being retrieved from an array with the same syntax unless you're using a number to access the value by index.

@jeremiahberndt7809 3 года назад

I was also confused by this. I believe it is just the same index and so he is accessing it in the same place every time

@sustrata9125 Год назад

n is the parameter of the function.

@ratlamking 4 года назад

This is the fastest Subscribe button I have ever hit

@surelock3221 4 года назад

I hip thrusted that motherfucking like button so hard bro

@rittenbrake1613 4 года назад

me too

@japeter89 4 года назад

Agreed. The channel I needed to become a senior developer

@abhishek_k7 4 года назад

I was just searching for memoization and dynamic programming on RU-vid and saw this notification. Literally! lol

@DouglasGordo 4 года назад

Kyle is google AI confirmed.

@almudza9803 4 года назад

I agree

@WebDevSimplified 4 года назад

I may or may not be able to read minds :P

@abhishek_k7 4 года назад

@@WebDevSimplified now we know! lol

@opuu 2 года назад

Using array[n] is bad idea, instead use object[n].

@Typhoonbladefist 4 года назад

Cache lookup tables for beginners; you trade memory for efficiency. This is often used in games for sin/cos calculations.

@dinohunter7176 2 года назад

Where efficiency in your case mean speed, or execution time. :)

@fanyinU 4 года назад

Oh man, this is one of the most useful and clear videos I've ever seen! You are awesome. Thanks for putting out so many great content! Your channel is absolutely underrated.

@rishabhkalra9505 4 года назад

Dude... This was a really good example to explain memoization. Great work!

@akshat528 4 года назад

You are using an array for caching. Is it okay to use Hash table? const fibonacci = (number, memoHash = {}) => { if(memoHash[number]) return memoHash[number]; let result; if (number

@robertpetta1246 4 года назад

Awesome video. Thx! Here's a more succint way of doing the same thing: function fib(n, cache = [0, 1, 1]) { if (cache[n] != null) return cache[n]; return cache[n] = fib(n - 2, cache) + fib(n - 1, cache); };

@nomadvagabond1263 4 года назад

trading time for space.. good thing we dont live in the 80's 90's :3

@BigDoubleJoe 4 года назад

true, i was like "ok now you have a 30.000 entries long array". there are better ways to calculate fibonacci-sequence but i think the video deals with concepts instead of solving specific problems

@nomadvagabond1263 4 года назад

@@BigDoubleJoe now imagine doing this for a complex object.. i don't think you can use it everywhere though creating memory leaks and loads of bugs over time.

@Dsandles47 3 года назад

Maybe I'm just not catching it, but can someone explain how that for loop at the beginning creates a function that returns the square of a number?

@XengShi 2 года назад

I also did'nt understand, even its dosen't works for me

@av03 4 года назад

Thanks Kyle, now I understand how useMemo in react is useful

@ben790924 4 года назад

pls share your opinions

@smileyboi9386 10 месяцев назад

Memoization sounds like memorization with a speech impediment

@yaverjavid 2 года назад

I did this without knowing about it... Now I know a term for it;

@imPrathamDev 18 часов назад

I think the first example will be good if you used an object or map, I know this video is old but still

@Nadzap Год назад

This is a really really good video. Seriously, well done.

@ericdimarzio5756 4 месяца назад

What a great video. Awesome!

@takatakboy 4 года назад

Your explanations are so good to the point that I gain so much knowledge and confidence that I can solve problems using recursion and also start explaining them to people.

@KaleesM-tm4lw 9 дней назад

The memorization is Good but using object is better to hold the values in keys instead of doing it in an array format. If you use the array to memoize for the demonstration it'll look weird because the value will be captured in index. Here you're passing 30k as n value but in the memoize the index will be 30k index...

@raffaelenicolapiazzolla3927 4 года назад

Can you make flutter tutorial?

@zameeebasha 4 года назад

Mind blown 👨🏻‍💻👨🏻‍💻

@RedEyedJedi 4 года назад

As you know Kyle, I am a big fan of your channel, but every time you deliberately miss out a semi-colon, a little piece of me dies inside. I know you don't have to put them in with JavaScript but doing so can prevent errors from happening.

4 года назад

An excellent explanation, very clear and concise! The only thing you should have mentioned is that this is just an example and that nobody in their right mind would calculate Fibonacci numbers recursively, when there is a simple formula for them. This video might have given this misconception to people who don't know about it. Computing Fibonacci numbers recursively is a great (and pretty standard) example for memoization, but it's just that: an academic example, not a practical usage.

@4541047 4 года назад

Great video. Does your condition on the array should be != 'undefined' and not 'null' ? Since the array default value is undefined?

@robertpetta1246 4 года назад

Technically, yes, comparing it to 'undefined' would be correct, but the '!=' operator works with both 'null' and 'undefined', unlike the '!==' operator, which would then require '!== undefined'

@4541047 4 года назад

@@robertpetta1246 Thanks!

@ianhnizdo4787 2 года назад

I'm sorry that double 'for loop' in the first example makes no sense to me. Say 4. i=1 You add 1+2+3+4=10 i=2 You add again 1+2+3+4=10 10+10=20. By the end of the cycle you get 40. However 4 squared is 16. What am I missing here?

@Alex-ii3tv 4 года назад

Very good JS channel. Please continue making videos.

@marquezdrums 2 года назад

Can someone explain the difference between dynamic programming and memoization for me? is Dynamic programming just code that uses memoization, er...?

@pastorfred2543 4 года назад

Wow..wow..wooow.. Thanks so much for this Tip. I'm gonna Master this in the use cases.

@Mr.Unknown0701 Месяц назад

watched another video, that was way too difficult to understand, you made it easy to grasp the concept 👏❤

@samrey8134 3 года назад

3 days of research problems on memoizations solved in under 8 minutes. Someone get this guy a Cape and a "S" on his chest. Seriously....

@rajashekhar433 4 года назад

Can you please make a video on PWA like service worker and cache

@faiyazrasul2050 7 месяцев назад

A video on the 10 projects each for a beginner dev of JS, intermediate dev of JS, senior dev of JS

@raymondmichael4987 4 года назад

Thanks buddy, you really simplify things. Please can cover gulp especially currently version, I'm working with sass, I know you top some cheers on top, like html uglifying versioning and any you can think of. Or perhaps you can create using your dev tool of choice if it's parcel webpack or whatever.

@DossouJeanMarie 10 месяцев назад

is the memoization will reduice the execution time if i decide to show all the result at the same time? i hope that memoization is used for showing progressive answer only that.

@kingstonejob7840 2 года назад

I call this one memoization simplified, thank you. Do u have tabulation simplified too?

@greenie62 3 года назад

id offer to those learning this the first time, to find a fib(n) example where they draw out the tree's the 2 different approaches will create...essentially the first approach will entail the function to call itself as many times as the answer is (n = 50, most computers kinda hit the wall) and so its scaling in exponential time. The 2nd will prune the tree in a way that it grows at linear time.pretty crazy/powerful refactor. as always though, nice job on a quick/user-friendly explanation.

@ProGamer-rf5ic 5 месяцев назад

Can someone please explain to me how the initial squaring without memoization works?

@adilismail3593 4 года назад

Hello children you we are up against the crysis but if you look at history.... ~ byjus

@XengShi 2 года назад

2:55 can someone explain this for loop I didn't understand what's going on here

@sammykanan3932 3 года назад

this dude makes complex things way easier than almost everyone else I follow

@Paulo-oe6no 4 года назад

Great explanation! ty very much!!

@pipertripp 4 года назад

yeah, I using caching all the time, mostly of the "if ya got it in cache, don't make the REST call" variety. It's good to remember that for computationally intensive tasks caching can play an important role in improving performance. This was a nice vid on the subject. Well done.

@ridl27 4 года назад

holly sh*t! what an excellent explanation! and it reminds me of hash-tables)

@SimoneGesualdi 5 месяцев назад

Your videos are amazing, thanks!

@tacowilco7515 4 года назад

Great video as always. Probably worth mentioning that array was used just for demonstration purposes, so people wouldn't get confused :)

@animelover-qc3hv 2 месяца назад

loved it! thank you for this!

@abhisheksatyam4733 3 года назад

2:49 I hit like... got the concept, Watching till the end now...

@crycetruly 4 года назад

Very practical video, Thanks man..

@muhammadumair7861 4 года назад

Dude you are super cool instructor

@WebDevSimplified 4 года назад

Thank you!

@fadiliabdeljalil770 4 года назад

It was very helpful, thank you !

@LBCreateSpace 6 месяцев назад

Very clear example, thank you!

@sherazraees6746 Год назад

The fib program is not efficient. let's suppose when you pass 40 in fib function. so the function make a array of 41 index. and then you enter the value in 40 index. so in this array 40 index are empty.. so it's not perfect way

@memyaccount8213 6 месяцев назад

Efficiency can have multiple types though, like memory efficiency vs. speed/time efficiency. I think he's just more specifically talking about efficiency in terms of speed

@amitkumawat646 3 года назад

What is the time complexity of fib memoization ?

@XengShi 2 года назад

1:17 But in my computer all results comes at same time

@nextleveltech267 7 месяцев назад

Really Helpful. Thanks a lot

@HillelGarciaAustria 3 года назад

Just for you to know, the fibonacci sequence starts with 0, not with 1.

@Superhermanas566 2 года назад

Thanks, this is very clear video.

@tasmto 4 года назад

This makes sense now thank you Mr Kyle!

@shivanimishra2448 Год назад

Thank you again,Kyle.

@Andy-si1pl Год назад

"We are caching the value based on the input" PERFECT!!! I struggled with not remembering that FACT for ages.

@itsgojoverfr Год назад

guys guys guys, im quite new to programming and when kyle added those two fib() functions together i got pretty confused, like how can functions be added lol? i would appreciate a reply because i really don't understand.

@memyaccount8213 6 месяцев назад

It's based on what each function returns (note where it says 'return' in the function, to see how that's determined). So when you add two functions together, you're adding their return values. It's almost like when you add two variables together, because you're just adding together the values within the variables. And when adding functions, you're adding together the values returned by the functions.

@itsgojoverfr 6 месяцев назад

@@memyaccount8213 i appreciate the reply! Asked this question 8 months ago, have learnt a lot since then lol

@RomanKnav 2 года назад

Awsome. I had no clue how neither memoization nor dynamic programming worked until I watched this. Thanks!

@cyberlink2863 Год назад

mate you are is leterally on fire. ✌

@mickeykutti5165 2 года назад

What do the words associative arrays , lookup table,cache hit/miss ratio have in common with memoization?

@CROXoDyLE 2 года назад

Wow I thought my professor just wanted to kill me with this stuff. Turns out this might be the most useful topic. Thanks for explaining it so well!

@andresviveros3994 4 года назад

Can some explain the sample code at 0120? I am new to coding and cant see where the squaring happens. Thanks

@oida10000 3 года назад

Nice. Does JS offer a build in solution for this like Pythons lru_cache? It is tedious to get every result case into this array.

@parasarora5869 4 года назад

great explanation and examples...thank you very much !! 👍👍👍

@gurleensingh2600 Месяц назад

great explanation!

@AmarSingh-uw1db 3 года назад

Awsome explanation sir, Than you so much 👍🏼👍🏼👍🏼

@adriannaguevarra2714 Год назад

This is the first time I truly understood memoization and dynamic programming hahaha thanks so much!

@PrinceKumar-xh2ty 3 года назад

very good explanation

@ahmetkarakartal9563 2 года назад

wow you are so good. Thanks

@garrettguitar6583 4 года назад

Use an object, not an array.

@MaxSharpy Год назад

So clear and easy to fallow. Thx for making your vids Kyle!

@ninjarogue 3 года назад

Thank you, I like the way you approached this one, it was very easy for me to understand.

@kaiserkonok 2 года назад

Very Clear Explanation. Thank you so much🖤

@sushirolls24 3 года назад

Would memoizing the fib sequence still make it recursive?

@flashminat0x 2 года назад

dont need to lie i watched more than 10 vids of this concept and this one made inside my brain. nice work dude

@flyfly8401 2 года назад

so dp is using cache!

@usama57926 4 года назад

great explanation

@emiel04 Год назад

This is beautiful.

@CodeWithNepali 2 года назад

that was a really very simple explanation bro, thanks a lot bro:)

@kishoreandra 4 года назад

I learned something today !!..... Thanks sir!

@amatiasq 4 года назад

So dynamic programming is... recursion?

@rummanchowdhury3807 Год назад

Cool explanation.

@flyingsquirrel3271 2 года назад

This was exactly what I needed. Thanks a lot!! :)

@usama57926 4 года назад

wow amazing

@shivangchaturvedi237 3 года назад

Hands down the best go-to guy for JS basics.

@oleksandrvorovchenko8674 4 года назад

Thanks! Really good and simple explanation.

@software-egineering-be-tounsi 4 года назад

amazing !! very good subject

@abdelmonemnaceur7776 4 года назад

Simply, you are amazing :D thx!

@MahbubTonoy 2 года назад

Thank You

@zdargahi 2 года назад

this video is the most clear video to understand memoization

@brecoldyls 4 года назад

I like how you provided real world context for memorization and DP with the caching example. I would have liked to see you go a step further and explain the bottom up approach to solving DP problems e.g. solving Fibonacci iteratively using an array with a few initial values; however this would perhaps be a bit too advanced of a concept to put in such a short video so I understand the omission, maybe just mentioning it at least would have been nice. I like your explanation overall though and I’m curious, do you have a degree in Computer Science or are you self taught? With all your practical knowledge I would assume the latter but your videos like this and the ones on design patterns and recursion make me think that you have a more formal education. Thank you!