In this article, we will be discussing a common technique in Python known as memorization. This technique allows us to cache results and significantly speed up our functions. If we have a function that takes 30 seconds to execute, memorization can help it take less than a second. I'll explain how it works and provide an example of how it can save us time. So, let's jump right into it!
Fibonacci Number WIthout Memoization
from functools import wraps
from time import perf_counter
import sys
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
if __main__ == '__main__':
start = pref_counter()
f = fibonacci(36)
end = pref_counter()
print(f)
print("Time: {} seconds".format(end - start))
### Output
14930352
Time: 1.834435466346 seconds
Fibonacci Number WIth Memoization
from functools import wraps
from time import perf_counter
import sys
def memorize(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]
@memorize
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
if __main__ == '__main__':
start = pref_counter()
f = fibonacci(36)
end = pref_counter()
print(f)
print("Time: {} seconds".format(end - start))
### Output
14930352
Time: 4.234435466346-05 seconds
Frequently Asked Questions (FAQs) about Memoization
- Is memoization better than DP?
Memoization is the top-down approach to solving a problem with dynamic programming. It’s called memoization because we will create a memo for the values returned from solving each problem.
- Is memoization the same as caching?
Memoization is a specific type of caching. Caching can generally refer to any storing technique (like HTTP caching) for future use, but memoizing refers more specifically to the caching function that returns the value.
- Why memoization is top-down?
The top-down approach breaks the large problem into multiple subproblems. if the subproblem is solved already then reuse the answer. Otherwise, Solve the subproblem and store the result in some memory.
- Does memoization use recursion?
Memoization follows a top-down approach to solving the problem. It consists of recursion and caching. In computation, recursion represents the process of calling functions repeatedly, whereas cache refers to the process of storing intermediate results.
- Should I use tabulation or memoization?
For problems requiring all subproblems to be solved, tabulation typically outperforms memoization by a constant factor. This is because the tabulation has no overhead of recursion which reduces the time for resolving the recursion call stack from the stack memory.
Whenever a subproblem needs to be solved for the original problem, memoization is preferable since a subproblem is solved lazily, i.e. only the required computations are carried out.
- Where is memoization used?
Memoization is an optimization technique used to speed up computer programs by caching the results of expensive function calls and returning them when the same inputs are reencountered.
- Why is it called memoization?
The term “memoization” comes from the Latin word “memorandum” (“to remember”), which is commonly shortened to “memo” in American English, and which means “to transform the results of a function into something to remember.”.
- How does memoization reduce time complexity?
Solving the same problem again and again takes time and increases the run-time complexity of the overall program. This problem can be resolved by maintaining some cache or memory where we will store the already calculated result of the problem for some particular input. So that if we don’t want to recalculate the same problem, we can simply use the result that is stored in the memory and reduce the time complexity.
- What is the difference between memorization and caching?
Memoization is a specific type of caching that involves caching the return value of a function based on input. Caching is a more general term. For example, HTTP caching is caching but it is not memorization.
By the way…
Call to action
Hi, Everydaycodings— I’m building a newsletter that covers deep topics in the space of engineering. If that sounds interesting, subscribe and don’t miss anything. If you have some thoughts you’d like to share or a topic suggestion, reach out to me via LinkedIn or X(Twitter).
References
And if you’re interested in diving deeper into these concepts, here are some great starting points:
Kaggle Stories - Each episode of Kaggle Stories takes you on a journey behind the scenes of a Kaggle notebook project, breaking down tech stuff into simple stories.
Machine Learning - This series covers ML fundamentals & techniques to apply ML to solve real-world problems using Python & real datasets while highlighting best practices & limits.