Chapter 25 Memoization

In the previous example, known is created outside the function, so it belongs to the special frame called __main__. Variables in __main__ are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next.

It is common to use global variables for flags; that is, boolean variables that indicate (“flag”) whether a condition is true. For example, some programs use a flag named verbose to control the level of detail in the output:

If you try to reassign a global variable, you might be surprised. The following example is supposed to keep track of whether the function has been called:

But if you run it you will see that the value of been_called doesn’t change. The problem is that example2 creates a new local variable named been_called. The local variable goes away when the function ends, and has no effect on the global variable.

To reassign a global variable inside a function you have to declare the global variable before you use it:

The global statement tells the interpreter something like, “In this function, when I say been_called, I mean the global variable; don’t create a local one.”

Here’s an example that tries to update a global variable:

If you run it you get:

Python assumes that count is local, and under that assumption you are reading it before writing it. The solution, again, is to declare count global.

If a global variable refers to a mutable value, you can modify the value without declaring the variable:

So you can add, remove and replace elements of a global list or dictionary, but if you want to reassign the variable, you have to declare it:

Global variables can be useful, but if you have a lot of them, and you modify them frequently, they can make programs hard to debug.

As you work with bigger datasets it can become unwieldy to debug by printing and checking the output by hand. Here are some suggestions for debugging large datasets:

Scale down the input:

If possible, reduce the size of the dataset. For example if the program reads a text file, start with just the first 10 lines, or with the smallest example you can find. You can either edit the files themselves, or (better) modify the program so it reads only the first n lines.

If there is an error, you can reduce n to the smallest value that manifests the error, and then increase it gradually as you find and correct errors.

Check summaries and types:

Instead of printing and checking the entire dataset, consider printing summaries of the data: for example, the number of items in a dictionary or the total of a list of numbers.

A common cause of runtime errors is a value that is not the right type. For debugging this kind of error, it is often enough to print the type of a value.

Write self-checks:

Sometimes you can write code to check for errors automatically. For example, if you are computing the average of a list of numbers, you could check that the result is not greater than the largest element in the list or less than the smallest. This is called a “sanity check” because it detects results that are “insane”.

Another kind of check compares the results of two different computations to see if they are consistent. This is called a “consistency check”.

Format the output:

Formatting debugging output can make it easier to spot an error. We saw an example in Section 10.1. Another tool you might find useful is the pprint module, which provides a pprint function that displays built-in types in a more human-readable format (pprint stands for “pretty print”).

Again, time you spend building scaffolding can reduce the time you spend debugging.

mapping:

A relationship in which each element of one set corresponds to an element of another set.

dictionary:

A mapping from keys to their corresponding values.

key-value pair:

The representation of the mapping from a key to a value.

item:

In a dictionary, another name for a key-value pair.

key:

An object that appears in a dictionary as the first part of a key-value pair.

value:

An object that appears in a dictionary as the second part of a key-value pair. This is more specific than our previous use of the word “value”.

implementation:

A way of performing a computation.

hashtable:

The algorithm used to implement Python dictionaries.

hash function:

A function used by a hashtable to compute the location for a key.

hashable:

A type that has a hash function. Immutable types like integers, floats and strings are hashable; mutable types like lists and dictionaries are not.

lookup:

A dictionary operation that takes a key and finds the corresponding value.

reverse lookup:

A dictionary operation that takes a value and finds one or more keys that map to it.

raise statement:

A statement that (deliberately) raises an exception.

singleton:

A list (or other sequence) with a single element.

call graph:

A diagram that shows every frame created during the execution of a program, with an arrow from each caller to each callee.

memo:

A computed value stored to avoid unnecessary future computation.

global variable:

A variable defined outside a function. Global variables can be accessed from any function.

global statement:

A statement that declares a variable name global.

flag:

A boolean variable used to indicate whether a condition is true.

declaration:

A statement like global that tells the interpreter something about a variable.