In this chapter, we will present iteration using loops and iterators. We will show examples of how this can be used with lists and generators. Iteration is one of the fundamental operations a computer is useful for. Traditionally, iteration is achieved by a for
loop. A for
loop is a repetition of a block of instructions a certain number of times. Inside the loop, one has access to a loop variable, in which the iteration number is stored.
The Python idiom is slightly different. A for
loop in Python is primarily designed to exhaust a list, that is, to enumerate the elements of a list. The effect is similar to the repetition effect just described if one uses a list containing the first n integers.
A for
loop only needs one element of the list at a time. It is therefore desirable to use a for
loop with objects that are able to create those elements on demand, one at a time. This is what iterators achieve in Python.
The primary aim of the for
statement is to traverse a list:
for s in ['a', 'b', 'c']:
print(s), # a b c
In this example, the loop variable s is successively assigned to one element of the list. Notice that the loop variable is available after the loop has terminated. This may sometimes be useful; refer, for instance, the example in section Controlling the flow inside the loop.
One of the most frequent uses of a for
loop is to repeat a given task a defined number of times, using the function range
(refer to section Lists of Chapter 1, Getting Started).
for iteration in range(n): # repeat the following code n times
...
If the purpose of a loop is to go through a list, many languages (including Python) offer the following pattern:
for k in range(...):
...
element = my_list[k]
If the purpose of that code were to go through the list my_list
, the preceding code would not make it very clear. For this reason, a better way to express this is as follows...
Controlling the flow inside the loop
Sometimes it is necessary to jump out of the loop, or to go directly to the next loop iteration. These two operations are performed by the break
and continue
commands. The break
keyword, as the name indicates, breaks the loop. Two situations can occur where the loop breaks:
- The loop is completely executed.
- The loop is left before it was completely executed (
break
).
For the first case, special actions can be defined in an else
block, which is executed if the whole list is traversed. This is useful in general if the purpose of the for
loop is to find something and stop. Examples might be searching for one element satisfying a certain property inside a list. If such an element is not found, the else
block is executed.
Here is a common usage in scientific computing. Quite often, we use an iterating algorithm that is not guaranteed to succeed. In that case, it is preferable to use a (big) finite loop so that the program does not get caught in an infinite loop...
A for
loop is primarily used to traverse a list, but it picks the elements of the list one at a time. In particular, there is no need to store the whole list in memory for the loop to work properly. The mechanism that allows for
loops to work without lists is that of iterators.
An iterable object produces objects (to be passed to a for
loop). Such an object, obj
, may be used inside a for
loop, as follows:
for element in obj:
...
The notion of iterator thus generalizes the idea of lists. The simplest example of an iterable object is given by lists. The produced objects are simply the objects stored in the list:
L = ['A', 'B', 'C']
for element in L:
print(element)
An iterable object need not produce existing objects. The objects may, instead, be produced on the fly.
A typical iterable is the object returned by the function range
. This function works as if it would generate a list of integers, but instead, the successive integers are produced on the fly when they...
We give an example of application of generators for convergence acceleration. This presentation follows closely the example given by Pramode C.E in Python Generator Tricks (refer [9] for more information).
Note that a generator may take an other generator as an input parameter. For instance, suppose that we have defined a generator that generates the elements of a converging sequence. It is then possible to improve the convergence by an acceleration technique due to Euler and Aitken, often called Aitken’s Δ2-method (Refer [33]). It transforms a sequence si into another by defining
Both sequences have the same limit, but the sequence converges significantly faster. One possible implementation is as follows:
def Euler_accelerate(sequence):
"""
Accelerate the iterator in the variable `sequence`.
"""
s0 = next(sequence) # Si
s1 = next(sequence) # Si+1
s2 = next(sequence) # Si+2
while True:
...
In this section we will compare different ways to fill lists. They are different in computational efficiency and also in code readability.
List filling with the append method
A ubiquitous programming pattern is to compute elements and store them in a list:
L = []
for k in range(n):
# call various functions here
# that compute "result"
L.append(result)
This approach has a number of disadvantages:
- The number of iterations is decided in advance. If there is a
break
instruction, then the preceding code takes care of both generating values and deciding when to stop. This is not desirable and lacks flexibility. - It makes the assumption that the user wants the whole history of the computation, for all the iterations. Suppose we are only interested in the sum of all the computed values. If there are many computed values, it does not make sense to store them, as it is much more efficient to add them one at a time.
When iterators behave as lists
Some list operations also work on iterators. We will now examine the equivalents of list comprehensions and list zipping (refer to section List of Chapter 3, Container Types, for more details).
There is an equivalent of list comprehension for generators. Such a construction is called a generator expression:
g = (n for n in range(1000) if not n % 100)
# generator for 100, 200, ... , 900
This is useful in particular for computing sums or products because those operations are incremental; they only need one element at a time:
sum(n for n in range(1000) if not n % 100) # returns 4500
In that code, you notice that the sum
function is given one argument, which is a generator expression. Note that Python syntax allows us to omit the enclosing parentheses of generators when a generator is used as the only argument of a function.
Let us compute the Riemann zeta function ζ, whose expression is
With a generator expression, we may compute a partial...
As we mentioned earlier, a for
loop only needs an iterable object. Lists, in particular, are iterable. This means that a list is able to create an iterator from its contents. In fact, this is true for any object (not only lists): any object may be made iterable.
This is achieved via the __iter__
method, which should return an iterator. Here we give an example where the __iter__
method is a generator:
class OdeStore:
"""
Class to store results of ode computations
"""
def __init__(self, data):
"data is a list of the form [[t0, u0], [t1, u1],...]"
self.data = data
def __iter__(self):
"By default, we iterate on the values u0, u1,..."
for t, u in self.data:
yield u
store = OdeStore([[0, 1], [0.1, 1.1], [0.2, 1.3]])
for u in store:
print(u)
# result: 1, 1.1, 1.3
list(store) # [1, 1.1, 1.3]
If you try to use the features of...
Infinite iterations are obtained either with an infinite iterator, with a while
loop, or by recursion. Obviously, in practical cases, some condition stops the iteration. The difference with finite iterations is that it is impossible to say by a cursory examination of the code, whether the iteration will stop or not.
The while
loop may be used to repeat a code block until a condition is fulfilled:
while condition:
<code>
A while
loop is equivalent to the following code:
for iteration in itertools.count():
if not condition:
break
<code>
So a while
loop is equivalent to an infinite iterator, which might be stopped if a condition is fulfilled. The danger of such a construction is obvious: the code may be trapped in an infinite loop if the condition is never fulfilled.
The problem in scientific computing is that one is not always sure that an algorithm will converge. Newton iteration, for instance, might not converge...
In this chapter, we studied iterators, a programming construct very near to a mathematical description of iterative methods. You saw the yield
keyword and met finite and infinite iterators.
We showed that an iterator can be exhausted. More special aspects such as iterator comprehension and recursive iterators were introduced and demonstrated with the help of examples.
Ex. 1 → Compute the value of the sum:
Ex. 2 → Create a generator that computes the sequence defined by the relation:
Ex. 3 → Generate all the even numbers.
Ex. 4 → Let . In calculus, it is shown that . Determine experimentally the smallest number n such that . Use a generator for this task.
Ex. 5 → Generate all prime numbers less than a given integer. Use the algorithm called Sieve of Eratosthenes.
Ex. 6 → Solving the differential equation by applying the explicit Euler method results in the recursion:
Write a generator that computes the solution values un for a given initial value u0 and for a given value of the time step h.
Ex. 7 → Compute π using the formula:
The integral can be approximated using the composite trapezoidal rule, that is, by this formula:
where .
Program a generator for the values yi = f(xi) and evaluate the formula by summing one term after the other. Compare your results with the quad
function of SciPy.
Ex. 8 → Let x = [1, 2, 3] and y = [-1, -2, -3...