Python
  11.2 Functions:   
Decorators &
Memoization

A thorough reference for this section is: decorators-in-12-steps (local copy). There are a number of such online references, and this is a good one. It allows you to understand Section 11.2.3, but not 11.2.4. Books almost never devote pages enough for understanding.

11.2.1 Timing a Function: As initial examples, I'm measuring the execution time of functions. These examples lead to the more elegant decorators.

So first suppose we want to measure the time a function takes to execute. Consider the following program:

Determine Execution Time: timer function
# timer0.py: time Gregory's Series
import sys
import time

def timer(func, n):  # wall-clock time
    start = time.time()
    result = func(n)
    end = time.time()
    sys.stdout.write("func=" + func.__name__ +
      ", args=" + str(n) +
      ", time=" + str(end - start) + ", res=")
    return result

def g(n):        # Gregory's Series
    sum  = 0.0   # final sum
    sign = 1.0   # sign on each term
    for k in range(0,n):
        term = 1.0/(2.0*k + 1.0)
        sum = sum + sign*term
        sign = -sign
    return sum*4.0
result = timer(g, 5000000)
sys.stdout.write(str(result)+'\n')
Output
func=g,args=5000000,time=6.152,res=3.14159245359
    Items of interest or for study:
  • The function timer is executed with the function g (calculate Gregory's series) as an actual parameter, as well as g's formal parameter n as an actual parameter of timer. It gets the start time, calls g(n), saves the return value, and gets the end time, so that end - start gives the execution time. Finally it returns the value returned when g(n) is called.

  • Code like this is possible in C (passing a pointer to a function), but not in Java.

  • We are measuring elapsed (wall-clock) time and not CPU time.

  • Because this is Python, the timer0.py code at the left would work with any function that has a single parameter, without worrying about the type of the parameter. In the same way, the object returned could be anything that can be printed.

Next let's look at a more general approach:

Determine Execution Time: timer1 module
# timer1.py: clock time of a function
import sys
import time

def timer(func, *args):  # wall-clock time
    start = time.time()
    result = func(*args)
    end = time.time()
    sys.stdout.write("func=" + func.__name__ +
      ", args=" + str(args) +
      ", time=" + str(end - start) + ", res=")
    return result
Test timer1 module
# timer1_test.py: test the timer module
import sys
from timer1 import timer

def g(n):        # Gregory's Series
    sum = 0.0    # final sum
    sign = 1.0   # sign on each term
    for k in range(0,n):
        term = 1.0/(2.0*k + 1.0)
        sum = sum + sign*term
        sign = -sign
    return sum*4.0
result = timer(g, 5000000)
sys.stdout.write(str(result)+'\n')

def c(n, k): # combinations
    if n == k or k == 0:
        return 1
    return c(n-1, k-1) + c(n-1, k)
result = timer(c, 24, 12)
sys.stdout.write(str(result)+'\n')
Output
func=g,args=(5000000,),time=6.767,res=3.14159245359
func=c,args=(24, 12),  time=5.441,res=2704156
    Items of interest or for study:
  • The code at the left uses the *args features from the previous section: 11.1 Functions: Intro.

  • This will handle any kind of Python parameter list not including keyword parameters. And even keyword parameters can be handled by adding **kwargs after the *args.

  • There are two kinds of parameters at the left: a single int and a pair of ints. Return values are a float and an int.

  • Important is that this example only needs the extra call to timer, but it works for any function.

  • This seems to be a satisfactory solution to the problem of timing a function using a wrapper without using a Python decorator. There is only the extra explicit call to the timer function. With decorators there would be the extra explicit inclusion of @timer.

  • This approach works even if the function being timed is recursive at the top level. The mimic decorators in the next section (11.2.2), and the real decorators in the section after that (11.2.3) won't work in such a case.

11.2.2 Decorators -- Behind the Curtain: The book Python Essential Reference by David Beazley describes decorators in Python with (page 101):

A decorator is a function whose primary purpose is to wrap another function or class. This wrapping is to transparently alter or enhance the behavior of the object being wrapped. Decorators are denoted using the special @ symbol:

@trace
def square(x)
    return x*x
  is shorthand for   
def square(x)
    return x*x
square = trace(square)

Notice that "trace(square)" replaces the original "square".



Mimic decorators:
no parameters


# timer_miimic0.py: mimic decorators
import sys
import time

def timer(func):
    start = time.time()
    result = func()
    end = time.time()
    sys.stdout.write("func=" +
      func.__name__ + ", time=" +
      str(end - start) + ", res=")
    return func

def g():         # Gregory's Series
    n = 1000000
    sum = 0.0    # final sum
    sign = 1.0   # sign on each term
    for k in range(0,n):
        term = 1.0/(2.0*k + 1.0)
        sum = sum + sign*term
        sign = -sign
    return sum*4.0
g = timer(g)
result = g()
sys.stdout.write(str(result) + '\n')



Output


func=g, time=1.103, res=3.14159165359
   
Mimic decorators: with parameters
# timer_mimic.py: mimics decorators
import sys
import time

def timer(func, *args):
    def callf(*args):
        start = time.time()
        result = func(*args)
        end = time.time()
        sys.stdout.write("func=" +
          func.__name__ + ", args=" +
          str(args) + ", time=" +
          str(end - start) + ", res=")
        return result
    return callf

def g(n):        # Gregory's Series
    sum = 0.0    # final sum
    sign = 1.0   # sign on each term
    for k in range(0,n):
        term = 1.0/(2.0*k + 1.0)
        sum = sum + sign*term
        sign = -sign
    return sum*4.0
g = timer(g)
result = g(1000000)
sys.stdout.write(str(result) + '\n')

def d(n, k):
    def c(n, k): # combinations
        if n == k or k == 0:
            return 1
        return c(n-1, k-1) + c(n-1, k)
    return c(n, k)
d = timer(d)
result = d(22, 11)
sys.stdout.write(str(result) + '\n')
                                         
Output
func=g, args=(5000000,), time=6.107, res=3.14159245359
func=c, args=(24, 12),   time=3.717, res=2704156

Items of interest or for study:

  • On the left above, I used Beasley's "shorthand" idea given above the code to mimic a version of decorators, without using any of the library decorator code. This works as it should without parameters.

  • I was unable to get the code at the left to work with a parameter.

  • The code on the right also mimics Python decorators, wrapping a functions that have parameter, in one case one parameter and in the other case two parameters. Here I copied Beazley, using the crazy function callf (the name has no significance) that is defined inside timer, but not called directly. Instead timer returns a reference to callf. Beazley says:

    The function callf that is returned from trace() is a closure that serves as a replacement for the original function.

    This is how decorators are implemented in Python. For details see the reference at the beginning of this page: decorators-in-12-steps (local copy).

11.2.3 Decorators: This section shows actual Python decorators.

Use decorator for execution time: timer module
# timer.py: decorator for execution time
import time
import sys
from functools import wraps

def timethis(func):
    '''
    Decorator that reports the execution time.
    '''
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        sys.stdout.write("func=" + func.__name__ +
          ", args=" + str(args) +
          ", time=" + str(end - start) + ", res=")
        return result
    return wrapper
Test timer module
# timer_test.py: time two different functions
import sys
from timer import timethis

@timethis
def g(n):
    sum = 0.0      # final sum
    sign = 1.0     # sign on each term
    for k in range(0,n):
        term = 1.0/(2.0*k + 1.0)
        sum = sum + sign*term
        sign = -sign
    return sum*4.0
result = g(5000000)
sys.stdout.write(str(result)+'\n')

@timethis
def d(n, k):
    def c(n, k):
        if n == k or k == 0:
            return 1
        return c(n-1, k-1) + c(n-1, k)
    return c(n, k)
result = d(24, 12)
sys.stdout.write(str(result)+'\n')
Output
func=g, args=(5000000,), time=6.048, res=3.14159245359
func=c, args=(24, 12),   time=3.767, res=2704156
    Items of interest or for study:
  • The stuff in this section is syntactic sugar for what was in the previous section.

  • The examples in this section use the library module functools that implements decorators. Here we still have the weird return of a reference to the wrapper() function, but this part mostly has magic unexplained code. (See the reference to decorators at the start of this whole page.)

  • This approach doesn't allow a recursive function to be wrapped at the top level, so the recursive c( ) is called from non-recursive d( ).

11.2.4 Memoization: Here is a more complicated example that performs memoization on an arbitrary function (as long as its parameter list is "hashable"). In this case the decorator is a class. This part is not explained here (yet).

Memoization is a big deal in functional programming. Some functional languages do memoization as part of the optimization for execution, as for example in Lisp. For Python, see for example: Memoization in Python.

The example below came from: Python Decorator Library. See also: functools: Higher-order functions and operations on callable objects -- very heavy-duty stuff.

The page about the Partition function p(n) shows a simple example where Python code for the function p(n) is memoized directly by hand so that it will execute efficiently.

Class decorator for memoization + testing
# memoized.py: the class for memoization
import collections
import functools
import sys

class memoized(object):
    '''Decorator. Caches a function's return value
    each time it is called.  If called later with
    the same args, the cached value is returned
    (not reevaluated).
    '''
    def __init__(self, func):
        self.func = func
        self.cache = {}
    def __call__(self, *args):
        if not isinstance(args,collections.Hashable):
            # uncacheable. a list, for instance.
            return self.func(*args)
        if args in self.cache:
            return self.cache[args]
        else:
            value = self.func(*args)
            self.cache[args] = value
            # print '(', args, ',', value, ')'
            return value
    def __repr__(self):
        '''Return the function's docstring.'''
        return self.func.__doc__
    def __get__(self, obj, objtype):
        '''Support instance methods.'''
        return functools.partial(self.__call__, obj)

# mem_fib.py: test Fibonacci nums
from memoized import memoized
@memoized
def fibon(n):
    '''Return nth fib number.'''
    if n in (0, 1):
        return n
    return fibon(n-1) + fibon(n-2)
print fibon(12)
# mem_comb.py: test comb
from memoized import memoized
@memoized
def c(n, k): # combinations
    if n == k or k == 0:
        return 1
    return c(n-1, k-1) + c(n-1, k)
print '\n', c(100, 50)
# mem_part.py: test partition
from memoized import memoized
@memoized
def p(n):
    if n < 0:
        return 0
    if n == 0 or n == 1:
        return 1
    sign = 1
    res = 0
    for k in range(1, n+1):
        term = p(n-k*(3*k-1)/2)+\
          p(n - k*(3*k + 1)/2)
        res = res + sign*term
        sign = -sign
    return res
print '\n', p(10)

Output: final value + items inserted into dictionary
% mem_fib.py
( (1,) , 1 )
( (0,) , 0 )
( (2,) , 1 )
( (3,) , 2 )
( (4,) , 3 )
( (5,) , 5 )
( (6,) , 8 )
( (7,) , 13 )
( (8,) , 21 )
( (9,) , 34 )
( (10,) , 55 )
( (11,) , 89 )
( (12,) , 144 )
144
% mem_comb.py
( (3, 0) , 1 )
( (2, 0) , 1 )
( (1, 0) , 1 )
( (1, 1) , 1 )
( (2, 1) , 2 )
( (3, 1) , 3 )
( (4, 1) , 4 )
( (2, 2) , 1 )
( (3, 2) , 3 )
( (4, 2) , 6 )
( (5, 2) , 10 )
( (3, 3) , 1 )
( (4, 3) , 4 )
( (5, 3) , 10 )
( (6, 3) , 20 )
20

% mem_part.py
( (1,) , 1 )
( (0,) , 1 )
( (-3,) , 0 )
( (-5,) , 0 )
( (2,) , 2 )
( (-2,) , 0 )
( (-4,) , 0 )
( (-9,) , 0 )
( (-12,) , 0 )
( (3,) , 3 )
( (-1,) , 0 )
( (-8,) , 0 )
( (-11,) , 0 )
( (-18,) , 0 )
( (-22,) , 0 )
( (4,) , 5 )
( (-7,) , 0 )
( (-10,) , 0 )

( (-17,) , 0 )
( (-21,) , 0 )
( (-30,) , 0 )
( (-35,) , 0 )
( (5,) , 7 )
( (-6,) , 0 )
( (-16,) , 0 )
( (-20,) , 0 )
( (-29,) , 0 )
( (-34,) , 0 )
( (-45,) , 0 )
( (-51,) , 0 )
( (6,) , 11 )
( (-15,) , 0 )
( (-19,) , 0 )
( (-28,) , 0 )
( (-33,) , 0 )
( (-44,) , 0 )
( (-50,) , 0 )

( (-63,) , 0 )
( (-70,) , 0 )
( (7,) , 15 )
( (-14,) , 0 )
( (-27,) , 0 )
( (-32,) , 0 )
( (-43,) , 0 )
( (-49,) , 0 )
( (-62,) , 0 )
( (-69,) , 0 )
( (-84,) , 0 )
( (-92,) , 0 )
( (8,) , 22 )
( (-13,) , 0 )
( (-26,) , 0 )
( (-31,) , 0 )
( (-42,) , 0 )
( (-48,) , 0 )
( (-61,) , 0 )
( (-68,) , 0 )

( (-83,) , 0 )
( (-91,) , 0 )
( (-108,) , 0 )
( (-117,) , 0 )
( (9,) , 30 )
( (-25,) , 0 )
( (-41,) , 0 )
( (-47,) , 0 )
( (-60,) , 0 )
( (-67,) , 0 )
( (-82,) , 0 )
( (-90,) , 0 )
( (-107,) , 0 )
( (-116,) , 0 )
( (-135,) , 0 )
( (-145,) , 0 )
( (10,) , 42 )
42

Items of interest or for study:

(Revision date: 2015-06-30. Please use ISO 8601, the International Standard.)