We’ll address the general need for iterative processing in Iterative Processing. There are a few specific kinds of iterations that we can identify, and we’ll describe these in Patterns of Iteration. The most commonly-used Python iterative statement is presented in The for Statement. We’ll look at some examples in Multi-Dimensional Loop-the-Loop and Simulating All 100 Rolls of the Dice.
A program may have a goal that is best described using the words “for all”, where we have to do some calculation for all values in a set of values.
Let’s look at creating a table of Celsius temperatures and their matching Fahrenheit temperatures. We only need useful temperatures between -20 ° C and 40 ° C. We’ll work backwards from the ending.
Goal: we need to print all C and F values; the values must satisfy an equation that maps between the two temperatures; the values for C are between -20 and 40.
How do we get to this well-defined final state?
Loop Condition: The value for C is between -20 and 44, and we have not computed and printed the value for F yet. When this condition is true, we have more work to do. When this is false, we have satisfied our for all condition.
What work do we have to do that satisfies the rest of our goal? What precondition is required to make this true initially?
Iterative Step 3: Add 2 to the value of C. This satisfies part of our for all goal by creating a value of C for which we haven’t computed an F.
What else do we have to do?
Iterative Step 2: Print the values for C and F. This satisfies part of our for all goal by printing values of C and F.
What’s the precondition for printing C and F?
Iterative Step 1: Compute the value for F. To do this, we’ll need the value for C. Then we can use a formula from the exercises in Expression Exercises to set the desired value for F.
Precondition: Set the value for C to -20. This sets our Loop Condition to be true.
What’s the precondition for setting C?
Initial Condition. Any initial values of F and C are valid for the start of this program.
When we reverse this list of goals, we have the algorithm for computing a mapping between the Fahrenheit temperature and the Celsius temperature.
We often call iterative or repetitive processing a “loop” because the program statements are executed in a kind of loop. Both the for and while statements provide a condition that controls how many times the loop is executed. The condition in the for statement is trivial, but the pattern is so common that it has a large number of uses. The condition in the while statement is completely open-ended, therefore it requires a little more care when designing the statement.
Iterative processing relies on all the elements of sequential and conditional processing that we’ve already seen. Iterative programming is the backbone of computing. First we’ll look at three common kinds of iteration. Then we’ll see how to write those kinds of iteration in Python.
There are three basic species of iterations: mapping, reducing and filtering. As with much of computer science, other words have been borrowed for these rather abstract ideas. Don’t think of road maps, weight loss or clothes dryers. Think of mapping in the sense of mapping one value to another, reducing a set of values to a single value, and filtering unwanted values out of a set.
Mapping All Values In A Set. Perhaps the simplest kind of iterations is called a mapping. Our iteration maps all values in a set from some domain to some range. We see this kinds of mapping when we look at a Fahrenheit to Celsius conversion table, or a deciliters to cups table. Even an chart that maps the combination of air temperature and wind speed to a wind-chill temperature is a kind of mapping. We’ll look at these kinds of iterations extensively in this chapter.
The for statement is ideal for performing a mapping that has to be done for all values in a set. The typical pattern for a mapping uses a Python for statement and one or more “compute mapped value” statements. It’s a Python statement with a suite of statements, and has a general outline like the following:
For i is a value in some set: Compute mapped result based on i
Here’s the result of a small program that produces a mapping from Swedish Krona (SEK) to US Dollars (USD); it’s a currency exchange table. A Krona is worth about $0.125 right now. We used a Python “for all” loop to iterate through all values from 5 to 50 in steps of 5.
5 0.625 10 1.25 15 1.875 20 2.5 25 3.125 30 3.75 35 4.375 40 5.0 45 5.625 50 6.25
The result of a mapping is an output set of values; the size of the output set matches the size of the input set. In our example above, we have has many Krona values as Dollar values.
Reducing All Values To One Value. Another common kind of iteration is a reduction where all the values in a set are reduced to a single resulting value. When we add up or average a column of numbers, we’re doing a reduction. As we look at our two representative problems (see Two Minimally-Geeky Problems : Examples of Things Best Done by Customized Software), we see that we will be simulating casino games and computing averages of the results of a number of simulation runs.
The for statement is ideal for performing reductions. The typical pattern for a reduction uses a “initializations”, a “for all”, and one or more statements to “update the reduction”.
Initialize the Reductions total= 0 count= 0 For i is a values in some set: Update the Reduction total += calculation based on i count += 1
The result of a reduction is a single number created from the input set of values. Common examples are the sum, average, minimum or maximum. It could also be a more sophisticated reduction like the statistical median or mode.
Filtering All Values To Find a Subset. The third common kind of iteration is a filter where the iteration picks a subset of the values from all values in a set. For instance, we may want a filter that keeps only even numbers, or only red numbers in Roulette.
In this case, we’re introducing a condition, which makes a filter more complex than the map or reduce. A filter combines iteration and conditional processing.
There are two senses of filtering:
These are sometimes lumped under the category of “search”. Search is so important, that several computer science books are on focused on just this subject.
When we look closely at the rules for Craps we see that a game is a kind of filter. Once the game has established a point, the rest of the game is a kind of filter applied to a sequence of dice roles that ignores dice roles except for 7 and the point number. We can imagine adding filter conditions; for example, we could add a filter to keep the dice rolls that win a hardways bet.
The while statement can be used for filtering. Additionally, the break and continue statements can simplify very complex filters. The typical pattern for a filter uses an “initialize”, a “while not finished”, “filter condition” and an “update the results”.
Initialize the Results result = None While Not Finished Filtering: Filter Condition If condition based on i : Update the results result = ...
The result of a filter is a subset of the input values. It may be the original set of values, in the rare case that every value passes the filtering test. It may be a single value if we are searching for just one occurrence of a value that passes the filter.
The most common way to do a “for-all” mapping, reduction or filtering is with the for statement.
The for statement looks like this:
for variable in sequence : suite
The words for and in and the : are essential syntax. The suite is an indented block of statements. Any statement is allowed in the block, including indented for statements.
There are a number of ways of creating the necessary sequence of values. The most common way to create a sequence is to use the range() function. First we’ll look at the for statement, then we’ll provide a definition for the range() function.
Printing All The Values. This first example uses the range() function to create a sequence of six values from 0 to just before 6. The for statement iterates for all values of the sequence, assigning each value to the local variable i. For each of six values of i, the suite of statements inside the for statement is executed.
The suite of statements is just a print() function, which has an expression that adds one to i and prints the resulting value.
for i in range(6): print(i+1)
We can summarize this as “for all i in the range of ‘0 to one before 6’, print i +1”.
Using A Literal Sequence Display. We can also create the sequence manually, using a literal sequence display. A sequence display looks like this: [ expression , ... ]. It’s a list of expressions; for now they should be numbers separated by commas. The square brackets are essential syntax for marking a sequence. We’ll return to sequences in Basic Sequential Collections of Data.
This example uses an explicit sequence of values. These are all of the red numbers on a standard Roulette wheel. It then iterates through the sequence, assigning each value to the local variable r. The print() function prints all 18 values followed by the word “red”.
for r in [1,3,5,7,9,12,14,16,18,19,21,23,25,27,30,32,34,36]: print(r, "red")
Summing All The Values. The second example sums a sequence of five odd values from 1 to just before 10. The for statement iterates through the sequence, assigning each value to the local variable j. The print() function prints the value.
sum= 0 for j in range(1,5*2,2): sum += j print(sum)
Generates values from 0 to x-1, incrementing by 1.
Generates values from x to y -1, incrementing by 1. Each value, v will have the property .
Generates values from x to y - z, incrementing by z. The values will be , where .
From this we can see the following features of the range() function. If we provide one value, we get a sequence from 0 to just before the value we provided. If we provide two values we get a sequence from the starting value to one before the ending value. If we provide three values, the third value is the increment between each value in the sequence.
>>> range(6) [0, 1, 2, 3, 4, 5] >>> range(1,7) [1, 2, 3, 4, 5, 6] >>> range(1,11,2) [1, 3, 5, 7, 9]
Summary. The for statement encapsulates three pieces of information.
Debugging the for Statement
If you are typing a for statement, and you get a SyntaxError: invalid syntax, you omitted the :.
The most common problem is setting up the sequence properly. Very often, this is because of the complex rules for the range() function, and we have one too many or one too few values.
A less common problem is to misspell the variable in the for statement or the suite. If the variable names don’t match, the for statement will set a variable not used properly by the suite. An error like NameError: name 'j' is not defined means that your suite suite expected j, but that was not the variable on your for statement.
Another problem that we can’t really address completely is writing a for statement where the suite doesn’t do the right thing in the first place. In this case, it helps to be sure that the suite works in the first place. An execution trace (see Where Exactly Did We Expect To Be?) can help. Also, you can enter the statements from the suite separately to the Python shell to see what they do.
Our previous examples have had one value which varies. Sometimes we’ll have two (or more) values which vary. Here are some examples that have multiple variables.
Here’s a more complex example, showing nested for statements. This enumerates all the 36 outcomes of rolling two dice. The outer for statement creates a sequence of 6 values, and iterates through the sequence, assigning each value to the local variable d1 . For each value of d1, the inner loop creates a sequence of 6 values, and iterates through that sequence, assigning each value to d2. The print() function will be executed 36 times to print the values of d1 and d2.
for d1 in range(6): for d2 in range(6): print(d1+1, d2+1, '=', d1+d2+2 )
We can interpret this as a mapping from two dice to the sum of those two dice. This is a kind of two-dimensional table with one die going down the rows and one die going across the columns. Each cell of the table has the sum written in.
The output from this example, though, doesn’t look like a table because it’s written down the page, not across the page. To write across the page, we can make use of a feature of the print() function. We’ll manually set the end-of-line to ',' or '\n'.
1 2 3 4 5 6 7
from __future__ import print_function print("", "1", "2", "3", "4", "5", "6") for d1 in range(1,7): print(d1,end=' ') for d2 in range(1,7): print(d1+d2,end=' ') print()
Here’s a program which does 100 simulations of rolling two dice. The for statement creates the sequence of 100 values, assigns each value to the local variable i. It turns out that the suite of statements never actually uses the value of i, it is just bookkeeping for the state changes until the loop is complete.
We can summarize this as “for all 100 samples, set d1 to be a random number between 1 and 6, set d2 to be a random number between 1 and 6, print d1 + d2”.
from __future__ import print_function import random for i in range(100): d1= random.randrange(6)+1 d2= random.randrange(6)+1 print(d1+d2)
This previous example is a mapping from the sample number, (i) to two random dice (d1, d2), and then the two dice are mapped to a single sum.
We’ll expand this simple loop to do some additional processing in While We Have More To Do : The while Statement.
How much effort to produce software?
The following equations are the basic COCOMO estimating model, described in [Boehm81]. The input, K, is the number of 1000’s of lines of source; that is total source lines divided by 1000.
Development Effort, where K is the number of 1000’s of lines of source. E is effort in staff-months.
Development Cost, where E is effort in staff-months, R is the billing rate. C is the cost in dollars (assuming 152 working hours per staff-month)
Project Duration, where E is effort in staff-months. D is duration in calendar months.
Staffing, where E is effort in staff-months, D is duration in calendar months. S is the average staff size.
Evaluate these functions for projects which range in size from 8,000 lines (K = 8) to 64,000 lines (K = 64) in steps of 8. Produce a table with lines of source, Effort, Duration, Cost and Staff size.
Wind Chill Table.
Used by meteorologists to describe the effect of cold and wind combined. Given the wind speed in miles per hour, v, and the temperature in ° F, t, the Wind Chill, w, is given by the formula below. See Wind Chill in Expression Exercises for more information.
Wind speeds are for 0 to 40 mph, above 40, the difference in wind speed doesn’t have much practical impact on how cold you feel.
Evaluate this for all values of V (wind speed) from 0 to 40 mph in steps of 5, and all values of T (temperature) from -10 to 40 in steps of 5.
Celsius to Fahrenheit Conversion Tables.
For values of Celsius from -20 to +30 in steps of 5, produce the equivalent Fahrenheit temperature. The following formula converts C (Celsius) to F (Fahrenheit).
For values of Fahrenheit from -10 to 100 in steps of 5, produce the equivalent Celsius temperatures. The following formula converts F (Fahrenheit) to C (Celsius).
Dive Planning Table.
Given a surface air consumption rate, c, and the starting, s, and final, f, pressure in the air tank, a diver can determine maximum depths and times for a dive. For more information, see Surface Air Consumption Rate in Expression Exercises.
Accept c, s and f from input, then evaluate the following for d from 30 to 120 in steps of 10. Print a table of t and d.
For each diver, c is pretty constant, and can be anywhere from 10 to 20, use 15 for this example. Also, s and f depend on the tank used, typical values are s=2500 and f=500.