Loop patterns

An important part of learning to program is recognizing and using common patterns in programming. In these notes I am going to introduce you to some of the most common patterns that show up in the use of loops in Python.

All of the examples below will make use of a common data set:

data = [2,-1,-2,1,-3,-7,-3,1,6,2,1,2,-3,2,1,-1]

Adding thing up

The first and most basic loop pattern is the summation pattern. To compute the sum of the items in our data set we would use this code.

total = 0
for x in data:
    total += x

We can do other things in the summation loop beyond just adding things up. For example, if we need to compute the average of the items in our list we would need to count the items at the same time we are adding them.

total = 0
count = 0
for x in data:
    total += x
    count += 1
average = total/count

Searching for things

In the search pattern we iterate over a loop looking for something. To help us with the search we typically put an if statement in the loop body to check each item we come to.

For example, to count how many items in our data list are negative we would do this:

negative_count = 0
for x in data:
    if x < 0:
        negative_count += 1

Here is some code that searches for the largest number in the list.

largest = data[0]
for x in data:
    if x > largest:
        largest = x

A single loop can also be used to search for more than one thing at the same time. In this example we search for both the smallest and the largest number in the data list.

smallest = data[0]
largest = data[0]
for x in data:
    if x > largest:
        largest = x
    elif x < smallest:
        smallest = x

Filtering

The filtering pattern involves selecting a subset of some list. The most common way to implement filtering is to start out with an empty result list and then append items to it as we find items to add.

For example, if we wanted to filter out the negative numbers in our data list and just retain the positive items we would do this:

positive_numbers = []
for x in data:
    if x >= 0:
        positive_numbers.append(x)

Packaging code in a function

Another important concept in programming is reuse. Once we solved a problem once, we may want to use that same solution in other programs. The most common way to implement reuse is to take our useful code and embed it in a function. We can then collect sets of useful functions into a package of functions that we can import in other programs.

Here are some of the examples from above restructured as functions.

Here is a function to add up the elements of a list.

def sum_list(values):
    sum = 0
    for x in values:
        sum += x
    return sum

Here is a function to find the smallest and largest values of a list.

def find_bounds(values):
    smallest = values[0]
    largest = values[0]
    for x in values:
        if x < smallest:
            smallest = x
        elif x > largest:
            largest = x
    return (smallest,largest)

Here is a function to filter a list and return a list of only the positive values.

def positive_filter(value)
    positive_numbers = []
    for x in values:
        if x > 0:
            positive_numbers.append(x)
    return positive_numbers

Using several functions to solve a problem

Beyond reuse, functions also play an important role in problem decomposition. To solve a more complex problem we may need to break the problem down into subtasks. Writing functions to help carry out the subtasks is a common precedure in programming.

Here is an example. The mode in a list of numbers is the number that appears most often. An important subtask in computing the mode of a list is computing how many times a given number appears in a list of values. Here is a function to answer that question.

def count_occurances(values,v):
    """Return the count of how many times v appears in values"""
    count = 0
    for x in values:
        if x == v:
            count += 1
    return count

We can then use this function to help us write the function to compute the mode of a list of numbers.

def mode(values):
    """Return the number that appears most often in values"""
    max_count = 1
    most_common = values[0]
    for x in values:
        count = count_occurances(values,x)
        if count > max_count:
            max_count = count
            most_common = x
    return most_common

Programming Exercise

The mean x of a list of data values is the average of the data values.

The standard deviation of a list of data values is

In a list an outlier is any data element that lies more than 2 standard deviations from the mean of the list.

Write a program that finds the outliers in the data list

data = [2,-1,-2,1,-3,-7,-3,1,6,2,1,2,-3,2,1,-1]

Your program should define and use three functions:

1. A function to compute the mean of a list of numbers.
2. A function to compute the standard deviation of a list of numbers
3. A function to filter a list of data values and return a list of any outliers in the list.