Memoization: The TRUE Way To Optimize Your Code In Python

i love your videos

from functools import lru_cache
This also does the work

memory leak go BRRRRRRRR

Thanks

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

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

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

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

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.

=======================================

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

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

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]

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.

dont use python = more speed.

Wait, so "memoization" is not a typo?

You know you should take a computer science course before making an optimization video, you are absolutely clueless and I feel bad for whoever will deal with your code

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

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

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

lru cache decorator is already available at functools

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)

Whoah

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.

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

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

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.

How can I generate randomly smooth 600x600 images with this Memoization algorithm?

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

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

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.

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.

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.

in functools there is a decorator @cache or @lru_cache

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

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

Nice!!!

It seems like an implementation of dynamic programming?

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!

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

fibonacci? use O(logN) method

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

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

Just telling that if you put number too large app will crash on low end device... so why not use @cache built inside functools... it allows to limit cache and setting limit to 5 works very well.

Use just prefect library

thank you very much !