Memo Tables and the Magic of Higher Order Functions in Python!

Подписаться 59 тыс.

Просмотров 1,4 тыс.

50% 1

Higher order functions are functions that take in and/or return other functions, and we're going to use this incredibly powerful feature to implement memoization. Memoization is an incredible technique that can significantly speed up naively-implemented recursive functions,, with little additional knowledge required.
Today, we explore a Python technique to easily "inject" memoization capability to ANY function, allowing great speedups with no changes to the function itself!
= TABLE OF CONTENTS =
0:00 Introduction & Context
1:01 Video Contents Page
2:05 Background: Naive Recursive Functions
2:55 Code: Fibonacci Function
4:22 Code: Seeing the slowness of Recursive Fibonacci
5:59 Theory: Higher Order Functions in Python
7:03 Theory: Our Strategy to "Inject" Code into a Function
7:53 Background: Applying Higher Order Functions with Counting
8:17 Code: Applying Higher Order Functions with a Counting
11:18 Code: Using our count() function
13:22 Background: The big problem
13:54 Theory: What is Memoization
15:52 Code: Creating the memoize() higher order function
19:14 Code: Running our memoize() function
20:10 Code: Using count() and memoize() together
22:08 Code: Visualizing the Memo Table
22:53 Theory: Generalizing to larger functions (Multiple Parameters)
24:29 Code: The nCr() Function (Two Parameters)
25:24 Code: Applying count() and memoize() to nCr()
26:30 Code: Visualizing the Memo Table
27:31 Summary
= CODE DOWNLOAD =
To view and download the code written in this video, check out the following Bitbucket repository: bitbucket.org/nerdfirst/memoi...
To download, first click on "Downloads" in the left sidebar. Then, in the subsequent page, click "Download Repository".
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational RU-vid channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → www.nerdfirst.net/donate/
0612 TV Official Writeup: nerdfirst.net/0612tv
More about me: about.me/lcc0612
Official Twitter: / 0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond RU-vid videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! nerdfirst.net/
-----
Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.

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

27 июл 2024

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

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

One of the best video that clearly explain memorization ~ Great job!

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

Hello and thank you very much for your comment! Glad you liked the video =)

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

Very nice video! The count example can be used to explain proxy pattern via FP. Keep up the good work

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

Hello and thank you for your comment! Glad you liked the video =)

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

Awesome video, keep up the great work! :)

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

Hello and thank you very much for your comment! Glad you liked the video =)

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

I know this is kinda not directly the point of the video but for something like the Fibonacci numbers a generator would be the better option. (Maybe also for the binomial coefficient where r is a parameter for the generator. In this case the "memoization" is in the state of the generator (and has less overhead). The downside however is that generators only work in one direction (aka generating fib(5) after having generated fib(10) means creating a new generator).

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

Hello and thank you for your comment! Oh for sure - Fibonacci numbers are one of the few recusive functions that are much better off written as just a linear function using a loop. Generators are fine for this purpose as long as you note down the values generated. (But even then, re-running the generator wouldn't hurt as much as the recursive explosion we're seeing).

@Apprenticer Год назад

i know it is difficult to communicate but what is "augmented logic" or why are you explaining things in ana abstract way? Augmented function even google doesn't know it.

@NERDfirst Год назад

Hello and thank you for your comment! "Augment" is not a technical term. It simply means "to add on". So, an augmented function is a function in which we've added something to, so that it does more beyond its original definition. Understanding concepts in an abstract way is very important if you want to generalize and apply your understanding towards other problems, beyond just the example you've learnt from.