The Decorator and Strategy Patterns

Strategy Pattern

You are using the Strategy pattern in Homework 8 without knowing it.

Defining distance

One part of the analysis for Homework 8 is about defining the distance between train stations. There is the basic measure of Euclidean distance, which we use in the code, but there are many more definitions of distance.

For example, we could say, "the station is 15 minutes from here," and that would be a meaningful distance. In that case, we would be defining the distance as the number of minutes it takes to travel between the two nodes.

We also explore defining the distance between two stations as the financial cost of building the track between them (which is bigger if we have to dig a tunnel underwater or through a mountain), or defining it as as 1/n, where n is the number of passengers who regularly travel between the two stations.

Strategy Pattern

So, we have many definitions of distance, and the same algorithm can use any of these distance definitions.

Suppose we want to write an algorithm to find the shortest path between two physical locations, but using a definition of distance that is chosen by the user at run time. For example, the user might choose that they want the path that takes the least time, or the one that makes the fewest greenhouse gas emissions. To efficiently write a program that performs the algorithm to solve this problem, we need to allow the definition of distance to be chosen at runtime. The Strategy Pattern solves this problem.

The Strategy Pattern (also known as the Duration Pattern) allows us to choose an algorithm at runtime.

Example: Strategies for playing Tic Tac Toe

• Place a third piece in a row to win
• Block the opponent if they're about to win
• Place in an open corner
• Place in any open square The strategy for choosing a place changes based on the game state.

Example: maps directions

• Shortest path
• Shortest time
• Least emissions
• Least tolls
• Maximize sightseeing The user chooses the path-finding algorithm at runtime.

Poll: How could the Strategy Pattern be used to define multiple definitions of distance in Homework 8 (public transportation MST)?

1. Ignore the distances between stations when building the train track system (assume all stations are equidistant)
2. Take user input to choose between multiple existing implementations of the distance() function (which returns the distance between two stations)
3. Take user input to choose between multiple existing implementations of Kruskal's Algorithm (which builds a Minimum Spanning Tree)
4. After the train track system is built, allow passengers to choose where they want to travel using the trains.

Function Decorators

We have already seen some decorators:

• @property (to create a property named after the method)
• *.setter (to give that property a "setter" method)
• @classmethod (for setUpClass(cls) and tearDownClass(cls) to run once before / after unit testing)

In this lecture, we will find out how these decorators were implemented, and how we can create our own decorators.

Functions are objects that can be stored in mutable variables

As we already know, in Python, functions are objects. We can reference them using variables, store them in lists, and pass them as arguments to other functions:

from typing import Callable

def double(num: int) -> int:
    return num * 2

def triple(num: int) -> int:
    return num * 3

functions: list[Callable[[int], int]] = [double, triple]

def apply_functions(num: int) -> list[int]:
    return [func(num) for func in functions]

print(apply_functions(5))  # [10, 15]

Creating a function decorator

A function decorator is a way to mutate a function's variable to modify what it does.

For example, let's create a decorator called @time_calls that modifies a given function to print the time it took to run it like this:

@time_calls
def multiply_list(nums: list[int], multiplier: int = 1) -> list[int]:
    return [num * multiplier for num in nums]

print(multiply_list([i for i in range(5)], multiplier = 3))

Because we modified multiply_list() to do what @time_calls tells it to do, this is the printed output:

Executed multiply_list with ([0, 1, 2, 3, 4],) and {'multiplier': 3} in 7.152557373046875e-06ms
[0, 3, 6, 9, 12]

This is how we created the @time_calls decorator to work like that:

def time_calls(func: Callable[..., Any]) -> Callable[..., Any]:
    def wrapper(*args: Any, **kwargs: Any) -> Any:
        now = time.time()
        return_value = func(*args, **kwargs)
        print(f'Executed {func.__name__} with {args} and {kwargs} in {time.time() - now}ms')
        return return_value
    return wrapper

We defined a function called time_calls() that takes a function as its argument and returns a function.

The function that it returns is a modified version of the function that is passed to it as an argument.

That modification is that, in addition to running the passed function as usual, it prints the number of milliseconds that it took to run it.

All that is needed for the @time_calls decorator to work is this definition of the time_calls() function (somewhere in the file before the decorator is used).

Poll: What does the @mystery decorator do?

T = TypeVar('T')

def mystery(func: Callable[[float], T]) -> Callable[[float], T]:
    def wrapper(x: float) -> T:
        if x < 0:
            raise ValueError("Argument must be positive")
        return func(x)
    return wrapper

@mystery
def square_root(x: float) -> Any:
    return x ** 0.5

print(square_root(9))

1. Modifies the function to print the number of milliseconds it took to run it
2. Modifies the function such that it raises a ValueError if the argument is negative
3. Modifies the function to run it twice
4. Nothing

A common use of decorators: caching

Caching is temporarily storing values that are recalculated often (so they only need to be calculated once). For example, consider the function where we find the nth Fibonacci number:

def fibonacci(n: int) -> int:
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

In order to calculate the 5th Fibonacci number, we need to calculate the 4th and 3rd ones. And to calculate the 4th number, we need to calculate the 3rd and 2nd ones. And to calculate the 3rd number, we need to calculate the 2nd and 1st ones... There are a lot of recalculated numbers here.

So, let's write some code that stores each Fibonacci number the first time it is calculated, so that each subsequent time, we can just look it up rather than recalculating it.

(Write this example together, then step through it with the debugger)

R = TypeVar('R')

def cache(func: Callable[..., R]) -> Callable[..., R]:
    storage: dict[tuple[Any, ...], R] = {}
    def wrapper(*args: Any) -> R:
        if args in storage:
            return storage[args]
        result = func(*args)
        storage[args] = result
        return result
    return wrapper

@cache
def fibonacci(n: int) -> int:
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

Poll: Can we re-use the @cache decorator to perform caching for other functions in the same file?

1. Yes
2. Yes, but that other function would share the "cache" of stored values, which are specific to Fibonacci
3. No, it would not run

Easiest way to test this: create a duplicate method called fibonacci2(), decorate it, call it after the regular fibonacci(), and step through it in the debugger.

Example where caching helps a language model (BERT) run faster

This is a Python Notebook in Google Colab. Each cell block needs to be run individually. Code is executed in the order that the cell blocks are executed, so it is possible for something lower down in the file to be run before something above it in the file.

https://colab.research.google.com/drive/1mFWNiRTlctAUOQPZs_CdvMW_OF2Rgkzh?usp=sharing