[Solved] How Python memoization works?

Question

I'm trying to solve code coach Hofstadter's Q-Sequence.
I write the code in standard recursion fashion with base case and return statement, it passes test case 1 & 2 and other doesn't.
I check with Wikipedia and confirmed my code is correct with q(20) equals 12.
Then I search Q&A for hints and found 2 possible solutions. One is set a higher recursion limit, and the other is memoization.

I tried q(100) on my PC, and it keeps calculating after 5 mins so I forced it to stop.
With memoization it outputs the result instantly, yet it still fails on test case 6 in code coach.

Can anyone explain how memoization works in line by line style with q(3)?
I used https://pythontutor.com to visualized the process but still don't understand what's going on.

my_dict = {}
def q(n):
if n == 1 or n == 2:
return 1
if n not in my_dict:
my_dict[n] = q(n - q(n-1)) + q(n - (q(n-2))
return my_dict[n]

Answer 1

If you rename your my_dict variable to "memory", it might be clearer what it does.
Memoization is about keeping note of inputs and reusing the results that have already been calculated. With a more fancy word this is also known as cache. A dict is perfect for this, because lookup is instant O(1) complexity.
In your particular code, it is not yet useful for n=3 because nothing is reused yet, you only start memoizing after n=3. 1 and 2 are the recursion base cases. In your function you invoke q 4 times, that is quite insane when n gets higher. Because without memoization it has to recalculate all the subresults for every lower n value multiple times.

With memo, if the function has already calculated the result for a specific n, will just reuse it from the dict. the calculation is only performed for new n and stored in memo.

You can see also this old code of mine that has some explanation about the functools.lru_cache decorator that can achieve the same effect.
https://code.sololearn.com/cWpFUu2kmHLZ/?ref=app

Answer 2

Wong Hei Ming
memoization speeds things up by storing previously computed data in a cache so it does not have to be recomputed repeatedly in recursive functions. You used a dictionary as the cache in your function.
Tibor Santa
lru_cache is faster than dictionary memoization. But yes, for big recursive functions, memoization is the way to get things done.

But recursion should really be avoided whenever you can. It's a memory hog.
Easy to code but hard to process and a big resource consumer.

I added a non recursive version I found online to the code for comparison.

https://code.sololearn.com/cWO02XZSvvf5/?ref=app

Answer 3

Tibor Santa, your code have some notation I haven't seen before ("variable: datatype" & "->"), that's new to me. Lickily it is not that difficult to understand with a quick search.
On the memoization part I see you used decorator, and that is something I don't get used to. It is time to go back and study again.
And I found AI Sweigart wrote a book about recursion when I search the topic. It talks about memoiztion in chapter 7 and without decorator.
https://inventwithpython.com/recursion/chapter7.html
Maybe I will read from the beginning while study decorator again at the same time to better understand how both methods work.

Bob_Li, Tibor Santa's does use lru_cache in the code. And it is a good time to explore the library.

Anyway I set the recursion limit to 2000 with my code and solved teh code coach. Yet there are more to learn.

Answer 4

Wong Hei Ming
you should google search non recursive implementations of the sequence.

I added a non recursive function in my sample code above. It can go much farther than it's recursive siblings.

Answer 5

Functions in Python are objects, very similar to a class.
When you use the dot notation on a function name, you effectively create a class variable inside the function. Bob_Li is right, it represents some sort of namespaced global state, that is preserved after function execution, but also accessible from inside the function.

As a fan of functional programming I do not like this at all, because the declaration is not transparent, and it can make the function impure, when some external state is used or modified which is not dependent on function parameters.

You can test this with code like this:

class T:
pass

T.test = 42
t = T()
print(T.test)
print(t.test)
print(T.__dict__)

https://realpython.com/python-classes/#the-__dict__-attribute

Answer 6

Tibor Santa
Pure functions are indeed easier to reason about and test. But what we often end up with pure functional programming is lots of copies and duplications. It's like passing everything by value. Speed gains and memory resources is often traded off for code purity.

Maybe if the speed and resources are not the primary concern, the ideals of pure functions can be pursued, but whenever it's not possible, mutations and impure functions should not be ruled out.
Just be careful and keep the complexity down. Using impure functions is actually more resource friendly and faster.

As long as the mutations are clear and direct, they should not be a problem. The problem is when the code is big and lots of processes are mutating the same variable. Hidden mutations are hard to trace. The dot notation is one solution, but still be careful.

low level languages are fast because they mutate values via pointers. If they were to copy and create new resources every time, things would slow down very fast..🤔.

Answer 7

Bob_Li yes I'm aware about the performance trade-off.
But we could also ask the question this way. Which code is better? The one that is slow and perfect all the time, or the one that is really fast, but has or potentially can have bugs which are very difficult to fix :)
Maybe it also depends on the application if it can tolerate some errors.
Well that's why I like the design philisophy of Rust because it leads to mistakes being more difficult to make, by making the mutation and shared global state very explicit.

Answer 8

Bob_Li
A variable name with a dot? That's new!
Is it you give it a booster by hardcoding [None, 1, 1]? Changing the values give different results.

Answer 9

Wong Hei Ming
The list is the starting values for the sequence. It should not be altered.

The dot notation is also something new to me. Maybe others would give more details about it...

It looks like it's working like a namespaced external variable that is defined outside the function but is accessible to it.
But my experiments with it feels like it's not really restrictive or binding. It still works and used like a normal global variable and other functions can access and modify it.
The only difference seems to be the need to use the global keyword is not necessary for the dot variable.
More like a reminder to the programmer as to which function is working with it, (like python's underscored 'private' variables, which are not actually private, but just a code convention)

https://code.sololearn.com/cJSI9yO7cKSZ/?ref=app

Answer 10

Tibor Santa
it's always ideals vs reality. We strive for perfection but always have to make do with good enough. That's why Rust have the unsafe trait. The external environment and design requirement is not always ideal. Risks and uncertainty are sometimes unavoidable, or fast is not fast enough.

Like in game engines. corners are cut and shortcuts are taken. mutation is the name of the game. it's really a use case where pure functions would be a bad fit. But in systems where security and predictability is important, you will need explicit and repeatable results for every process. Using pure functions would be a very good idea here.

It's not my intent to be argumentative. I just feel that paradigms are just theoretical ideals, but reality is what we have deal with. Sticking to one is limiting your options. Code is ephemeral and its lifetime is finite. Good enough is often the goal. If it gets the job done, then our work is done.

ok, maybe we are derailing this topic..👍