17.4. Case Study: Memoize

17.4.1. Environment

  • Date: 2024-07-11

  • Python: 3.12.4

  • IPython: 8.26.0

  • Computer: MacBook M3 Max, 16 cores (12 performance and 4 efficiency) / 3nm, 128 GB RAM LPDDR5

  • System: macOS 14.5

17.4.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

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)

17.4.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)