Using Python LRU Cache Decorator
Keep your friends close
Many functions (actually, all functions that do not depend on external input and randomness), when called with the same parameters, are expected to return the same values. For example, math.factorial(10)
is always 3_628_800 and math.sin(math.pi)
is always 1.2246467991473532e-16, at least for the same implementation of the floating-point library. Also, these functions may be quite time-consuming to call. In the spirit of Occam’s Razor, such expensive calls with expected values should not be repeated without necessity.
Let’s consider computing Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, …. The first two numbers are ones; each next number is the sum of its two immediate predecessors. For example, 13=5+8. An elegant function for calculating the n’th number can be defined recursively in the most straightforward way:
def fib(n):
return 1 if n in (0, 1) else fib(n - 1) + fib(n - 2)>>> fib(10)
89
>>> fib(20)
10946
>>> fib(30)
1346269
>>> fib(40)
KeyboardInterrupt
Oops. The last function call suddenly takes a ridiculous amount of time — so much, in fact, that I impatiently interrupted it with ^C. But perhaps it was a computer glitch or me seeing things on a hard day’s night? We can measure a function execution time using the module timeit
and the…