 |  |  | Contents |
來源:http://beastie.cs.ua.edu/cs150/book/book_15.html
Loops
In the previous chapter, you learned how recursion can solve a problem by breaking it in to smaller versions of the same problem. Another approach is to useiterative loops. In some programming languages, loops are preferred as they use much less computer memory as compared to recursions. In other languages, this is not the case at all. In general, there is no reason to prefer recursions over loops or vice versa, other than this memory issue. Any loop can be written as a recursion and any recursion can be written as a loop. Use a recursion if that makes the implementation more clear, otherwise, use an iterative loop.
The most basic loop structure in Python is the while loop, an example of which is:
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 assocated 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".
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 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 ommitted 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 intial value and step of the for loop explicitly.
For loops are commonly used to sweep through each element of an list:
for i in range(0,len(items),1):
print(items[i])
Recall the items in a list 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 a list of n items produces an error, therange 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. Like recursion and lists, loops and lists go very well together. The next sections detail some common loop patterns involving lists.
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 lists, but many programming languages do not have lists as part of the language; the programmer must supply lists. For this example, assume that the start function gets the first item in the given list, returning None if there are no items in the list. The next function returns the next item in the given list, returning None if there are no more items. This while loop counts the number of items in the list:
count = 0
i = start(items)
while (i != None)
count += 1
i = next(items)
When the loop finishes, the variable count holds the number of items in the list.
The counting pattern increments a counter everytime the loop body is evaluated.
The filtered-count pattern
A variation on 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 a list:
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 list of items since 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 a list:
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, total is initialized to zero. When accumulating a product, total is initialized to one.
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 list, 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 accumulationg, 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 list when accumulating a list (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 a list. We can use a filtered-counting approach and if the count is greater than zero, we know that the item was indeed in the list.
count = 0
for i in range(0,len(items),1):
if (items[i] == target):
count += 1
found = count > 0
This pattern is so common, it is often encapsulated in a function. Moreover, we can improve the efficiency by short-circuiting the search. Once the target item is found, there is no need to search the remainder of the list:
def find(target,items):
found = False:
i = 0
while (not(found) and i < len(items)):
if (items[i] == target):
found = True
i += 1
return found
We presume the target item is not in the list and as long as it is not found, we continue to search the list. As soon as we find the item, we set the variable found to True and then the loop condition fails, since not true is false.
Experienced programmers would likely define this function to use an immediate return once the target item is found:
def find(target,items):
for i in range(0,len(items),1):
if (items[i] == target):
return True
return False
As a beginning programmer, however, you should avoid returns 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 filter pattern
Recall that a special case of a filtered-accumulation is the filter pattern. A loop version of filter starts out by initializing an accumulator variable to an empty list. In the loop body, the accumulator variable gets updated with those items from the original list that pass some test.
Suppose we wish to extract the even numbers from a list. Our test, then, is to see if the current element is even. If so, we add it to our growing list:
def extractEvens(items):
evens = []
for i in range(0,len(items),1):
if (items[i] % 2 == 0):
evens = evens + [items[i]]
return evens
Given a list of integers, extractEvens returns a (possibly empty) list 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])
[]
The extreme pattern
Often, we wish to find the largest or smallest value in a list. 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 list is greater than or equal to zero. If not, as is the case when all values in the list 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 a list 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 shuffle pattern
Recall, the shuffle pattern from the previous chapter. Instead of using recursion, we can use a version of the loop accumulation pattern instead. As before, let's assume the lists are exactly the same size:
def shuffle(list1,list2):
list3 = []
for i in range(0,len(list1),1):
list3 = list3 + [list1[i],list2[i]]
return list3
Note how we initialized the resulting list list3 to the empty list. Then, as we walked the first list, we pulled elements from both lists, adding them into the resulting list.
When we have walked past the end of list1 is empty, we know we have also walked past the end of list2, since the two lists have the same size.
If the incoming lists do not have the same length, life gets more complicated:
def shuffle2(list1,list2):
list3 = []
if (len(list1) < len(list2)):
for i in range(0,len(list1),1):
list3 = list3 + [list1[i],list2[i]]
return list3 + list2[i:]
else:
for i in range(0,len(list2),1):
list3 = list3 + [list1[i],list2[i]]
return list3 + list1[i:]
We can also use a while loop that goes until one of the lists is empty. This has the effect of removing the redundant code in shuffle2:
def shuffle3(list1,list2):
list3 = []
i = 0
while (i < len(list2) and i < len(list2)):
list3 = [list1[i],list2[i]]
i = i + 1
...
When the loop ends, one or both of the lists have been exhausted, but we don't know which one or ones. A simple solution is to add both remainders to list3and return.
def shuffle3(list1,list2):
list3 = []
i = 0
while (i < len(list2) and i < len(list2)):
list3 = [list1[i],list2[i]]
i = i + 1
return list3 + list1[i:] + list2[i:]
Suppose list1 is empty. Then the expression list1[i:] will generate the empty list. Adding the empty list to list3 will have no effect, as desired. The same is true if list2 (or both list1 and list2 are empty).
The merge pattern
We can also merge using a loop. Suppose we have two ordered lists (we will assume increasing order) and we wish to merge them into one ordered list. We start by keeping two index variables, one pointing to the smallest element in list1 and one pointing to the smallest element in list2. Since the lists are ordered, we know the that the smallest elements are at the head of the lists:
i = 0 # index variable for list1 j = 0 # index variable for list2
Now, we loop, similar to shuffle3:
while (i < len(list1) and j < len(list2)):
Inside the loop, we test to see if the smallest element in list1 is smaller than the smallest element in list2:
if (list1[i] < list2[j]):
If it is, we add the element from list1 to list3 and increase the index variable i for list1 since we have `used up' the value at index i.
list3 = list3 + [list1[i]]
i = i + 1
Otherwise, list2 must have the smaller element and we do likewise:
list3 = list3 + [list2[j]]
j = j + 1
Finally, when the loop ends (i or j has gotten too large), we add the remainders of both lists to list3 and return:
return list3 + list1[i:] + list2[j:]
In the case of merging, one of the lists will be exhausted and the other will not. As with shuffle3, we really don't care which list was exhausted.
Putting it all together yields:
def merge(list1,list2):
list3 = []
i = 0
j = 0
while (i < len(list1) and j < len(list2)):
if (list1[i] < list2[j]):
list3 = list3 + [list1[i]]
i = i + 1
else:
list3 = list3 + [list2[j]]
j = j + 1
return list3 + list1[i:] + list2[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
Related to the bottomless pattern of recursive functions is the missed condtion pattern of loops. With missed condition, the index variable is updated, but it is updated in such a way that the loop condition is 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.
lusth@cs.ua.edu
| | | Contents |
沒有留言:
張貼留言