Suppose our program needs to perform an operation that significantly increases execution time, and moreover, this operation must be performed repeatedly. If the operation is deterministic — meaning that for the same input data or request it always produces the same output or response — then we can apply a technique called memoization. In essence, this means that once we compute the result for a given request, we store it in memory. Then, when the same request occurs again, instead of performing the time-consuming operation once more, we simply return the value already stored in memory.
In other words, memoization essentially converts time consumption into memory consumption.
The more frequently the same inputs need to be processed, the greater the improvement in execution time this technique can provide (while requiring relatively little excess memory).
Memoization can be implemented in several ways. One common approach is to use a closure. The following example demonstrates this technique.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
from time import sleep def power_function_factory(q): """Return a function that calculates powers of q.""" power_values = [] def _power(n:int): # If the value corresponding to n has already been stored, we return it. # If not — meaning that the element at index n of the list used for storage does not yet exist — # then we calculate the value, store it, and return it. try: return power_values[n] except IndexError: sleep(0.2) # Simulating longer execution time y = q**n power_values.append(y) return y return _power # TEST # Creating a function that returns powers of 2. power2 = power_function_factory(2) # When requesting a value for the first time, it takes noticeable time to calculate it. for i in range(10): print(power2(i), end = ' ') print() # Result: 1 2 4 8 16 32 64 128 256 512 # However, if we later request the same values again, we receive them almost instantly. # Of course, values that have not yet been calculated still take time to compute, but # afterward they are also returned quickly. for i in range(11): print(power2(i), end = ' ') # Result: 1 2 4 8 16 32 64 128 256 512 1024 |
For the sake of simplicity and clarity, the closure function presented here calculates integer powers, where the base of the exponentiation is determined by the argument q passed to the enclosing function. Since exponentiation itself is not particularly slow, we simulate a noticeable increase in execution time by using the sleep() function from the time module of Python’s standard library. The duration of the delay must be specified as the function’s argument in seconds.
The computed power values are stored in a list, referenced by a local variable of the enclosing function. As we know (discussed in an earlier article), the closure function can access the value of this local variable anywhere in the program where the closure function is invoked. If the power value for a given integer has not yet been stored, the function calculates it and saves it in the list. If a value is already stored at the corresponding index, the function simply returns it.
This example is intended only to demonstrate the principle. There are still some details to consider regarding memoization and its implementation. These topics are covered in greater depth in the e-book “Python Knowledge Building Step by Step from the Basics to the First Desktop Application”, especially in the chapters “Exchanging Time for Storage Space – Memoization to Decrease Execution Time” and “Support for Memoization.”