Its good that you showed working of the memoization, but there are some inbuilt decorators for this exact same process, we can use cache or lru_cache from functools library. So that we don't need to write the memoization function every time.

To add to this nice video: Memoization isn't just some random word, it is an optimization technique from the broader topic of "dynamic programming", where we try to remember steps of a recursive function. Recursive functions can be assholes and turn otherwise linear-time algorithms into exponential beasts. Dynamic programming is there to counter that, because sometimes it may be easier to reason about the recursive solution.

You do mention this at the end, but "from functools import lru_cache" is a) in the standard library b) is even less to type and c) can optionally limit the amount of memory the memoization-cache can occupy.

Memoization is a very useful technique, but it is trading off increased memory usage to hold the cache to get the extra speed. In many case it is a good tradeoff, but it could also use up all of your memory if overused. For the fibonacci function an iterative calculation is very fast and uses a constant amount of memory.

Memoization is very important concept to understand for code performance improvement. 👍 I have used different approach in the past for this exact issue. As a quick way, you can pass a dict as second argument, which will work as cache def fib(numb: int, cache: dict = {}) -> int: if numb < 2: return numb else: if numb in cache: return cache[numb] else: cache[numb] = fib(numb - 1, cache) + fib(numb - 2, cache) return cache[numb]

Awesome video. This is wonderful to learn. Thanks, I really appreciate your videos.

Maybe some people don't realize why it's so good with fibonacci and why they aren't getting similar results with their loops inside functions. This caches the function return (taking args and kwargs into account), which is mega helpful because the Fibonacci function is recursive, it calls itself, so each fibonacci(x) has to be calculated only 1 time. Without caching, the fibonacci function has to calculate each previous fibonacci number from 1, requiring rerunning the same function(x) a huge number of times.

Definitely helping to boost a bit of performance in my massive open world text adventure I'm developing. Thank you for this tip!

key creation here seems risky, as in some odd cases 2 different (k)wargs can end up as same key. Example: Args 1, kwargs "2", args 12, kwargs 12 empty strings. Would recomend adding specjal character between args and kwargs to avoid such thing.

Great video, by the way witch theme are you using?

That's so neat. Python has a solution for a problem called Cascade Defines in the QTP component of an ancient language, Powerhouse.

Thanks a lot this cntent is incredible for junior python devs like me

how is memoization different from the lru_cache u discussed in another video?

used a for loop for my fibonacci function: def fib(n): fibs = [0,1] for i in range(n-1): fibs.append(fibs[-1]+fibs[-2]) return fibs[n] ran like butter even at 1000+ as an input

Could this also be used in a while loop for example?: while a != 3000: print(a) a+=1

For primitive recursive functions, such as Fibonacci's series, tail recursion would also circumvent the issue with max recursion depth, wouldn't it?

I would like to know how you did that arrow as I have never seen it before?

thank you very much !

Why? In the functools module @cache decorator does the same thing and you don't have to write your own implementation but just from functools import cache

Another way to optimize your Python is to use a systems level language and to add bindings 🦀. This is why polars is so fast

could you please explain where it store the cache?

I actually think that this isn't that great of an example. This only works because the function recurses twice. Memoization is a great tool for pure functions that get frequently called with the same input. The recursive fibonacci definition happens to do this, but this is still not a great implementation. An iterative approach can be even faster and won't use up memory. You could even momoize the iterative implementation, for quick lookups of repeat inputs, but no wasted memory for all the intermediate values. Memoization is a powerful and useful tool, but it should be used when it is appropriate. In this case a better algorithm is all that is needed. (And you don't even need to change the recursion depth!)

This is SICK

Why is there not a new cache defined for each function call?

I used the same technique to minimize AWS lambda calls to other services when it's the same expected value return.

It should be noted that generating keys that way can break compatibility with certain classes. A class implementing the __hash__ method will not behave as expected if you use its string representation as the key instead of the object itself. The purpose of __hash__ will be lost and __str__ or __repr__ will be used instead, which are neither reliable nor intended to be used for that purpose. It's generally best to let objects handle their own hashing. I realize you can't cover everything in a video so I wanted to mention it. One solution would be to preserve the objects in a tuple: key = (args, tuple(kwargs.items())) Similarly, the caching wrapper in Python's functools module uses a _make_key function which essentially returns: (args, kwd_mark, *kwargs.items()) where kwd_mark is a persistent object() which separates args from kwargs in a flattened list. Same idea, slightly more efficient. As others have noted, I think you missed a good opportunity to talk about functools, but that may now be a good opportunity for a future video. Thanks for your time and content.

lru cache decorator is already available at functools

It seems great to implement. Can I do it with any code?

What is the difference between lru_cache and this

Functools library already has two memoization decorators: cache and lru_cache. So no need to write your own implementation.

Nice!!!

Hello. Please could you explain me what's the most efficient between using @memoization and @lru_cache? Thank you, and congratulations for this really useful channel!

As a cpp dev, using recursion instead of basic loop to calc fibonacci looks like overkill. Personally i will write it like 2 element table, one boolen to change postion where im setting newest calced variable and doing this in loop for n times

i love your videos

Why don't you use DP?

fibonacci(43) generates more than a billion recursive calls to fibonacci(n) using that code. Its no wonder fibonacci(50) doesn't complete, think how many times its generating a fibonacci(43) call which will add a billion more calls. There's only 50 unique return values, the cache version is 50 function calls vs literally billons of recursive function calls.

Awesome

at 6:40 on line 28 10_000 what is that syntax?

can someone explain to me '→' i am not familiar with it in python

Thanks

2:40 Should take about 26 hours, looking at the time it took to do fib(30). Fib(40) would have been a better number to make your point.

implementation of memoization is very slow compared to if you used hashmap or 2d array but a nice starter to dynamic programming for beginners

Use just prefect library

you can easily make fib with loops instead of recursion, saving yourself stack frames, stack memory, loads of time and your sanity. Recursion should be avoided whenever possible. It's slow, eats limited stack space, generates insane, impossible to debug stack traces and is generally a pain in the rear end. Caching results makes sense in some applications. But fib only needs 2 values to be remembered. Memory access, especially access larger than a page, or larger than processor cache is slow in it's own right. An iterative approach also doesn't require boilerplate code for a caching wrapper. And of course you don't get max recursion depth errors from perfectly sane and valid user inputs if you don't use recursion. Which you shouldn't. The naive recursive approach takes O(n^2) time. The iterative approach only takes O(n). Memorization also takes this down to O(n), but you still get overhead from function calls and memory lookups. If you want fast code, don't recurse. If you want readable code, don't recurse. If you want easy to debug code, don't recurse. The only reason to recurse is if doing it iteratively hurts readability or performance, whichever is more important to you. The max recursion value is there for a reason. Setting an arbitrary new value that's pulled out of your ass isn't fixing any problems, it just kicks the can down the road. What if some user wants the 10001st number? What you want is an arbitrary number. Putting in the user's input also is a really bad idea. Just... don't use recursion unless it can't be avoided. Here are my results, calculating fibbonacci(40) on my crappy laptop. In [27]: measure(fib_naive) r=102334155, 44.31601328699617 s In [28]: measure(fib_mem) r=102334155, 0.00019323197193443775 s In [29]: measure(fib_sane) r=102334155, 2.738495822995901e-05 s As you can see, the non recursive implementation is faster by a factor of 10 again, and it will only get worse with larger values. Of course calling the function again with the same value for testing in the interpreter is a bit of a mess. obviously an O(1) lookup of fib(1e9999) is going to be faster than an O(n) calculation. fib_naive and fib_mem are the same except for using your implementation of the cache. fib_sane is def fib_sane(n: int) -> int: p = 1 gp = 0 for _ in range(1, n): t = p + gp gp = p p = t return p

You invented the wheel

Whoah

Dude i know this video is to show memoization but in case you don't know there is a formaula for n'th fibonnaci and that's very simple too

Wait, so "memoization" is not a typo?

This is like, the usual talk about memoization but it's just slightly wrong everywhere. You don't use default libraries to import this functionality, you however don't write case-specific code for this case either, instead, you try to write generic library code very badly. Fever dream'ish quality to this video.

memory leak go BRRRRRRRR

lru_cache seems significantly faster and requires less code.

Lesson: stop using recursion because it's slow. Use while loops instead.

I know it is for demonstration purpose but this implementation of the Fibonacci sequence is awful, with or without the decorator. Without the decorator you have a O(exp(n)) program and on the other end a memory cache which is useless unless you need all the Fibonacci sequence. If you want to keep a O(n) program without memory issue in this case, just do a for loop and update only two variables a_n and a_n_plus_1. Like this, it is still a O(n) program but your store only two variables, not n. I know that some people will say it is obvious and that example has been chosen for demonstration but somebody had to say it (if it is not already done)

Man I'm thinking what if we use this function in Cython code 💀.

the better way might be to use generator functions in python

poderoso script super🎉

Optimizing python be like Feed a turtle for speed istead using a fast animal

I see his point. His code, if if cannot add up some numbers to Fibonacci(50), in less than a few seconds, he's got the wrong code, which is what he's demonstrating, or he's using the wrong computer programming language for this task. Everyone knows scientific problems are best handled in FORTRAN (or at least, C or Rust), and this problem is pure arithmetic. Python is not the right language for this problem unless of course memorize is used.

dont use python = more speed.

fibonacci? use O(logN) method

from functools import wraps from time import perf_counter import sys def memoize(func): cache={} @wraps(func) def wrapper(*args, **kwargs): key= str(args)+str(kwargs) if key not in cache: cache[key]=func(*args, **kwargs) return cache[key] return wrapper def sum(n): s=0 for i in range(n): if i%3==0 or i%5==0: s=s+i return s t = int(input().strip()) for a0 in range(t): n = int(input().strip()) start= perf_counter print(sum(n)) end= perf_counter #For this code, it is not working-----------

The best way to optimize python is to use another language

in functools there is a decorator @cache or @lru_cache

Can functools.lrucache be used for this instead?

That was interesting and effective. I tried using 5000 and got an error Process finished with exit code -1073741571 (0xC00000FD). I started looking for the upper limit on my Windows PC, and it's 2567. At 2568, I start to see the error. It may be because I have too many windows each with too many tabs, so I'll have to try it again after cleaning up my windows/tabs. Or it may just be a hardware limitation on my PC. Still, it's incredibly fast. Thanks! Also, I just checked for the error message on openai (since everybody's talking about it lately) and it said this: ======================================= Exit code -1073741571 (0xC00000FD) generally indicates that there was a stack overflow error in your program. This can occur if you have a function that calls itself recursively and doesn't have a proper stopping condition, or if you have a very large number of nested function calls. To troubleshoot this error, you will need to examine your code to see where the stack overflow is occurring. One way to do this is to use a debugger to step through your code and see where the error is being thrown. You can also try adding print statements to your code to trace the flow of execution and see where the program is getting stuck. It's also possible that the error is being caused by a problem with the environment in which your program is running, such as insufficient stack size or memory. In this case, you may need to modify the environment settings or allocate more resources to the program. If you continue to have trouble troubleshooting the error, it may be helpful to post a more detailed description of your code and the steps you have taken so far to debug the issue. =======================================

This reminds of learning to multiply at school a long time ago 🧓. Thanks for the tutorial video 😊! likes = 57 😉👍

i believe that simple is better...and faster... #fibonacci time_start = time.time() print('st:', time.time()) a, b = 0, 1 fb_indx = 10000-1 ctn=0 while ctn != fb_indx: #print( b, end=' ') a, b = b, a+b ctn+=1 print( ' ', 'fibonacci', fb_indx, ':', b) print(' ended:', time.time(), ' ', 'timed:', time.time()-time_start) #timed: 0.0.005985736846923828

OMG! You can just use functools.cache...

In your fibonnacci implementation, f(n-2)+f(n-1) would be more efficient for the recursion because it reaches a lower depth sooner