5.1. Case Study: Memoize
5.1.1. Environment
Date: 2024-07-11
Python: 3.12.4
IPython: 8.26.0
System: macOS 14.5
Computer: MacBook M3 Max
CPU: 16 cores (12 performance and 4 efficiency) / 3nm
RAM: 128 GB RAM LPDDR5
5.1.2. Recap
Recap information about factorial (n!):
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
factorial(5) # = 120
return 5 * factorial(4) # 5 * 24 = 120
return 4 * factorial(3) # 4 * 6 = 24
return 3 * factorial(2) # 3 * 2 = 6
return 2 * factorial(1) # 2 * 1 = 2
return 1 * factorial(0) # 1 * 1 = 1
return 1 # 1
5.1.3. No Cache
>>> def factorial(n: int) -> int:
... return 1 if n == 0 else n * factorial(n-1)
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
4.85 μs ± 237 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.4. Global Scope
>>> _cache = {}
>>>
>>> def cache(func):
... def wrapper(n):
... if n not in _cache:
... _cache[n] = func(n)
... return _cache[n]
... return wrapper
>>> @cache
... def factorial(n: int) -> int:
... return 1 if n == 0 else n * factorial(n-1)
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
114 ns ± 25.4 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.5. Local Scope
>>> def cache(func):
... _cache = {}
... def wrapper(n):
... if n not in _cache:
... _cache[n] = func(n)
... return _cache[n]
... return wrapper
>>> @cache
... def factorial(n: int) -> int:
... return 1 if n == 0 else n * factorial(n-1)
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
113 ns ± 25.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.6. Embedded Scope
>>> def cache(func):
... def wrapper(n):
... if n not in wrapper.cache:
... wrapper.cache[n] = func(n)
... return wrapper.cache[n]
... if not hasattr(wrapper, 'cache'):
... setattr(wrapper, 'cache', {})
... return wrapper
>>> @cache
... def factorial(n: int) -> int:
... return 1 if n == 0 else n * factorial(n-1)
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
187 ns ± 37.7 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.7. Contains
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n not in _cache:
... _cache[n] = 1 if n == 0 else n * factorial(n-1)
... return _cache[n]
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
107 ns ± 27.7 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.8. Get
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... result = _cache.get(n)
... if result:
... return result
... if n == 0:
... return 1
... else:
... result = _cache[n] = n * factorial(n-1)
... return result
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
107 ns ± 18.6 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.9. Exceptions 1
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n == 0:
... return 1
... try:
... return _cache[n]
... except KeyError:
... _cache[n] = result = n * factorial(n-1)
... return result
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
105 ns ± 25.4 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.10. Exceptions 2
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... try:
... return _cache[n]
... except KeyError:
... _cache[n] = 1 if n == 0 else n * factorial(n-1)
... return _cache[n]
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
80.4 ns ± 15.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.11. Layer
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... def factorial(n: int) -> int:
... if n == 0:
... return 1
... return n * factorial(n-1)
... if not n in _cache:
... _cache[n] = factorial(n)
... return _cache[n]
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
229 ns ± 28.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
5.1.12. Get from cache
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n == 0:
... return 1
... if n in _cache:
... return _cache[n]
... result = _cache[n] = n * factorial(n-1)
... return result
>>>
... %%timeit -r 1000 -n 1000
... factorial(50)
... factorial(49)
... factorial(51)
153 µs ± 9.64 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
5.1.13. Assignment Expression
>>> # %%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n):
... if n == 0:
... return 1
... if (result := _cache.get(n)):
... return result
... result = n * factorial(n-1)
... _cache[n] = result
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
153 µs ± 9.64 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)