LRU_Cache stands for least recently used cache. I understand the value of any sort of cache is to save time by avoiding repetitive computing. Usually you store some computed value in a temporary place (cache) and look it up later rather than recompute everything. Functools is a built-in library within Python and there is a decorate lru_cache which is designed to help Python developers achieve similar goals.

So I have a dummy problem here, instead of the Fibonacci problem, it is even more exhaustive as the new item in the array need to be the sum of all its previous items plus 1. The level of complexity goes exponentially.

Clearly, by computing n = 24 is already taking more than 6 seconds. However, by decorating the function using the lru_cache, it is as quick as 4 millisecond. You can also find out the cache info, the sheer amount of hits is a the secret of why the function has been sped up so much.

The performance acceleration is outstanding and based on the definition of Dynamic programming, this is almost a necessity so developers can focus all their efforts into decomposing the problem into subproblems rather than worrying about manually storing hashtable somewhere for loop up.

Attached is an example of by using the lru_cache decorator, how you can come up with a solution that outperform 100% of the Python solutions out there from leetcode execution time and space wise.

If you are interested in looking under the hood, it isn’t quite complex as all the utilities are written in Python rather than Cython, however, developers are only supposed to access the lru_cache through clear_cache or cache_info because it is believed that messing with cache through an threaded environment will cause unnecessary trouble. I tried to access some of the its private and internally attributes but failed to access the cache due to the fact that cache lives within the namespace of the wrapper and it is not accessible outside the function. This might be an interesting challenge to understand how to get it working.