Programming Patterns in Python

Now that we have an understanding of how computers organize data and have some low level programming operations, let's look at a few common high-level programming patterns. Each of these operations has an implementation using conditional and loop patterns, which we can very easily express using python syntax. We can also use existing library functions to achieve the same thing, which we'll explore also.

As we go through, you will see that program design and coding are a game of word association. A high-level operation, such as map, should trigger a pseudocode (English-like "code") loop template in your mind, which should then trigger a for-each Python code template.

Keep in mind that we design programs by selecting and applying operations, not specific code sequences. Coding is the final act in the design process where we get an executable document. So, think visually about how you would manipulate lists of data or extract information from data. I often draw things out or put them into a spreadsheet to help me visualize. Manually moving some data around on paper helps me to understand the operations to perform.

After designing a sequence or combination of high-level operations, we can write things out in pseudocode or go straight to Python syntax. As you gain more experience, it will be easier to go straight from the operation to the code, but we still design programs using operations, not code, in our head. For complex problems, I still write out pseudocode, despite 35+ years coding experience.

Programming patterns

Programmers draw from a set of patterns or templates when choosing an overall program plan. The same is true of the individual operations themselves. Programmers have a catalog of common operations that they rely on when choosing the steps of a plan.

You're no doubt familiar with operations such as:

• sum the numbers in a list
• count the numbers in a list.

But we can abstract those further into:

• find all values in a list satisfying a condition
• apply an operation to each element in the list.
• ...

The more abstract the operation, the more widely applicable it is. The kinds of operations we use depends partly on a programmer's style but is heavily influenced by the capabilities of the programming language and its libraries of pre-existing functionality.

Data for exercises

We will be doing several small exercises as we go through this material. Please cut and paste this Python code into the notebook you are using.

Please try to do the exercises without looking at the solutions, which appear immediately below the exercise description.

Accumulate

Let's start with a very simple but extremely common pattern called accumulate. The pattern traverses a sequence of elements and accumulates a value. For example, to sum the numbers in a sequence, we use the accumulator operation with the + operator. As we traverse the sequence, we update a running sum that's initialized to 0:

In Excel, this is like using sum(...) in a cell. In Python, the implementation of this pattern has an initialization step and a loop:

We can use any other arithmetic operator we want, such as *. In fact, we can use any function that takes two operands and returns a new value. For summing, the two "input" numbers of the function are the previous accumulated value and the next value in the sequence. The result of that function is the new accumulated value. + and * are the most common operators.

You will also see this operation called reduce, as in map/reduce in the distributed computing world of Hadoop and Spark.

A counter is a special case of an accumulator that counts the number of elements in a sequence. It also uses the + operator but the two "input" numbers are the previous accumulated value and a fixed 1 value, not the next element in the sequence.

We can update multiple running accumulated values, not just one. For example, let's say we wanted to count the number of even and odd values in a sequence. We need two accumulator values, both starting at zero, but the operation is the same:

The +1 indicates an "add one to accumulated value" operation applied at each step but only if the current value is even or odd. In Python code, we'd do something like the following:

Map

Perhaps the most common operation maps one sequence to another, applying an operator or function to each element. (It's like an accumulator that accumulates a list of stuff instead of a single value.) For example, using a spreadsheet to create a new column containing the unit price discounted by 5% starts like this in a spreadsheet:

We can represent both lists at time 0 using list literals:

In other words:

The translation process in our heads from high-level operation to pseudocode to code is a game of word association". When your brain sees an operation that maps a column of data to another, think "map". When your brain hears "map" it should generate the appropriate pseudocode loop, filling in the pieces appropriately. When your brain hears "for each blah blah", think "oh, for-each loop" and use the appropriate coding pattern:

Notice that I have included the initialization of the empty list as part of this code snippet. The reason is that we really want to mentally associate the initialization with this code pattern.

Even at the microlevel, think about mapping operations to code. For example, when I think about "add x to list y", my brain translates that to y.append(x).

List comprehension for map operation

This is such a common pattern that Python has an explicit construct to make things easier. It's called a list comprehension and it's really just shorthand that looks more like mathematical set notation:

Exercise

Without looking at the code we just did, try to write the code out for a map operation using a list comprehension that divides the prices in half, again putting the values in Discounted. Don't cut/paste. Type!

Exercise

Given a list of names, ['Xue', 'Mary', 'Robert'], give code to implement a map operation that converts the names to list namelens containing the length of the names. Hint: Function call len('Xue') returns 3. Don't cut/paste. Type!

Combine

Let's look at the code pattern to traverse two lists at once placing the result in a third list. For example, to compute the cost of a sales transaction, we multiply the quantity times the unit price. In a spreadsheet, that looks like this:

Dragging that formula down the Cost column, applies the formula to the following rows, thus, filling the new column.

Programmatically, what we're doing is multiplying the ith element from two different sequences and placing the result in the ith position of the output sequence:

At time zero, we have the following data available:

When traversing more than a single list, we typically need to use an indexed loop rather than a for-each loop:

List comprehension for combine operation

Or, better yet, use a list comprehension:

Tricks for formatting:

Note that you might be tempted to use a double for-each loop in a list comprehension, but you get the cross product of each value in quantity times each value in your price. That's not what we want, as you can see here:

The zip function

We can also use zip, a very useful function that pulls one value from each list to make a tuple at each iteration:

Or, with a list comprehension:

Split

The opposite of combining is splitting where we split a stream into two or more new streams. For example, I often have to split the full names in a list into their first and last names. In a spreadsheet, we make a blank column:

and then split on the space character (In Excel, you use Data > Text to Columns) to get two new columns:

We could "undo" this split using a combine operation with the string concatenation operator, which would combine first and last names together into a new stream containing full names again.

Another common use of splitting is to take a string representing a string of numbers and split it into a list with those numbers:

We can even traverse a list to get a matrix (list of lists)

Slice

Most of the operations we've examined so far yield lists or sequences that have the same size as the input sequence, but there are many operations that yield subsets of the data. The first such operation is slice, which extracts a subset of a list. (Again, here I explicitly use the term list to indicate that slicing generally occurs on a data structure that fits in memory.)

The slice operation is a function of two values, a start and end position within a list.

Warning: Most languages and libraries assume the ending slice position is exclusive, which would mean slicing from the position 0 to position 3, in this case. To make matters more complicated, Python but not R, starts counting at 0 not 1. It's hard to switch back and forth between Python and R in this respect, so it's good to highlight here so you keep it in mind.

Filter

The most general operation used to extract data from a list or sequence is called filter. For example, using Excel's filter mechanism, we can filter a Shipping column for those values less than $10:

The filter operation is similar to the map operation in that a computation is applied to each element of the input stream. Map applies a function to each element of a sequence and creates a new sequence of the same size. Filter tests each element for a specific condition and, if true, adds that element to the new sequence.

A filter operation is just a map that conditionally adds elements to the target list:

List comprehension for filter operation

But, we should use instead a variation on the list comprehension seen in the pattern we have for the map operation:

We can also filter on one column but keep the data within each row together. Here is an example, using Excel, that filters Oscar winners from the list of nominees (the condition is winner equals 1):

The code for the looping construct looks like (jumping straight to the list comprehension form):

The output is a list of lists, a filtered table of rows one per movie.

Notice how we test one column value from the row, movie[2], but add the entire row to the new table. If we just added the "winner" column value to the new list, we would end up with a list of ones: 1, 1, 1, ..., 1.

Exercise

Filter the Oscars list into Oscars2 for all movies with 3-word titles. To break a string into a list of words, use title.split(' '). If the length, len(), of that list is 3, then copy the entire row to Oscars2.

Exercise

Rather than just referencing an iterate value, x, we can also use expressions in list comprehensions. Use the filtering variation of a list comprehension to double the shipping cost in Shipping if less than 10 dollars. Put the result in list Shipping2.

Exercise

Given a list of names=['Xue', 'Mary', 'Bob'], filter the list into names2 for those names starting with X. Recall that name[i] yields the ith character in name. Or use name.startswith(...).

Search

The filter operation finds all elements in a sequence that satisfy a specific condition, but often we'd like to know which element satisfies the condition first (or last). (Or, we often just need to know if a particular element is present.) This brings us to the search operation. At its most general, search returns the first (or last) position in the sequence rather than the value at that position. If we have the position, often called the index, we can always ask the sequence for the value at that position. If the element is not found, the search returns invalid index -1.

Searching is, in some sense, a variation on filtering. The difference is what we do when we find an element for which the condition is true. Instead of adding that element to the target list, a search bails out of the loop.

The break statement breaks out of the immediately-enclosing loop, regardless of the type of loop.

The search operation can even be used within a string (list of characters) to find the position of a character of interest. For example, to slice up a full name into first and last names, we can combine a search for the space character with two slice operations. Given full name Xue Li, a search for the space character returns the fourth position or index 3. To extract the first name, we slice from index 0 to index 3, exclusively on the right. To get the last name, we slice from index 4 to 6, exclusively on the right.

Here's what that looks like a python:

To determine the index of the end of the string, programmers tend to use the length of the string. The length works out to be an index whose value is one past the end of the string, which is what we want for a slice using an exclusive right index.

Nested loops

We sometimes need to repeat repeated instructions, which we call a nested loop. In the analytics world, nested loops are hugely important because we use them to process matrices, images, and tables of data.

Processing matrices

Recall that, while we humans can look at the entire matrix at once, a computer examines each element one-by-one. Take a look at this 3x3 matrix:

which we can represent in python using a list of list:

Because this is not a one-dimensional data structure, we can't use a simple "for each element in the matrix" loop to examine each element. The most common pattern for iterating through all elements of an nrows x ncols matrix looks like this:

for i in 0..nrows-1:
    for j in 0..ncols-1:
        do something with matrix[i,j]

where matrix[i,j] accesses the element at row i and column j. Such a nested loop gives all possible combinations of i and j, which is what we want when operating on a matrix. Consider the following translation of that template to Python that prints out all of the two-dimensional indices:

Notice how the column j value varies more quickly than the row i value. We can reverse this order of traversal by changing the loop order:

With the j loop on the outside, it will vary less quickly than the inner i loop.

Double-for list comprehensions to get all combinations

Double loops inside list comprehensions give all combinations, which in this case is something we want. The following code example creates a list of string representations of the coordinates:

Now, let's use an accumulator to sum all of the elements of a 3x3 matrix, we let nrows=3 and ncols=3 and use an addition operation:

Processing images

In the images project for this class, we do lots of fun things to images. An image is nothing more than a two-dimensional matrix whose entries are pixel grayscale values from 0 to 255. A pixel value of 0 is black and 255 is white. For example, if we zoom in on an image, we see the individual elements (called pixels) of a two-dimensional matrix:

The only difference between an image and a matrix is that we typically access the elements of an image using x and y coordinates, rather than row and column. The template for a nested loop that accesses each element of an image looks like this:

for x in 0..width-1:
    for y in 0..height-1:
        process pixel[x,y]

Because the y coordinate varies faster than the x coordinate, the inner loop traverses one vertical stripe. The outer loop shifts x to the next vertical stripe to the right.

Exercise

As a more realistic example, let's add two matrices A and B together to form C. The key operation is to add A_i,j to B_i,j to get C_i,j. Visually, it looks like this:

Write out the nested Python indexed loops to add two matrices together, C = A + B. Here are some definitions to get you started:

nrows = ncols = 3
A = [
    [1, 3, 10],
    [4, -9, 0],
    [2, 5, 8]
]
B = [
    [7, 4, 0],
    [4, 3, 1],
    [1, 6, 8]
]
# Use list comprehension to init list of lists
C = [[0]*ncols for i in range(nrows)]

Warning: don't do this:

Exercise

Instead of using indexed loops as we've done so far (which is very appropriate for matrices), we can also use nested for-each loops. Try this out.

Given a list of first names, first=['Xue', 'Mary', 'Robert'] and a list of last names, last=['Li', 'Smith', 'Dixon'], write a nested Python loop to print every combination of first and last name.

Exercise

Now repeat that exercise using a double-loop list comprehension.