In Python the function decorator is used to realize the memo function

The definition of "memo"

Memoization was coined by Donald Michie in 1968 and is based on the Latin word "memorandum" which means "to be remembered". Although it bears some resemblance to the word "memorization", it is not a misspelling of the word. Memoisation is actually a technique for computing to speed up a program by remembering the calculated result of an input, such as the result of a function call. If you encounter the same input or a function call with the same parameters, the previously stored results can be reused to avoid unnecessary calculations. In many cases, you can use a simple array to store the results, but you can also use many other data structures, such as associative arrays, called hashes in Perl and dictionaries in Python.

Memos can be explicitly programmed by programmers, but some programming languages, such as Python, provide a mechanism for automatic memos.
Use function decorator to realize memo function

In the previous chapter on (link: http://www.python-course.eu/python3_recursive_functions.php), we solved the Fibonacci sequence using iteration and recursion, respectively. We have proved that if we directly use the mathematical definition of Fibonacci sequence to solve the sequence in a recursive function, as the following function does, it will have exponential time complexity:
 

def fib(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

In addition, we propose a method to improve the time complexity of recursive implementation by adding a dictionary to remember the calculation results of previous functions. This is an example of an explicit use of the memo technique, although we didn't call it that at the time. The downside of this approach is that the clarity and elegance of the original recursive implementation is lost.

The reason for the above shortcomings is that we changed the code for the recursive function fib. However, the following code does not change our fib function, so its clarity and readability are not lost. For this purpose, we use a custom function memoize(). The function memoize() takes the function as an argument and USES a dictionary memo to store the result of the function. Although the variable memo and the function f only have partial memo functionality, they are captured by a closure through a function helper, which memoize() returns as a reference. So a call to memoize(fib) will return a reference to a helper(), which implements the functionality of the fib() function and a wrapper for storing results that are not yet stored in the dictionary memo, and prevents recalculation of existing results in memo.
 

def memoize(f):
  memo = {}
  def helper(x):
    if x not in memo:      
      memo[x] = f(x)
    return memo[x]
  return helper
 
def fib(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)
 
fib = memoize(fib)
 
print(fib(40))

Now let's take a look at the so-called decorator, starting with the line in the above code that assigns the memo function to the fib function:
 

fib = memoize(fib)

One way to say it is that the function memoize() decorates the function fib.
Encapsulate Memoize into a class

We can also wrap the cache of the results into a class, as shown in the following example:

 class Memoize:
  def __init__(self, fn):
    self.fn = fn
    self.memo = {}
  def __call__(self, *args):
    if args not in self.memo:
  self.memo[args] = self.fn(*args)
    return self.memo[args]

Because we are using a dictionary, we cannot use mutable arguments, which must be immutable.
Decorator in Python

An decorator in Python is a callable Python object that modifies the definition of a function, method, or class. The original object, the one to be changed, is passed as an argument to a decorator, which returns a modified object, such as a modified function, bound to the name used in the definition. Decorators in Python have a similar syntax to annotations in Java, that is, decorators in Python can be thought of as pure syntactic sugar, using "@" as the keyword.
Example: implement the memo function using decorator

In fact, we have used decorator before, just not so called it. In fact, the memoize function in the example at the beginning of this chapter is just a decorator that we use to remember the result of the fib function, except that we don't use the special syntax of decorators in Python, which is the @ character "@".

Instead of writing it in the following form
 

fib = memoize(fib)

We could write it like this
 

@memoize

But this line must be written directly before the decorated function, in our example fib(), as follows:
 

def memoize(f):
  memo = {}
  def helper(x):
    if x not in memo:      
      memo[x] = f(x)
    return memo[x]
  return helper
 
@memoize
def fib(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)
 
#fib = memoize(fib)
 
print(fib(40))

Use decorator to check parameters

In the chapter on recursive functions we introduced the factorial function, where we wanted to keep the function as simple as possible without covering up the basic idea, so the code didn't include any argument checking code. However, if someone called our function with a negative number or a floating point number as an argument, the function would be stuck in a dead loop.

The following program USES an decorator function to ensure that the argument passed to the function "factorial" is a positive integer:
 

def argument_test_natural_number(f):
  def helper(x):
    if type(x) == int and x > 0:
      return f(x)
    else:
      raise Exception("Argument is not an integer")
  return helper
 
@argument_test_natural_number
def factorial(n):
  if n == 1:
    return 1
  else:
    return n * factorial(n-1)
 
for i in range(1,10):
  print(i, factorial(i))
 
print(factorial(-1))

practice

Our exercise is an old riddle. In 1612, the French jesuit Claude Gaspar Bachet came up with the puzzle of using a scale to find the minimum number of weights (e.g., sugar or flour) for all integer weights from 1 pound to 40 pounds.

The first method might be to use weights of 1, 2, 4, 8, 16, and 32 pounds. If we place weights on one end of the scale and objects on the other, the number of weights used in this method will be minimal. However, we can also place the weights on both ends of the scale at the same time. In this case, we only need weights of 1, 3, 9, and 27.

Write a Python function called weigh(), which calculates the required weights and their distribution on the scale to weigh any integer weight from 1 pound to 40 pounds.
The solution

1. We need the function linear_combination() from the previous section, "(link: http://www.python-course.eu/linear_combinations.php)."
 

def factors_set():
  factors_set = ( (i,j,k,l) for i in [-1,0,1]
             for j in [-1,0,1]
             for k in [-1,0,1]
             for l in [-1,0,1])
  for factor in factors_set:
    yield factor
 
def memoize(f):
  results = {}
  def helper(n):
    if n not in results:
      results[n] = f(n)
    return results[n]
  return helper
 
@memoize
def linear_combination(n):
  """ returns the tuple (i,j,k,l) satisfying
    n = i*1 + j*3 + k*9 + l*27   """
  weighs = (1,3,9,27)
 
  for factors in factors_set():
    sum = 0
    for i in range(len(factors)):
     sum += factors[i] * weighs[i]
    if sum == n:
     return factors

Using the code above, we can easily write our function weigh().
 

def weigh(pounds):
  weights = (1,3,9,27)
  scalars = linear_combination(pounds)
  left = ""
  right = ""
  for i in range(len(scalars)):
    if scalars[i] == -1:
      left += str(weights[i]) + " "
  elif scalars[i] == 1:
      right += str(weights[i]) + " "
  return (left,right)
 
for i in [2,3,4,7,8,9,20,40]:
  pans = weigh(i)
  print("Left pan: " + str(i) + " plus " + pans[0])
  print("Right pan: " + pans[1] + "n")