Scope Top More on Input Contents

Loops

Loops are used to repeatedly execute some code. The most basic loop structure in Python is the while loop, an example of which is:

    i = 0
    while (i < 10):
        print(i,end="")
        i = i + 1

We see a while loop looks much like an if statement. The difference is that blocks belonging to ifs are evaluated at most once whereas blocks associated with loops may be evaluated many many times. Another difference in nomenclature is that the block of a loop is known as the body (like blocks associated with function definitions). Furthermore, the loop test expression is known as the loop condition.

As Computer Scientists hate to type extra characters if they can help it, you will often see:

    i = i + 1

written as

    i += 1

The latter version is read as "increment i" and saves a whopping two characters of typing.

A while loop tests its condition before the body of the loop is executed. If the initial test fails, the body is not executed at all. For example:

    i = 10
    while (i < 10):
        print(i,end="")
        i += 1

never prints out anything since the test immediately fails. In this example, however:

    i = 0;
    while (i < 10):
        print(i,end="")
        i += 1

the loop prints out the digits 0 through 9:

    0123456789

A while loop repeatedly evaluates its body as long as the loop condition remains true.

To write an infinite loop, use True as the condition:

    while (True):
        i = getInput()
        print("input is",i)
        process(i)

Other loops

There are many kinds of loops in Python, in this text we will only refer to while loops and for loops that count, as these are commonly found in other programming languages. The while loop we have seen; here is an example of a counting for loop:

    for i in range(0,10,1):
        print(i)

This loop is exactly equivalent to:

    i = 0
    while (i < 10):
        print(i)
        i += 1

In fact, a while loop of the general form:

    i = INIT
    while (i < LIMIT):
        # body
        ...
        i += STEP

can be written as a counting for loop:

    for i in range(INIT,LIMIT,STEP):
        # body
        ...

The range function counts from INIT to LIMIT (non-inclusive) by STEP and these values are assigned to i, in turn. After each assignment to i, the loop body is evaluated. After the last value is assigned to i and the loop body evaluated on last time, the for loop ends.

In Python, the range function assumes 1 for the step if the step is omitted and assumes 0 for the initial value and 1 for the step if both the initial value and step are omitted. However, in this text, we will always give the initial value and step of the for loop explicitly.

For loops are commonly used to sweep through each element of an array:

    for i in range(0,len(items),1):
        print(items[i]) 

Recall the items in an array of n elements are located at indices 0 through n - 1. These are exactly the values produced by the range function. So, this loop accesses each element, by its index, in turn, and thus prints out each element, in turn. Since using an index of n in an array of n items produces an error, the range function conveniently makes its given limit non-inclusive.

As stated earlier, there are other kinds of loops in Python, some of which, at times, are more convenient to use than a while loop or a counting for loop. However, anything that can be done with those other loops can be done with the loops presented here. Loops and arrays go very well together; the next sections detail some common loop patterns involving arrays.

The counting pattern

The counting pattern is used to count the number of items in a collection. Note that the built-in function len already does this for Python arrays, so counting the elements in an array is a bit of a waste of time. Still, it is about the easiest loop to write, so let's forge ahead20:

    count = 0
    for i in range(0,len(items),1):
         count += 1

When the loop finishes, the variable count holds the number of items in the array. In general, the counting pattern increments a counter every time the loop body is evaluated.

The filtered-count pattern

A variation on the counting pattern involves filtering. When filtering, we use an if statement to decide whether we should count an item or not. Suppose we wish to count the number of even items in an array:

    count = 0
    for i in range(0,len(items),1):
        if (items[i] % 2 == 0):
            count += 1

When this loop terminates, the variable count will hold the number of even integers in the array of items. The if makes sure the count is incremented only when the item of interest is even.

The accumulate pattern

Similar to the counting pattern, the accumulate pattern updates a variable, not by increasing its value by one, but by the value of an item. This loop, sums all the values in an array:

    total = 0
    for i in range(0,len(items),1):
        total += items[i]

By convention, the variable total is used to accumulate the item values. When accumulating a sum, the total is initialized to zero. When accumulating a product, the total is initialized to one21.

The filtered-accumulate pattern

Similar to the accumulate pattern, the filtered-accumulate pattern updates a variable only if some test is passed. This function sums all the even values in a given array, returning the final sum:

    def sumEvens(items):
        total = 0
        for i in range(0,len(items),1):
            if (items[i] % 2 == 0):
                total += items[i]
        return total

As before, the variable total is used to accumulate the item values. As with a regular accumulating, total is initialized to zero when accumulating a sum. The initialization value is one when accumulating a product and the initialization value is the empty array when accumulating an array (see filtering below).

The search pattern

The search pattern is a slight variation of filtered-counting. Suppose we wish to see if a value is present in an array. We can use a filtered-counting approach; if the count is greater than zero, we know that the item was indeed in the array.

    def find(target,items): # is target in items?
        return occurrences(target,items) > 0

    def occurrences(target,items):
        count = 0
        for i in range(0,len(items),1):
            if (items[i] == target):
                count = count + 1
        return count

In this case, occurrences implements the filtered-count pattern and helps find do its job. We designate such functions as occurrences and the like, helper functions. However, we can improve the efficiency of find by having it partially implement the filtered-count, but short-circuiting the search once the target item is found. We do this by returning from the body of the loop:

    def find(target,items):
        for i in range(0,len(items),1):
            if (items[i] == target):
                return True             # short-circuit!
        return False

When the array is empty, we return false, as indicated by the last line of the function, because the loop never runs and thus the return inside the loop can never be reached. In the same vein, if no item matches the target, we cannot return true, and eventually the loop exits and false is returned.

As a beginning programmer, however, you should be wary of returning from the body of a loop. The reason is most beginners end up defining the function this way instead:

    def find(target,items):
        for i in range(0,len(items),1):
            if (items[i] == target):
                return True
            else:
                return False

The behavior of this latter version of find is incorrect, but unfortunately, it appears to work correctly under some conditions. If you cannot figure out why this version fails under some conditions and appears to succeed under others, you most definitely should stay away from placing returns in loop bodies.

The extreme pattern

Often, we wish to find the largest or smallest value in an array. Here is one approach, which assumes that the first item is the largest and then corrects that assumption if need be:

    largest = items[0]
    for i in range(0,len(items),1):
        if (items[i] > largest):
            largest = items[i]

When this loop terminates, the variable largest holds the largest value. We can improve the loop slightly by noting that the first time the loop body evaluates, we compare the putative largest value against itself, which is a worthless endeavor. To fix this, we can start the index variable i at 1 instead:

    largest = items[0]
    for i in range(1,len(items),1): #start comparing at index 1
        if (items[i] > largest):
            largest = items[i]

Novice programmers often make the mistake of initialing setting largest to zero and then comparing all values against largest, as in:

    largest = 0
    for i in range(0,len(items),1):
        if (items[i] > largest):
            largest = items[i]

This code appears to work in some cases, namely if the largest value in the array is greater than or equal to zero. If not, as is the case when all values in the array are negative, the code produces an erroneous result of zero as the largest value.

The extreme-index pattern

Sometimes, we wish to find the index of the most extreme value in an array rather than the actual extreme value. In such cases, we assume index zero holds the extreme value:

    ilargest = 0
    for i in range(1,len(items),1):
        if (items[i] > items[ilargest]):
            ilargest = i

Here, we successively store the index of the largest value see so far in the variable ilargest.

The filter pattern

A special case of a filtered-accumulation is called filter. Instead of summing the filtered items (for example), we collect the filtered items into an array. The new array is said to be a reduction of the original array.

Suppose we wish to extract the even numbers from an array. The code looks very much like the sumEvens function, but instead of adding in the desired item, we make an array out of it and add it to the back of the growing array of even numbers:

    def extractEvens(items):
        evens = []
        for i in range(0,len(items),1):
            if (isEven(items[i])):
                evens = evens + [items[i]] # array concatenation
        return evens

Given an array of integers, extractEvens returns a (possibly empty) array of the even numbers:

    >>> extractEvens([4,2,5,2,7,0,8,3,7])
    [4, 2, 2, 0, 8]

    >>> extractEvens([1,3,5,7,9])
    []

Note that our use of array concatenation makes our extractEvens function run very slowly for very large arrays22. To speed up extractEvens, we will use the object nature of arrays and invoke the append method to add an new element to the end of the existing array23. In Python, one invokes a method on an object by using the dot operator. Generically, the expression:

    o.f()

means run method f on object o. Using the append method, our extractEvens function becomes:

    def extractEvens(items):
        evens = []
        for i in range(0,len(items),1):
            if (isEven(items[i])):
                evens.append(items[i]) # method invocation
        return evens

We can see that the append method implements the procedure pattern in that it modifies the evens array, not returning anything. With this change, the extractEvens function will run much faster24.

The map pattern

Mapping is a task closely coupled with that of filtering, but rather than collecting certain items, as with the filter pattern, we collect all the items. As we collect, however, we transform each item as we collect it. The basic pattern looks like this:

    def map(f,items):
        result = []
        for i in range(0,len(items),1):
            transformed = f(items[i])
            result.append(transformed)
        return result

Here, function f is used to transform each item in the before it is added to the growing result.

Suppose we wish to subtract one from each element in an array. First we need a transforming function that reduces its argument by one:

    def decrement(x): return x - 1

Now we can "map" the decrement function over an array of numbers:

    >>> map(decrement,[4,3,7,2,4,3,1])
    [3, 2, 6, 1, 3, 2,  0]

The shuffle pattern

Sometimes, we wish to combine two arrays into a third array, This is easy to do with the concatenation operator, +.

    array3 = array1 + array2

This places the first element in the second array after the last element in the first array. However, many times we wish to intersperse the elements from the first array with the elements in the second array. This is known as a shuffle, so named since it is similar to shuffling a deck of cards. When a deck of cards is shuffled, the deck is divided in two halves (one half is akin to the first array and the other half is akin to the second array). Next the two halves are interleaved back into a single deck (akin to the resulting third array).

We can use a loop to shuffle two arrays. If both arrays are exactly the same length, a shuffling function is easy to implement using the accumulate pattern. Let's first assume the arrays are exactly the same size, because that makes things easier:

    def shuffle(array1,array2):
        array3 = []
        for i in range(0,len(array1),1):
            array3.append(array1[i])
            array3.append(array2[i])
        return array3

Note how we initialized the resulting array array3 to the empty array. Then, as we walked the first array, we pulled elements from both arrays, adding them into the resulting array.

When we have walked past the end of array1 is empty, we know we have also walked past the end of array2, since the two arrays have the same size.

If the incoming arrays do not have the same length, life gets more complicated:

    def shuffle2(array1,array2):
        array3 = []
        if (len(array1) < len(array2)):
            for i in range(0,len(array1),1):
                array3.append(array1[i])
                array3.append(array2[i])
            return array3 + array2[i+1:]
        else:
            for i in range(0,len(array2),1):
                array3.append(array1[i])
                array3.append(array2[i])
            return array3 + array1[i+1:]

Note the need to add the remaining elements in the longer array to the items that made it into array3.

We can also use a while loop that goes until one of the arrays is empty. This has the effect of removing the redundant code in shuffle2:

    def shuffle3(array1,array2):
        array3 = []
        i = 0
        while (i < len(array1) and i < len(array2)):
            array3.append(array1[i])
            array3.append(array2[i])
            i = i + 1
        ...

When the loop ends, one or both of the arrays have been exhausted, but we don't know which one or ones. A simple solution is to add both remainders to array3 and return.

    def shuffle3(array1,array2):
        array3 = []
        i = 0
        while (i < len(array1) and i < len(array2)):
            array3.append(array1[i])
            array3.append(array2[i])
            i = i + 1
        return array3 + array1[i:] + array2[i:]

Suppose array1 is empty. Then the expression array1[i:] will generate the empty array. Adding the empty array to array3 will have no effect, as desired. The same is true if array2 (or both array1 and array2 are empty).

Looking back at shuffle2, we see that the code would be much simpler if we could guarantee that one array was shorter than another. Suppose we write the code so that the assumption is that the first array is the shorter. Our code becomes:

    def shuffle4(array1,array2):
        array3 = []
        for i in range(0,len(array1),1):
            array3.append(array1[i])
            array3.append(array2[i])
        return array3 + array2[i+1:]

But what happens when the second array is shorter? The code will fail (how?) unless we handle it. Here's one way to handle it:

    def shuffle4(array1,array2):
        if (len(array2) < len(array1)):
            return shuffle4(array2,array1) # arrays are flipped
        else:
            array3 = []
            for i in range(0,len(array1),1):
                array3.append(array1[i])
                array3.append(array2[i])
            return array3 + array2[i+1:]

Note that we re-call shuffle4 with array2 as the first array if the length of array2 is less than the length of array1. On this second call to shuffle4, we guarantee that the shorter array is the first array.

Although it may seem, at first, rather strange to call shuffle4 from within shuffle4, Computer Scientists do this trick all the time. It's called recursion and you will learn much more about recursion in a later chapter.

The merge pattern

With the shuffle pattern, we always took the head elements from both arrays at each step in the shuffling process. Sometimes, we wish to place a constraint of the choice of elements. For example, suppose the two arrays to be combined are sorted and we wish the resulting array to be sorted as well. The following example shows that shuffling does not always work:

    >>> a = [1,4,6,7,8]
    >>> b = [2,3,5,9]

    >>> c = shuffle2(a,b)
    [1, 2, 4, 3, 6, 5, 7, 9, 8]

The merge pattern is used to ensure the resulting array is sorted and is based upon the filtered-accumulate pattern. The twist is we only accumulate an item if it is the smallest item in the two arrays that has not already been accumulated. We start by keeping two index variables, one pointing to the smallest element in array1 and one pointing to the smallest element in array2. Since the arrays are ordered, we know the that the smallest elements are at the head of the arrays:

   i = 0  # index variable for array1
   j = 0  # index variable for array2

Now, we loop, similar to shuffle3:

    while (i < len(array1) and j < len(array2)):

Inside the loop, we test to see if the smallest element in array1 is smaller than the smallest element in array2:

        if (array1[i] < array2[j]):

If it is, we add the element from array1 to array3 and increase the index variable i for array1 since we have "used up" the value at index i.

            array3.append(array1[i])
            i = i + 1

Otherwise, array2 must have the smaller element and we do likewise:

            array3.append(array2[j])
            j = j + 1

Finally, when the loop ends (i or j has gotten too large), we add the remainders of both arrays to array3 and return:

    return array3 + array1[i:] + array2[j:]

In the case of merging, one of the arrays will be exhausted and the other will not. As with shuffle3, we really don't care which array was exhausted.

Putting it all together yields:

    def merge(array1,array2):
        array3 = []
        i = 0
        j = 0
        while (i < len(array1) and j < len(array2)):
            if (array1[i] < array2[j]):
                array3.append(array1[i])
                i = i + 1
            else:
                array3.append(array2[j])
                j = j + 1
        return array3 + array1[i:] + array2[j:]

The fossilized pattern

Sometimes, a loop is so ill-specified that it never ends. This is known as an infinite loop. Of the two loops we are investigating, the while loop is the most susceptible to infinite loop errors. One common mistake is the fossilized pattern, in which the index variable never changes so that the loop condition never becomes false:

    i = 0
    while (i < n):
        print(i)

This loop keeps printing until you terminate the program with prejudice. The reason is that i never changes; presumably a statement to increment i at the bottom of the loop body has been omitted.

The missed-condition pattern

With the missed condition pattern, the index variable is updated, but it is updated in such a way that the loop condition never evaluates to false.

    i = n
    while (i > 0):
        print(i)
        i += 1

Here, the index variable i needs to be decremented rather than incremented. If i has an initial value greater than zero, the increment pushes i further and further above zero. Thus, the loop condition never fails and the loop becomes infinite.

Code

For Linux and Mac users, the code from this chapter can be found here

For Windows users, look here (you will need to save the file as loops.py).

lusth@cs.ua.edu


Scope Top More on Input Contents