This chapter continues the advanced function topics theme, with a
reprisal of the comprehension and iteration concepts introduced in Chapter 14. Because list
comprehensions are as much related to the prior chapter’s functional
tools (e.g., map
and filter
) as they are to for
loops, we’ll revisit them in this context
here. We’ll also take a second look at iterators in order to study
generator functions and their generator expression
relatives—user-defined ways to produce results on demand.
Iteration in Python also encompasses user-defined classes, but we’ll defer that final part of this story until Part VI, when we study operator overloading. As this is the last pass we’ll make over built-in iteration tools, though, we will summarize the various tools we’ve met thus far, and time the relative performance of some of them. Finally, because this is the last chapter in the part of the book, we’ll close with the usual sets of “gotchas” and exercises to help you start coding the ideas you’ve read about.
In the prior chapter, we studied functional programming tools like map
and filter
, which map operations over sequences
and collect results. Because this is such a common task in Python
coding, Python eventually sprouted a new expression—the list
comprehension—that is even more flexible than the tools we
just studied. In short, list comprehensions apply an arbitrary
expression to items in an iterable, rather than
applying a function. As such, they can be more general tools.
We met list comprehensions in Chapter 14, in conjunction
with looping statements. Because they’re also related to functional
programming tools like the map
and
filter
calls, though, we’ll
resurrect the topic here for one last look. Technically, this feature
is not tied to functions—as we’ll see, list comprehensions can be a
more general tool than map
and
filter
—but it is sometimes best
understood by analogy to function-based alternatives.
Let’s work through an example that demonstrates the basics. As we saw in
Chapter 7, Python’s built-in ord
function returns the ASCII integer
code of a single character (the chr
built-in is the converse—it returns
the character for an ASCII integer code):
>>> ord('s')
115
Now, suppose we wish to collect the ASCII codes of
all characters in an entire string. Perhaps the
most straightforward approach is to use a simple for
loop and append the results to a
list:
>>>res = []
>>>for x in 'spam'
: ...res.append(ord(x))
... >>>res
[115, 112, 97, 109]
Now that we know about map
,
though, we can achieve similar results with a single function call
without having to manage list construction in the code:
>>>res = list(map(ord, 'spam'))
# Apply function to sequence >>>res
[115, 112, 97, 109]
However, we can get the same results from a list comprehension
expression—while map
maps a
function over a sequence, list comprehensions
map an expression over a sequence:
>>>res = [ord(x) for x in 'spam']
# Apply expression to sequence >>>res
[115, 112, 97, 109]
List comprehensions collect the results of applying an
arbitrary expression to a sequence of values and return them in a
new list. Syntactically, list comprehensions are enclosed in
square brackets (to remind you that they construct
lists). In their simple form, within the brackets you code an
expression that names a variable followed by what looks like a
for
loop header that names the
same variable. Python then collects the expression’s results for
each iteration of the implied loop.
The effect of the preceding example is similar to that of the
manual for
loop and the map
call. List comprehensions become more
convenient, though, when we wish to apply an arbitrary expression to
a sequence:
>>> [x ** 2 for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
Here, we’ve collected the squares of the numbers 0 through 9
(we’re just letting the interactive prompt print the resulting list;
assign it to a variable if you need to retain it). To do similar
work with a map
call, we would
probably need to invent a little function to implement the square
operation. Because we won’t need this function elsewhere, we’d
typically (but not necessarily) code it inline, with a lambda
, instead of using a def
statement elsewhere:
>>> list(map((lambda x: x ** 2), range(10)))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
This does the same job, and it’s only a few keystrokes longer
than the equivalent list comprehension. It’s also only marginally
more complex (at least, once you understand the lambda
). For more advanced kinds of
expressions, though, list comprehensions will often require
considerably less typing. The next section shows why.
List comprehensions are even more general than shown so far. For instance,
as we learned in Chapter 14, you can code
an if
clause after the for
to add selection logic. List
comprehensions with if
clauses
can be thought of as analogous to the filter
built-in discussed in the prior
chapter—they skip sequence items for which the if
clause is not true.
To demonstrate, here are both schemes picking up even numbers
from 0 to 4; like the map
list
comprehension alternative of the prior section, the filter
version here must invent a little
lambda
function for the test
expression. For comparison, the equivalent for
loop is shown here as well:
>>>[x for x in range(5) if x % 2 == 0]
[0, 2, 4] >>>list(filter((lambda x: x % 2 == 0), range(5)))
[0, 2, 4] >>>res = []
>>>for x in range(5):
...if x % 2 == 0:
...res.append(x)
... >>>res
[0, 2, 4]
All of these use the modulus (remainder of division) operator,
%
, to detect even numbers: if
there is no remainder after dividing a number by 2, it must be even.
The filter
call here is not much
longer than the list comprehension either. However, we can combine
an if
clause and an arbitrary
expression in our list comprehension, to give it the effect of a
filter
and a
map
, in a single
expression:
>>> [x ** 2 for x in range(10) if x % 2 == 0]
[0, 4, 16, 36, 64]
This time, we collect the squares of the even numbers from 0
through 9: the for
loop skips
numbers for which the attached if
clause on the right is false, and the expression on the left
computes the squares. The equivalent map
call would require a lot more work on
our part—we would have to combine filter
selections with map
iteration, making for a noticeably
more complex expression:
>>>list(
map((lambda x: x**2), filter((lambda x: x % 2 == 0), range(10))) )
[0, 4, 16, 36, 64]
In fact, list comprehensions are more general still. You can
code any number of nested for
loops in a list comprehension, and each may have an optional
associated if
test. The general
structure of list comprehensions looks like this:
[ expression fortarget1
initerable1
[ifcondition1
] fortarget2
initerable2
[ifcondition2
] ... fortargetN
initerableN
[ifconditionN
] ]
When for
clauses are nested
within a list comprehension, they work like equivalent nested
for
loop statements. For example,
the following:
>>>res = [x + y for x in [0, 1, 2] for y in [100, 200, 300]]
>>>res
[100, 200, 300, 101, 201, 301, 102, 202, 302]
has the same effect as this substantially more verbose equivalent:
>>>res = []
>>>for x in [0, 1, 2]:
...for y in [100, 200, 300]:
...res.append(x + y)
... >>>res
[100, 200, 300, 101, 201, 301, 102, 202, 302]
Although list comprehensions construct lists, remember that they can iterate over any sequence or other iterable type. Here’s a similar bit of code that traverses strings instead of lists of numbers, and so collects concatenation results:
>>> [x + y for x in 'spam' for y in 'SPAM']
['sS', 'sP', 'sA', 'sM', 'pS', 'pP', 'pA', 'pM',
'aS', 'aP', 'aA', 'aM', 'mS', 'mP', 'mA', 'mM']
Finally, here is a much more complex list comprehension that
illustrates the effect of attached if
selections on nested for
clauses:
>>> [(x, y) for x in range(5) if x % 2 == 0 for y in range(5) if y % 2 == 1]
[(0, 1), (0, 3), (2, 1), (2, 3), (4, 1), (4, 3)]
This expression permutes even numbers from 0 through 4 with
odd numbers from 0 through 4. The if
clauses filter out items in each
sequence iteration. Here is the equivalent statement-based
code:
>>>res = []
>>>for x in range(5):
...if x % 2 == 0:
...for y in range(5):
...if y % 2 == 1:
...res.append((x, y))
... >>>res
[(0, 1), (0, 3), (2, 1), (2, 3), (4, 1), (4, 3)]
Recall that if you’re confused about what a complex list
comprehension does, you can always nest the list comprehension’s
for
and if
clauses inside each other (indenting
successively further to the right) to derive the equivalent
statements. The result is longer, but perhaps clearer.
The map
and filter
equivalent would be wildly complex
and deeply nested, so I won’t even try showing it here. I’ll leave
its coding as an exercise for Zen masters, ex-Lisp programmers, and
the criminally insane....
Not all list comprehensions are so artificial, of course. Let’s look at one more application to stretch a few synapses. One basic way to code matrixes (a.k.a. multidimensional arrays) in Python is with nested list structures. The following, for example, defines two 3 × 3 matrixes as lists of nested lists:
>>>M = [[1, 2, 3],
...[4, 5, 6],
...[7, 8, 9]]
>>>N = [[2, 2, 2],
...[3, 3, 3],
...[4, 4, 4]]
Given this structure, we can always index rows, and columns within rows, using normal index operations:
>>>M[1]
[4, 5, 6]
>>>M[1][2]
6
List comprehensions are powerful tools for processing such structures, though, because they automatically scan rows and columns for us. For instance, although this structure stores the matrix by rows, to collect the second column we can simply iterate across the rows and pull out the desired column, or iterate through positions in the rows and index as we go:
>>>[row[1] for row in M]
[2, 5, 8] >>>[M[row][1] for row in (0, 1, 2)]
[2, 5, 8]
Given positions, we can also easily perform tasks such as
pulling out a diagonal. The following expression uses range
to generate the list of offsets and
then indexes with the row and column the same, picking out M[0][0]
, then M[1][1]
, and so on (we assume the matrix
has the same number of rows and columns):
>>> [M[i][i] for i in range(len(M))]
[1, 5, 9]
Finally, with a bit of creativity, we can also use list comprehensions to combine multiple matrixes. The following first builds a flat list that contains the result of multiplying the matrixes pairwise, and then builds a nested list structure having the same values by nesting list comprehensions:
>>>[M[row][col] * N[row][col] for row in range(3) for col in range(3)]
[2, 4, 6, 12, 15, 18, 28, 32, 36] >>>[[M[row][col] * N[row][col] for col in range(3)] for row in range(3)]
[[2, 4, 6], [12, 15, 18], [28, 32, 36]]
This last expression works because the row iteration is an outer loop: for each row, it runs the nested column iteration to build up one row of the result matrix. It’s equivalent to this statement-based code:
>>>res = []
>>>for row in range(3):
...tmp = []
...for col in range(3):
...tmp.append(M[row][col] * N[row][col])
...res.append(tmp)
... >>>res
[[2, 4, 6], [12, 15, 18], [28, 32, 36]]
Compared to these statements, the list comprehension version requires only one line of code, will probably run substantially faster for large matrixes, and just might make your head explode! Which brings us to the next section.
With such generality, list comprehensions can quickly
become, well, incomprehensible, especially when nested.
Consequently, my advice is typically to use simple for
loops when getting started with
Python, and map
or comprehensions
in isolated cases where they are easy to apply. The “keep it simple”
rule applies here, as always: code conciseness is a much less
important goal than code readability.
However, in this case, there is currently a substantial
performance advantage to the
extra complexity: based on tests run under Python today,
map
calls are roughly twice as
fast as equivalent for
loops, and
list comprehensions are usually slightly faster than map
calls.[43] This speed difference is generally due to the fact
that map
and list comprehensions run at C language speed
inside the interpreter, which is much faster than stepping through
Python for
loop code within the
PVM.
Because for
loops make
logic more explicit, I recommend them in general on the grounds of
simplicity. However, map
and list
comprehensions are worth knowing and using for simpler kinds of
iterations, and if your application’s speed is an important
consideration. In addition, because map
and list comprehensions are both
expressions, they can show up syntactically in places that for
loop statements cannot, such as in the
bodies of lambda
functions,
within list and dictionary literals, and more. Still, you should try
to keep your map
calls and list
comprehensions simple; for more complex tasks, use full statements
instead.
Python today supports procrastination much more than it did in the past—it provides tools that produce results only when needed, instead of all at once. In particular, two language constructs delay result creation whenever possible:
Generator functions are coded as normal def
statements but use yield
statements to return results one
at a time, suspending and resuming their state between
each.
Generator expressions are similar to the list comprehensions of the prior section, but they return an object that produces results on demand instead of building a result list.
Because neither constructs a result list all at once, they save memory space and allow computation time to be split across result requests. As we’ll see, both of these ultimately perform their delayed-results magic by implementing the iteration protocol we studied in Chapter 14.
In this part of the book, we’ve learned about coding normal functions that receive input parameters and send back a single result immediately. It is also possible, however, to write functions that may send back a value and later be resumed, picking up where they left off. Such functions are known as generator functions because they generate a sequence of values over time.
Generator functions are like normal functions in most
respects, and in fact are coded with normal def
statements. However, when created,
they are automatically made to implement the iteration protocol so
that they can appear in iteration contexts. We studied iterators in
Chapter 14; here,
we’ll revisit them to see how they relate to generators.
Unlike normal functions that return a value and exit, generator functions automatically suspend and resume their execution and state around the point of value generation. Because of that, they are often a useful alternative to both computing an entire series of values up front and manually saving and restoring state in classes. Because the state that generator functions retain when they are suspended includes their entire local scope, their local variables retain information and make it available when the functions are resumed.
The chief code difference between generator and normal
functions is that a generator yields a value,
rather than returning one—the yield
statement suspends the function
and sends a value back to the caller, but retains enough state to
enable the function to resume from where it left off. When
resumed, the function continues execution immediately after the
last yield
run. From the
function’s perspective, this allows its code to produce a series
of values over time, rather than computing them all at once and
sending them back in something like a list.
To truly understand generator functions, you need to
know that they are closely bound up with the notion of the
iteration protocol in Python. As we’ve seen, iterable objects define a
__next__
method, which either
returns the next item in the iteration, or raises the special
StopIteration
exception to end
the iteration. An object’s iterator is fetched with the iter
built-in function.
Python for
loops, and all
other iteration contexts, use this iteration protocol to step
through a sequence or value generator, if the protocol is
supported; if not, iteration falls back on repeatedly indexing
sequences instead.
To support this protocol, functions containing a yield
statement are compiled specially as
generators. When called, they return a
generator object that supports the iteration interface with an
automatically created method named __next__
to resume execution. Generator
functions may also have a return
statement that, along with
falling off the end of the def
block, simply terminates the generation of values—technically, by
raising a StopIteration
exception after any normal function exit actions. From the
caller’s perspective, the generator’s __next__
method resumes the function and
runs until either the next yield
result is returned or a StopIteration
is raised.
The net effect is that generator functions, coded as
def
statements containing
yield
statements, are
automatically made to support the iteration protocol and thus may
be used in any iteration context to produce results over time and
on demand.
As noted in Chapter 14, in Python
2.6 and earlier, iterable objects define a method named next
instead of __next__
. This includes the generator
objects we are using here. In 3.0 this method is renamed to
__next__
. The next
built-in function is provided as
a convenience and portability tool: next(I)
is the same as I.__next__()
in 3.0 and I.next()
in 2.6. Prior to 2.6,
programs simply call I.next()
instead to iterate manually.
To illustrate generator basics, let’s turn to some code. The following code defines a generator function that can be used to generate the squares of a series of numbers over time:
>>>def gensquares(N):
...for i in range(N):
...yield i ** 2
# Resume here later ...
This function yields a value, and so returns to its caller,
each time through the loop; when it is resumed, its prior state is
restored and control picks up again immediately after the yield
statement. For example, when it’s
used in the body of a for
loop,
control returns to the function after its yield
statement each time through the
loop:
>>>for i in gensquares(5):
# Resume the function ...print(i, end=' : ')
# Print last yielded value ... 0 : 1 : 4 : 9 : 16 : >>>
To end the generation of values, functions either use a
return
statement with no value
or simply allow control to fall off the end of the function
body.
If you want to see what is going on inside the for
, call the generator function
directly:
>>>x = gensquares(4)
>>>x
<generator object at 0x0086C378>
You get back a generator object that supports the iteration
protocol we met in Chapter 14—the generator
object has a __next__
method
that starts the function, or resumes it from where it last yielded
a value, and raises a StopIteration
exception when the end of
the series of values is reached. For convenience, the next(X)
built-in calls an object’s
X.__next__()
method for
us:
>>>next(x)
# Same as x.__next__() in 3.0 0 >>>next(x)
# Use x.next() or next() in 2.6 1 >>>next(x)
4 >>>next(x)
9 >>>next(x)
Traceback (most recent call last):...more text omitted...
StopIteration
As we learned in Chapter 14, for
loops (and other iteration contexts)
work with generators in the same way—by calling the __next__
method repeatedly, until an
exception is caught. If the object to be iterated over does not
support this protocol, for
loops instead use the indexing protocol to iterate.
Note that in this example, we could also simply build the list of yielded values all at once:
>>>def buildsquares(n):
...res = []
...for i in range(n): res.append(i ** 2)
...return res
... >>>for x in buildsquares(5): print(x, end=' : ')
... 0 : 1 : 4 : 9 : 16 :
For that matter, we could use any of the for
loop, map
, or list comprehension
techniques:
>>>for x in [n ** 2 for n in range(5)]:
...print(x, end=' : ')
... 0 : 1 : 4 : 9 : 16 : >>>for x in map((lambda n: n ** 2), range(5)):
...print(x, end=' : ')
... 0 : 1 : 4 : 9 : 16 :
However, generators can be better in terms of both memory use and performance. They allow functions to avoid doing all the work up front, which is especially useful when the result lists are large or when it takes a lot of computation to produce each value. Generators distribute the time required to produce the series of values among loop iterations.
Moreover, for more advanced uses, generators can provide a simpler alternative to manually saving the state between iterations in class objects—with generators, variables accessible in the function’s scopes are saved and restored automatically.[44] We’ll discuss class-based iterators in more detail in Part VI.
In Python 2.5, a send
method was added to the generator function protocol. The send
method advances to the next item in
the series of results, just like __next__
, but also provides a way for
the caller to communicate with the generator, to affect its
operation.
Technically, yield
is now
an expression form that returns the item passed to send
, not a statement (though it can be
called either way—as yield X
,
or A = (yield X)
). The
expression must be enclosed in parentheses unless it’s the only
item on the right side of the assignment statement. For example,
X = yield Y
is OK, as is
X = (yield Y) + 42
.
When this extra protocol is used, values are sent into a
generator G
by calling G.send(
value
)
. The generator’s code is then resumed,
and the yield
expression in the
generator returns the value passed to send
. If the regular G.__next__()
method (or its next(G)
equivalent) is called to
advance, the yield
simply
returns None
. For
example:
>>>def gen():
...for i in range(10):
...X = yield i
...print(X)
... >>>G = gen()
>>>next(G)
# Must call next() first, to start generator 0 >>>G.send(77)
# Advance, and send value to yield expression 77 1 >>>G.send(88)
88 2 >>>next(G)
# next() and X.__next__() send None None 3
The send
method can be
used, for example, to code a generator that its caller can
terminate by sending a termination code, or redirect by passing a
new position. In addition, generators in 2.5 also support a
throw(
type
)
method to raise an exception inside
the generator at the latest yield
, and a close
method that raises a special
GeneratorExit
exception inside
the generator to terminate the iteration. These are advanced
features that we won’t delve into in more detail here; see
reference texts and Python’s standard manuals for more
information.
Note that while Python 3.0 provides a next(X)
convenience built-in that calls
the X.__next__()
method of an
object, other generator methods, like send
, must be called as methods of
generator objects directly (e.g., G.send(X)
). This makes sense if you
realize that these extra methods are implemented on built-in
generator objects only, whereas the __next__
method applies to all iterable
objects (both built-in types and user-defined classes).
In all recent versions of Python, the notions of iterators and list comprehensions are combined in a new feature of the language, generator expressions. Syntactically, generator expressions are just like normal list comprehensions, but they are enclosed in parentheses instead of square brackets:
>>>[x ** 2 for x in range(4)]
# List comprehension: build a list [0, 1, 4, 9] >>>(x ** 2 for x in range(4))
# Generator expression: make an iterable <generator object at 0x011DC648>
In fact, at least on a function basis, coding a list
comprehension is essentially the same as wrapping a generator
expression in a list
built-in
call to force it to produce all its results in a list at
once:
>>> list(x ** 2 for x in range(4))
# List comprehension equivalence
[0, 1, 4, 9]
Operationally, however, generator expressions are very different—instead of building the result list in memory, they return a generator object, which in turn supports the iteration protocol to yield one piece of the result list at a time in any iteration context:
>>>G = (x ** 2 for x in range(4))
>>>next(G)
0 >>>next(G)
1 >>>next(G)
4 >>>next(G)
9 >>>next(G)
Traceback (most recent call last):...more text omitted...
StopIteration
We don’t typically see the next
iterator machinery under the hood of
a generator expression like this because for
loops trigger it for us
automatically:
>>>for num in (x ** 2 for x in range(4)):
...print('%s, %s' % (num, num / 2.0))
... 0, 0.0 1, 0.5 4, 2.0 9, 4.5
As we’ve already learned, every iteration context does this,
including the sum
, map
, and sorted
built-in functions; list
comprehensions; and other iteration contexts we learned about in
Chapter 14, such as
the any
, all
, and list
built-in functions.
Notice that the parentheses are not required around a
generator expression if they are the sole item enclosed in other
parentheses, like those of a function call. Extra parentheses are
required, however, in the second call to sorted
:
>>>sum(x ** 2 for x in range(4))
14 >>>sorted(x ** 2 for x in range(4))
[0, 1, 4, 9] >>>sorted((x ** 2 for x in range(4)), reverse=True)
[9, 4, 1, 0] >>>import math
>>>list(
map(math.sqrt, (x ** 2 for x in range(4))) )
[0.0, 1.0, 2.0, 3.0]
Generator expressions are primarily a memory-space optimization—they do not require the entire result list to be constructed all at once, as the square-bracketed list comprehension does. They may also run slightly slower in practice, so they are probably best used only for very large result sets. A more authoritative statement about performance, though, will have to await the timing script we’ll code later in this chapter.
Interestingly, the same iteration can often be coded with either a generator function or a generator expression. The following generator expression, for example, repeats each character in a string four times:
>>>G = (c * 4 for c in 'SPAM')
# Generator expression >>>list(G)
# Force generator to produce all results ['SSSS', 'PPPP', 'AAAA', 'MMMM']
The equivalent generator function requires slightly more code, but as a multistatement function it will be able to code more logic and use more state information if needed:
>>>def timesfour(S):
# Generator function ...for c in S:
...yield c * 4
... >>>G = timesfour('spam')
>>>list(G)
# Iterate automatically ['ssss', 'pppp', 'aaaa', 'mmmm']
Both expressions and functions support both automatic and
manual iteration—the prior list
call iterates automatically, and the following iterate
manually:
>>>G = (c * 4 for c in 'SPAM'
) >>>I = iter(G)
# Iterate manually >>>next(I)
'SSSS' >>>next(I)
'PPPP' >>>G = timesfour('spam')
>>>I = iter(G)
>>>next(I)
'ssss' >>>next(I)
'pppp'
Notice that we make new generators here to iterate again—as explained in the next section, generators are one-shot iterators.
Both generator functions and generator expressions are
their own iterators and thus support just one active
iteration—unlike some built-in types, you can’t have
multiple iterators of either positioned at different locations in
the set of results. For example, using the prior section’s generator
expression, a generator’s iterator is the generator itself (in fact,
calling iter
on a generator is a
no-op):
>>>G = (c * 4 for c in 'SPAM')
>>>iter(G) is G
# My iterator is myself: G has __next__ True
If you iterate over the results stream manually with multiple iterators, they will all point to the same position:
>>>G = (c * 4 for c in 'SPAM')
# Make a new generator >>>I1 = iter(G)
# Iterate manually >>>next(I1)
'SSSS' >>>next(I1)
'PPPP' >>>I2 = iter(G)
# Second iterator at same position! >>>next(I2)
'AAAA'
Moreover, once any iteration runs to completion, all are exhausted—we have to make a new generator to start again:
>>>list(I1)
# Collect the rest of I1's items ['MMMM'] >>>next(I2)
# Other iterators exhausted too StopIteration >>>I3 = iter(G)
# Ditto for new iterators >>>next(I3)
StopIteration >>>I3 = iter(c * 4 for c in 'SPAM')
# New generator to start over >>>next(I3)
'SSSS'
The same holds true for generator
functions—the following def
statement-based equivalent supports just one active iterator and is
exhausted after one pass:
>>>def timesfour(S):
...for c in S:
...yield c * 4
... >>>G = timesfour('spam')
# Generator functions work the same way >>>iter(G) is G
True >>>I1, I2 = iter(G), iter(G)
>>>next(I1)
'ssss' >>>next(I1)
'pppp' >>>next(I2)
# I2 at same position as I1 'aaaa'
This is different from the behavior of some built-in types, which support multiple iterators and passes and reflect their in-place changes in active iterators:
>>>L = [1, 2, 3, 4]
>>>I1, I2 = iter(L), iter(L)
>>>next(I1)
1 >>>next(I1)
2 >>>next(I2)
# Lists support multiple iterators 1 >>>del L[2:]
# Changes reflected in iterators >>>next(I1)
StopIteration
When we begin coding class-based iterators in Part VI, we’ll see that it’s up to us to decide how many iterations we wish to support for our objects, if any.
To demonstrate the power of iteration tools in action, let’s turn to some more advanced use case examples. Once you know about list comprehensions, generators, and other iteration tools, it turns out that emulating many of Python’s functional built-ins is both straightforward and instructive.
For example, we’ve already seen how the built-in zip
and map
functions combine iterables and
project functions across them, respectively. With multiple sequence
arguments, map
projects the
function across items taken from each sequence in much the same way
that zip
pairs them up:
>>>S1 = 'abc'
>>>S2 = 'xyz123'
>>>list(zip(S1, S2))
# zip pairs items from iterables [('a', 'x'), ('b', 'y'), ('c', 'z')] # zip pairs items, truncates at shortest >>>list(zip([−2, −1, 0, 1, 2]))
# Single sequence: 1-ary tuples [(−2,), (−1,), (0,), (1,), (2,)] >>>list(zip([1, 2, 3], [2, 3, 4, 5]))
# N sequences: N-ary tuples [(1, 2), (2, 3), (3, 4)] # map passes paired itenms to a function, truncates >>>list(map(abs, [−2, −1, 0, 1, 2]))
# Single sequence: 1-ary function [2, 1, 0, 1, 2] >>>list(map(pow, [1, 2, 3], [2, 3, 4, 5]))
# N sequences: N-ary function [1, 8, 81]
Though they’re being used for different purposes, if you study
these examples long enough, you might notice a relationship between
zip
results and mapped function
arguments that our next example can exploit.
Although the map
and zip
built-ins are fast and
convenient, it’s always possible to emulate them in code of our
own. In the preceding chapter, for example, we saw a function that
emulated the map
built-in for a
single sequence argument. It doesn’t take much more work to allow
for multiple sequences, as the built-in does:
# map(func, seqs...) workalike with zip
def mymap(func, *seqs):
res = []
for args in zip(*seqs):
res.append(func(*args))
return res
print(mymap(abs, [−2, −1, 0, 1, 2]))
print(mymap(pow, [1, 2, 3], [2, 3, 4, 5]))
This version relies heavily upon the special *args
argument-passing syntax—it
collects multiple sequence (really, iterable) arguments, unpacks
them as zip
arguments to
combine, and then unpacks the paired zip
results as arguments to the
passed-in function. That is, we’re using the fact that the zipping
is essentially a nested operation in mapping. The test code at the
bottom applies this to both one and two sequences to produce this
output (the same we would get with the built-in map
):
[2, 1, 0, 1, 2] [1, 8, 81]
Really, though, the prior version exhibits the classic
list comprehension pattern, building a list
of operation results within a for
loop. We can code our map more
concisely as an equivalent one-line list comprehension:
# Using a list comprehension
def mymap(func, *seqs):
return [func(*args) for args in zip(*seqs)]
print(mymap(abs, [−2, −1, 0, 1, 2]))
print(mymap(pow, [1, 2, 3], [2, 3, 4, 5]))
When this is run the result is the same as before, but the
code is more concise and might run faster (more on performance in
the section Timing Iteration Alternatives).
Both of the preceding mymap
versions build result lists all at once, though, and this can
waste memory for larger lists. Now that we know about
generator functions and expressions, it’s
simple to recode both these alternatives to produce results on
demand instead:
# Using generators: yield and (...)
def mymap(func, *seqs):
res = []
for args in zip(*seqs):
yield func(*args)
def mymap(func, *seqs):
return (func(*args) for args in zip(*seqs))
These versions produce the same results but return
generators designed to support the iteration protocol—the first
yields one result at a time, and the second returns a generator
expression’s result to do the same. They produce the same results
if we wrap them in list
calls
to force them to produce their values all at once:
print(list(mymap(abs, [−2, −1, 0, 1, 2]))) print(list(mymap(pow, [1, 2, 3], [2, 3, 4, 5])))
No work is really done here until the list
calls force the generators to run,
by activating the iteration protocol. The generators returned by
these functions themselves, as well as that returned by the Python
3.0 flavor of the zip
built-in
they use, produce results only on demand.
Of course, much of the magic in the examples shown so
far lies in their use of the zip
built-in to pair arguments from
multiple sequences. You’ll also note that our map
workalikes are really emulating the
behavior of the Python 3.0 map
—they truncate at the length of the
shortest sequence, and they do not support the notion of padding
results when lengths differ, as map
does in Python 2.X with a None
argument:
C:misc>c:python26python
>>>map(None, [1, 2, 3], [2, 3, 4, 5])
[(1, 2), (2, 3), (3, 4), (None, 5)] >>>map(None, 'abc', 'xyz123')
[('a', 'x'), ('b', 'y'), ('c', 'z'), (None, '1'), (None, '2'), (None, '3')]
Using iteration tools, we can code workalikes that emulate
both truncating zip
and 2.6’s
padding map
—these turn out to
be nearly the same in code:
# zip(seqs...) and 2.6 map(None, seqs...) workalikes
def myzip(*seqs):
seqs = [list(S) for S in seqs]
res = []
while all(seqs):
res.append(tuple(S.pop(0) for S in seqs))
return res
def mymapPad(*seqs, pad=None):
seqs = [list(S) for S in seqs]
res = []
while any(seqs):
res.append(tuple((S.pop(0) if S else pad) for S in seqs))
return res
S1, S2 = 'abc', 'xyz123'
print(myzip(S1, S2))
print(mymapPad(S1, S2))
print(mymapPad(S1, S2, pad=99))
Both of the functions coded here work on any type of
iterable object, because they run their arguments through the
list
built-in to force result
generation (e.g., files would work as arguments, in addition to
sequences like strings). Notice the use of the all
and any
built-ins here—these return True
if all and any items in an iterable
are True
(or equivalently,
nonempty), respectively. These built-ins are used to stop looping
when any or all of the listified arguments become empty after
deletions.
Also note the use of the Python 3.0
keyword-only argument, pad
; unlike the 2.6 map
, our version will allow any pad
object to be specified (if you’re using 2.6, use a **kargs
form to support this option
instead; see Chapter 18 for details). When these
functions are run, the following results are printed—a zip
, and two padding map
s:
[('a', 'x'), ('b', 'y'), ('c', 'z')] [('a', 'x'), ('b', 'y'), ('c', 'z'), (None, '1'), (None, '2'), (None, '3')] [('a', 'x'), ('b', 'y'), ('c', 'z'), (99, '1'), (99, '2'), (99, '3')]
These functions aren’t amenable to list comprehension
translation because their loops are too specific. As before,
though, while our zip
and
map
workalikes currently build
and return result lists, it’s just as easy to turn them into
generators with yield
so that they each return one piece
of their result set at a time. The results are the same as before,
but we need to use list
again
to force the generators to yield their values for display:
# Using generators: yield
def myzip(*seqs):
seqs = [list(S) for S in seqs]
while all(seqs):
yield tuple(S.pop(0) for S in seqs)
def mymapPad(*seqs, pad=None):
seqs = [list(S) for S in seqs]
while any(seqs):
yield tuple((S.pop(0) if S else pad) for S in seqs)
S1, S2 = 'abc', 'xyz123'
print(list(myzip(S1, S2)))
print(list(mymapPad(S1, S2)))
print(list(mymapPad(S1, S2, pad=99)))
Finally, here’s an alternative implementation of our
zip
and map
emulators—rather than deleting
arguments from lists with the pop
method, the following versions do
their job by calculating the minimum and maximum
argument lengths. Armed with these lengths,
it’s easy to code nested list comprehensions to step through
argument index ranges:
# Alternate implementation with lengths
def myzip(*seqs):
minlen = min(len(S) for S in seqs)
return [tuple(S[i] for S in seqs) for i in range(minlen)]
def mymapPad(*seqs, pad=None):
maxlen = max(len(S) for S in seqs)
index = range(maxlen)
return [tuple((S[i] if len(S) > i else pad) for S in seqs) for i in index]
S1, S2 = 'abc', 'xyz123'
print(myzip(S1, S2))
print(mymapPad(S1, S2))
print(mymapPad(S1, S2, pad=99))
Because these use len
and
indexing, they assume that arguments are sequences or similar, not
arbitrary iterables. The outer comprehensions here step through
argument index ranges, and the inner comprehensions (passed to
tuple
) step through the
passed-in sequences to pull out arguments in parallel. When
they’re run, the results are as before.
Most strikingly, generators and iterators seem to run
rampant in this example. The arguments passed to min
and max
are generator expressions, which run
to completion before the nested comprehensions begin iterating.
Moreover, the nested list comprehensions employ two levels of
delayed evaluation—the Python 3.0 range
built-in is an iterable, as is the
generator expression argument to tuple
.
In fact, no results are produced here until the square brackets of the list comprehensions request
values to place in the result list—they force the comprehensions
and generators to run. To turn these functions themselves into
generators instead of list builders, use parentheses instead of
square brackets again. Here’s the case for our zip
:
# Using generators: (...)
def myzip(*seqs):
minlen = min(len(S) for S in seqs)
return (tuple(S[i] for S in seqs) for i in range(minlen))
print(list(myzip(S1, S2)))
In this case, it takes a list
call to activate the generators and
iterators to produce their results. Experiment with these on your
own for more details. Developing further coding alternatives is
left as a suggested exercise (see also the sidebar for investigation of one such
option).
Finally, although we’ve focused on coding value generators ourselves in this section, don’t forget that many built-in types behave in similar ways—as we saw in Chapter 14, for example, dictionaries have iterators that produce keys on each iteration:
>>>D = {'a':1, 'b':2, 'c':3}
>>>x = iter(D)
>>>next(x)
'a' >>>next(x)
'c'
Like the values produced by handcoded generators, dictionary
keys may be iterated over both manually and with automatic iteration
tools including for
loops,
map
calls, list comprehensions,
and the many other contexts we met in Chapter 14:
>>>for key in D:
...print(key, D[key])
... a 1 c 3 b 2
As we’ve also seen, for file iterators, Python simply loads lines from the file on demand:
>>>for line in open('temp.txt'):
...print(line, end='')
... Tis but a flesh wound.
While built-in type iterators are bound to a specific type of
value generation, the concept is similar to generators we code with
expressions and functions. Iteration contexts like for
loops accept any iterable, whether
user-defined or built-in.
Although beyond the scope of this chapter, it is also possible
to implement arbitrary user-defined generator objects with
classes that conform to the iteration protocol.
Such classes define a special __iter__
method run by the iter
built-in function that returns an
object having a __next__
method
run by the next
built-in function
(a __getitem__
indexing method is
also available as a fallback option for iteration).
The instance objects created from such a class are considered
iterable and may be used in for
loops and all other iteration contexts. With classes, though, we
have access to richer logic and data structuring options than other
generator constructs can offer.
The iterator story won’t really be complete until we’ve seen how it maps to classes, too. For now, we’ll have to settle for postponing its conclusion until we study class-based iterators in Chapter 29.
We’ve been focusing on list comprehensions and generators in this chapter, but keep in mind that there are two other comprehension expression forms: set and dictionary comprehensions are also available as of Python 3.0. We met these briefly in Chapters 5 and 8, but with our new knowledge of comprehensions and generators, you should now be able to grasp these 3.0 extensions in full:
For sets, the new literal form {1, 3, 2}
is equivalent to set([1, 3, 2])
, and the new set
comprehension syntax {f(x) for x in S if
P(x)}
is like the generator expression set(f(x) for x in S if P(x))
, where
f(x)
is an arbitrary
expression.
For dictionaries, the new dictionary
comprehension syntax {key: val for (key,
val) in zip(keys, vals)}
works like the form dict(zip(keys, vals))
, and {x: f(x) for x in items}
is like the
generator expression dict((x, f(x)) for x
in items)
.
Here’s a summary of all the comprehension alternatives in 3.0. The last two are new and are not available in 2.6:
>>>[x * x for x in range(10)]
# List comprehension: builds list [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] # like list(generator expr) >>>(x * x for x in range(10))
# Generator expression: produces items <generator object at 0x009E7328> # Parens are often optional >>>{x * x for x in range(10)}
# Set comprehension, new in 3.0 {0, 1, 4, 81, 64, 9, 16, 49, 25, 36} # {x, y} is a set in 3.0 too >>>{x: x * x for x in range(10)}
# Dictionary comprehension, new in 3.0 {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
In a sense, set and dictionary comprehensions are just syntactic sugar for passing generator expressions to the type names. Because both accept any iterable, a generator works well here:
>>>{x * x for x in range(10)}
# Comprehension {0, 1, 4, 81, 64, 9, 16, 49, 25, 36} >>>set(x * x for x in range(10))
# Generator and type name {0, 1, 4, 81, 64, 9, 16, 49, 25, 36} >>>{x: x * x for x in range(10)}
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81} >>>dict((x, x * x) for x in range(10))
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
As for list comprehensions, though, we can always build the result objects with manual code, too. Here are statement-based equivalents of the last two comprehensions:
>>>res = set()
>>>for x in range(10):
# Set comprehension equivalent ...res.add(x * x)
... >>>res
{0, 1, 4, 81, 64, 9, 16, 49, 25, 36} >>>res = {}
>>>for x in range(10):
# Dict comprehension equivalent ...res[x] = x * x
... >>>res
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
Notice that although both forms accept iterators, they have no notion of generating results on demand—both forms build objects all at once. If you mean to produce keys and values upon request, a generator expression is more appropriate:
>>>G = ((x, x * x) for x in range(10))
>>>next(G)
(0, 0) >>>next(G)
(1, 1)
Like list comprehensions and generator expressions, both set
and dictionary comprehensions support nested associated if
clauses to filter items out of the
result—the following collect squares of even items (i.e., items
having no remainder for division by 2) in a range:
>>>[x * x for x in range(10) if x % 2 == 0]
# Lists are ordered [0, 4, 16, 36, 64] >>>{x * x for x in range(10) if x % 2 == 0}
# But sets are not {0, 16, 4, 64, 36} >>>{x: x * x for x in range(10) if x % 2 == 0}
# Neither are dict keys {0: 0, 8: 64, 2: 4, 4: 16, 6: 36}
Nested for
loops work as
well, though the unordered and no-duplicates nature of both types of
objects can make the results a bit less straightforward to
decipher:
>>>[x + y for x in [1, 2, 3] for y in [4, 5, 6]]
# Lists keep duplicates [5, 6, 7, 6, 7, 8, 7, 8, 9] >>>{x + y for x in [1, 2, 3] for y in [4, 5, 6]}
# But sets do not {8, 9, 5, 6, 7} >>>{x: y for x in [1, 2, 3] for y in [4, 5, 6]}
# Neither do dict keys {1: 6, 2: 6, 3: 6}
Like list comprehensions, the set and dictionary varieties can also iterate over any type of iterator—lists, strings, files, ranges, and anything else that supports the iteration protocol:
>>>{x + y for x in 'ab' for y in 'cd'}
{'bd', 'ac', 'ad', 'bc'} >>>{x + y: (ord(x), ord(y)) for x in 'ab' for y in 'cd'}
{'bd': (98, 100), 'ac': (97, 99), 'ad': (97, 100), 'bc': (98, 99)} >>>{k * 2 for k in ['spam', 'ham', 'sausage'] if k[0] == 's'}
{'sausagesausage', 'spamspam'} >>>{k.upper(): k * 2 for k in ['spam', 'ham', 'sausage'] if k[0] == 's'}
{'SAUSAGE': 'sausagesausage', 'SPAM': 'spamspam'}
For more details, experiment with these tools on your own.
They may or may not have a performance advantage over the generator
or for
loop alternatives, but we
would have to time their performance explicitly to be sure—which
seems a natural segue to the next section.
We’ve met quite a few iteration alternatives in this book. To summarize, let’s work through a larger case study that pulls together some of the things we’ve learned about iteration and functions.
I’ve mentioned a few times that list comprehensions have a speed
performance advantage over for
loop
statements, and that map
performance can be better or worse depending on call patterns. The
generator expressions of the prior sections tend to be slightly slower
than list comprehensions, though they minimize memory space requirements.
All that’s true today, but relative performance can vary over time because Python’s internals are constantly being changed and optimized. If you want to verify their performance for yourself, you need to time these alternatives on your own computer and your own version of Python.
Luckily, Python makes it easy to time code. To see how the iteration options stack up, let’s start with a simple but general timer utility function coded in a module file, so it can be used in a variety of programs:
# File mytimer.py
import time
reps = 1000
repslist = range(reps)
def timer(func, *pargs, **kargs):
start = time.clock()
for i in repslist:
ret = func(*pargs, **kargs)
elapsed = time.clock() - start
return (elapsed, ret)
Operationally, this module times calls to any function with any positional and keyword arguments by fetching the start time, calling the function a fixed number of times, and subtracting the start time from the stop time. Points to notice:
Python’s time
module
gives access to the current time, with precision that varies per
platform. On Windows, this call is claimed to give microsecond
granularity and so is very accurate.
The range
call is
hoisted out of the timing loop, so its construction cost is not
charged to the timed function in Python 2.6. In 3.0 range
is an iterator, so this step
isn’t required (but doesn’t hurt).
The reps
count is a
global that importers can change if needed: mytimer.reps = N
.
When complete, the total elapsed time for all calls is returned in a tuple, along with the timed function’s final return value so callers can verify its operation.
From a larger perspective, because this function is coded in a module file, it becomes a generally useful tool anywhere we wish to import it. You’ll learn more about modules and imports in the next part of this book—simply import the module and call the function to use this file’s timer (and see Chapter 3’s coverage of module attributes if you need a refresher).
To time iteration tool speed, run the following script—it uses the timer module we wrote to time the relative speeds of the list construction techniques we’ve studied:
# File timeseqs.py import sys, mytimer # Import timer function reps = 10000 repslist = range(reps) # Hoist range out in 2.6 def forLoop(): res = [] for x in repslist: res.append(abs(x)) return res def listComp(): return [abs(x) for x in repslist] def mapCall(): return list(map(abs, repslist)) # Use list in 3.0 only def genExpr(): return list(abs(x) for x in repslist) # list forces results def genFunc(): def gen(): for x in repslist: yield abs(x) return list(gen()) print(sys.version) for test in (forLoop, listComp, mapCall, genExpr, genFunc): elapsed, result = mytimer.timer(test) print ('-' * 33) print ('%-9s: %.5f => [%s...%s]' % (test.__name__, elapsed, result[0], result[-1]))
This script tests five alternative ways to build lists of results and, as shown, executes on the order of 10 million steps for each—that is, each of the five tests builds a list of 10,000 items 1,000 times.
Notice how we have to run the generator expression and
function results through the built-in list
call to force them to yield all of
their values; if we did not, we would just produce generators that
never do any real work. In Python 3.0 (only) we must do the same for the map
result, since it is now an iterable
object as well. Also notice how the code at the bottom steps through
a tuple of five function objects and prints the __name__
of each: as we’ve seen, this is a
built-in attribute that gives a function’s name.[45]
When the script of the prior section is run under Python
3.0, I get these results on my Windows Vista laptop—map
is slightly faster than list
comprehensions, both are quicker than for
loops, and generator expressions and
functions place in the middle:
C:misc> c:python30python timeseqs.py
3.0.1 (r301:69561, Feb 13 2009, 20:04:18) [MSC v.1500 32 bit (Intel)]
---------------------------------
forLoop : 2.64441 => [0...9999]
---------------------------------
listComp : 1.60110 => [0...9999]
---------------------------------
mapCall : 1.41977 => [0...9999]
---------------------------------
genExpr : 2.21758 => [0...9999]
---------------------------------
genFunc : 2.18696 => [0...9999]
If you study this code and its output long enough, you’ll
notice that generator expressions run slower than list
comprehensions. Although wrapping a generator expression in a
list
call makes it functionally
equivalent to a square-bracketed list comprehension, the internal
implementations of the two expressions appear to differ (though
we’re also effectively timing the list
call for the generator test):
return [abs(x) for x in range(size)] # 1.6 seconds return list(abs(x) for x in range(size)) # 2.2 seconds: differs internally
Interestingly, when I ran this on Windows XP with Python 2.5
for the prior edition of this book, the results were relatively
similar—list comprehensions were nearly twice as fast as equivalent
for
loop statements, and map
was slightly quicker than list
comprehensions when mapping a built-in function such as abs
(absolute value). I didn’t test
generator functions then, and the output format wasn’t quite as
grandiose:
2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit (Intel)] forStatement => 6.10899996758 listComprehension => 3.51499986649 mapFunction => 2.73399996758 generatorExpression => 4.11600017548
The fact that the actual 2.5 test times listed here are over
two times as slow as the output I showed earlier is likely due to my
using a quicker laptop for the more recent test, not due to
improvements in Python 3.0. In fact, all the 2.6 results for this
script are slightly quicker than 3.0 on this same machine if the
list
call is removed from the
map
test to avoid creating the
results list twice (try this on your own to verify).
Watch what happens, though, if we change this script to
perform a real operation on each iteration, such as addition,
instead of calling a trivial built-in function like abs
(the omitted parts of the following
are the same as before):
# File timeseqs.py ... ... def forLoop(): res = [] for x in repslist: res.append(x + 10) return res def listComp(): return [x + 10 for x in repslist] def mapCall(): return list(map((lambda x: x + 10), repslist)) # list in 3.0 only def genExpr(): return list(x + 10 for x in repslist) # list in 2.6 + 3.0 def genFunc(): def gen(): for x in repslist: yield x + 10 return list(gen()) ... ...
Now the need to call a user-defined function for the map
call makes it slower than the for
loop statements, despite the fact that
the looping statements version is larger in terms of code. On Python
3.0:
C:misc> c:python30python timeseqs.py
3.0.1 (r301:69561, Feb 13 2009, 20:04:18) [MSC v.1500 32 bit (Intel)]
---------------------------------
forLoop : 2.60754 => [10...10009]
---------------------------------
listComp : 1.57585 => [10...10009]
---------------------------------
mapCall : 3.10276 => [10...10009]
---------------------------------
genExpr : 1.96482 => [10...10009]
---------------------------------
genFunc : 1.95340 => [10...10009]
The Python 2.5 results on a slower machine were again relatively similar in the prior edition, but twice as slow due to test machine differences:
2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit (Intel)] forStatement => 5.25699996948 listComprehension => 2.68400001526 mapFunction => 5.96900010109 generatorExpression => 3.37400007248
Because the interpreter optimizes so much internally,
performance analysis of Python code like this is a very tricky
affair. It’s virtually impossible to guess which method will perform
the best—the best you can do is time your own code, on your
computer, with your version of Python. In this case, all we should
say for certain is that on this Python, using a user-defined
function in map
calls can slow
performance by at least a factor of 2, and that list comprehensions
run quickest for this test.
As I’ve mentioned before, however, performance should not be your primary concern when writing Python code—the first thing you should do to optimize Python code is to not optimize Python code! Write for readability and simplicity first, then optimize later, if and only if needed. It could very well be that any of the five alternatives is quick enough for the data sets your program needs to process; if so, program clarity should be the chief goal.
The timing module of the prior section works, but it’s a bit primitive on multiple fronts:
It always uses the time.clock
call to time code. While
that option is best on Windows, the time.time
call may provide better
resolution on some Unix platforms.
Adjusting the number of repetitions requires changing
module-level globals—a less than ideal arrangement if the
timer
function is being used
and shared by multiple importers.
As is, the timer works by running the test function a large number of times. To account for random system load fluctuations, it might be better to select the best time among all the tests, instead of the total time.
The following alternative implements a more sophisticated
timer module that addresses all three points by selecting a timer
call based on platform, allowing the repeat count to be passed in as
a keyword argument named _reps
,
and providing a best-of-N alternative timing function:
# File mytimer.py (2.6 and 3.0) """ timer(spam, 1, 2, a=3, b=4, _reps=1000) calls and times spam(1, 2, a=3) _reps times, and returns total time for all runs, with final result; best(spam, 1, 2, a=3, b=4, _reps=50) runs best-of-N timer to filter out any system load variation, and returns best time among _reps tests """ import time, sys if sys.platform[:3] == 'win': timefunc = time.clock # Use time.clock on Windows else: timefunc = time.time # Better resolution on some Unix platforms def trace(*args): pass # Or: print args def timer(func, *pargs, **kargs): _reps = kargs.pop('_reps', 1000) # Passed-in or default reps trace(func, pargs, kargs, _reps) repslist = range(_reps) # Hoist range out for 2.6 lists start = timefunc() for i in repslist: ret = func(*pargs, **kargs) elapsed = timefunc() - start return (elapsed, ret) def best(func, *pargs, **kargs): _reps = kargs.pop('_reps', 50) best = 2 ** 32 for i in range(_reps): (time, ret) = timer(func, *pargs, _reps=1, **kargs) if time < best: best = time return (best, ret)
This module’s docstring at the top of the file describes its
intended usage. It uses dictionary pop
operations to remove the _reps
argument from arguments intended for
the test function and provide it with a default, and it traces
arguments during development if you change its trace
function to print
. To test with this new timer module
on either Python 3.0 or 2.6, change the timing script as follows
(the omitted code in the test functions of this version use the
x + 1
operation for each test, as
coded in the prior section):
# File timeseqs.py
import sys, mytimer
reps = 10000
repslist = range(reps)
def forLoop(): ...
def listComp(): ...
def mapCall(): ...
def genExpr(): ...
def genFunc(): ...
print(sys.version)
for tester in (mytimer.timer, mytimer.best):
print('<%s>' % tester.__name__)
for test in (forLoop, listComp, mapCall, genExpr, genFunc):
elapsed, result = tester(test)
print ('-' * 35)
print ('%-9s: %.5f => [%s...%s]' %
(test.__name__, elapsed, result[0], result[-1]))
When run under Python 3.0, the timing results are essentially the same as before, and relatively the same for both the total-of-N and best-of-N timing techniques—running tests many times seems to do as good a job filtering out system load fluctuations as taking the best case, but the best-of-N scheme may be better when testing a long-running function. The results on my machine are as follows:
C:misc> c:python30python timeseqs.py
3.0.1 (r301:69561, Feb 13 2009, 20:04:18) [MSC v.1500 32 bit (Intel)]
<timer>
-----------------------------------
forLoop : 2.35371 => [10...10009]
-----------------------------------
listComp : 1.29640 => [10...10009]
-----------------------------------
mapCall : 3.16556 => [10...10009]
-----------------------------------
genExpr : 1.97440 => [10...10009]
-----------------------------------
genFunc : 1.95072 => [10...10009]
<best>
-----------------------------------
forLoop : 0.00193 => [10...10009]
-----------------------------------
listComp : 0.00124 => [10...10009]
-----------------------------------
mapCall : 0.00268 => [10...10009]
-----------------------------------
genExpr : 0.00164 => [10...10009]
-----------------------------------
genFunc : 0.00165 => [10...10009]
The times reported by the best-of-N timer here are small, of
course, but they might become significant if your program iterates
many times over large data sets. At least in terms of relative
performance, list comprehensions appear best in most cases; map
is only slightly better when built-ins
are applied.
We can also make use of Python 3.0
keyword-only arguments here to simplify the
timer module’s code. As we learned in Chapter 19, keyword-only arguments are
ideal for configuration options such as our functions’ _reps
argument. They must be coded after
a *
and before a **
in the function header, and in a
function call they must be passed by keyword and appear before the
**
if used. Here’s a
keyword-only-based alternative to the prior module. Though
simpler, it compiles and runs under Python 3.X only, not
2.6:
# File mytimer.py (3.X only)
"""
Use 3.0 keyword-only default arguments, instead of ** and dict pops.
No need to hoist range() out of test in 3.0: a generator, not a list
"""
import time, sys
trace = lambda *args: None # or print
timefunc = time.clock if sys.platform == 'win32' else time.time
def timer(func, *pargs, _reps=1000, **kargs):
trace(func, pargs, kargs, _reps)
start = timefunc()
for i in range(_reps):
ret = func(*pargs, **kargs)
elapsed = timefunc() - start
return (elapsed, ret)
def best(func, *pargs, _reps=50, **kargs):
best = 2 ** 32
for i in range(_reps):
(time, ret) = timer(func, *pargs, _reps=1, **kargs)
if time < best: best = time
return (best, ret)
This version is used the same way as and produces results identical to the prior version, not counting negligible test time differences from run to run:
C:misc>c:python30python timeseqs.py
...same results as before...
In fact, for variety we can also test this version of the module from the interactive prompt, completely independent of the sequence timer script—it’s a general-purpose tool:
C:misc>c:python30python
>>>from mytimer import timer, best
>>> >>>def power(X, Y): return X ** Y
# Test function ... >>>timer(power, 2, 32)
# Total time, last result (0.002625403507987747, 4294967296) >>>timer(power, 2, 32, _reps=1000000)
# Override defult reps (1.1822605247314932, 4294967296) >>>timer(power, 2, 100000)[0]
# 2 ** 100,000 tot time @1,000 reps 2.2496919999608878 >>>best(power, 2, 32)
# Best time, last result (5.58730229727189e-06, 4294967296) >>>best(power, 2, 100000)[0]
# 2 ** 100,000 best time 0.0019937589833460834 >>>best(power, 2, 100000, _reps=500)[0]
# Override default reps 0.0019845399345541637
For trivial functions like the one tested in this
interactive session, the costs of the timer’s code are probably as
significant as those of the timed function, so you should not take
timer results too absolutely (we are timing more than just
X ** Y
here). The timer’s
results can help you judge relative speeds of coding alternatives,
though, and may be more meaningful for longer-running operations
like the following—calculating 2 to the power one million takes an
order of magnitude (power of 10) longer than the preceding
2**100,000
:
>>>timer(power, 2, 1000000, _reps=1)[0]
# 2 ** 1,000,000: total time 0.088112804839710179 >>>timer(power, 2, 1000000, _reps=10)[0]
0.40922470593329763 >>>best(power, 2, 1000000, _reps=1)[0]
# 2 ** 1,000,000: best time 0.086550036387279761 >>>best(power, 2, 1000000, _reps=10)[0]
# 10 is sometimes as good as 50 0.029616752967200455 >>>best(power, 2, 1000000, _reps=50)[0]
# Best resolution 0.029486918030102061
Again, although the times measured here are small, the differences can be significant in programs that compute powers often.
See Chapter 19 for more on keyword-only arguments in 3.0; they can simplify code for configurable tools like this one but are not backward compatible with 2.X Pythons. If you want to compare 2.X and 3.X speed, for example, or support programmers using either Python line, the prior version is likely a better choice. If you’re using Python 2.6, the above session runs the same with the prior version of the timer module.
For more insight, try modifying the repetition counts used
by these modules, or explore the alternative timeit
module in Python’s standard library,
which automates timing of code, supports command-line usage modes,
and finesses some platform-specific issues. Python’s manuals
document its use.
You might also want to look at the profile
standard library module for a
complete source code profiler tool—we’ll learn more about it in
Chapter 35 in the context of
development tools for large projects. In general, you should profile
code to isolate bottlenecks before recoding and timing alternatives
as we’ve done here.
It might be useful to experiment with the new str.format
method in Python 2.6 and 3.0
instead of the %
formatting
expression (which could potentially be deprecated in the future!),
by changing the timing script’s formatted print
lines as follows:
print('<%s>' % tester.__name__) # From expression print('<{0}>'.format(tester.__name__)) # To method call print ('%-9s: %.5f => [%s...%s]' % (test.__name__, elapsed, result[0], result[-1])) print('{0:<9}: {1:.5f} => [{2}...{3}]'.format( test.__name__, elapsed, result[0], result[-1]))
You can judge the difference between these techniques yourself.
You might try modifying or emulating the timing script to
measure the speed of the 3.0 set and dictionary
comprehensions shown in this chapter, and their for
loop equivalents. Using them is less
common in Python programs than building lists of results, so we’ll
leave this task in the suggested exercise column (and please, no
wagering...).
Finally, keep the timing module we wrote here filed away for
future reference—we’ll repurpose it to measure performance of
alternative numeric square root operations in an exercise at the end
of this chapter. If you’re interested in pursuing this topic
further, we’ll also experiment with techniques for timing dictionary
comprehensions versus for
loops
interactively.[46]
Now that we’ve reached the end of the function story, let’s review some common pitfalls. Functions have some jagged edges that you might not expect. They’re all obscure, and a few have started to fall away from the language completely in recent releases, but most have been known to trip up new users.
As you know, Python classifies names assigned in a function
as locals by default; they live in the
function’s scope and exist only while the function is running. What
you may not realize is that Python detects locals statically, when
it compiles the def
’s code,
rather than by noticing assignments as they happen at runtime. This
leads to one of the most common oddities posted on the Python
newsgroup by beginners.
Normally, a name that isn’t assigned in a function is looked up in the enclosing module:
>>>X = 99
>>>def selector():
# X used but not assigned ...print(X)
# X found in global scope ... >>>selector()
99
Here, the X
in the function
resolves to the X
in the module.
But watch what happens if you add an assignment to X
after the reference:
>>>def selector():
...print(X)
# Does not yet exist! ...X = 88
# X classified as a local name (everywhere) ... # Can also happen for "import X", "def X"... >>>selector()
UnboundLocalError: local variable 'X' referenced before assignment
You get the name usage error shown here, but the reason is
subtle. Python reads and compiles this code when it’s typed
interactively or imported from a module. While compiling, Python
sees the assignment to X
and
decides that X
will be a local
name everywhere in the function. But when the function is actually
run, because the assignment hasn’t yet happened when the print
executes, Python says you’re using
an undefined name. According to its name rules, it should say this;
the local X
is used before being
assigned. In fact, any assignment in a function body makes a name
local. Imports, =
, nested
def
s, nested classes, and so on
are all susceptible to this behavior.
The problem occurs because assigned names are treated as
locals everywhere in a function, not just after the statements where
they’re assigned. The previous example is ambiguous: was the
intention to print the global X
and create a local X
, or is this
a real programming error? Because Python treats X
as a local everywhere, it’s seen as an
error; if you mean to print the global X
, you need to declare it in a global
statement:
>>>def selector():
...global X
# Force X to be global (everywhere) ...print(X)
...X = 88
... >>>selector()
99
Remember, though, that this means the assignment also changes
the global X
, not a local
X
. Within a function, you can’t
use both local and global versions of the same simple name. If you
really meant to print the global and then set a local of the same
name, you’d need to import the enclosing module and use module
attribute notation to get to the global version:
>>>X = 99
>>>def selector():
...import __main__
# Import enclosing module ...print(__main__.X)
# Qualify to get to global version of name ...X = 88
# Unqualified X classified as local ...print(X)
# Prints local version of name ... >>>selector()
99 88
Qualification (the .X
part)
fetches a value from a namespace object. The interactive namespace
is a module called __main__
, so
__main__.X
reaches the global
version of X
. If that isn’t
clear, check out Chapter 17.
In recent versions Python has improved on this story somewhat by issuing for this case the more specific “unbound local” error message shown in the example listing (it used to simply raise a generic name error); this gotcha is still present in general, though.
Default argument values are evaluated and saved when a
def
statement is run, not when
the resulting function is called. Internally, Python saves one
object per default argument attached to the function itself.
That’s usually what you want—because defaults are evaluated at
def
time, it lets you save values
from the enclosing scope, if needed. But because a default retains
an object between calls, you have to be careful about changing
mutable defaults. For instance, the following function uses an empty
list as a default value, and then changes it in-place each time the
function is called:
>>>def saver(x=[]):
# Saves away a list object ...x.append(1)
# Changes same object each time! ...print(x)
... >>>saver([2])
# Default not used [2, 1] >>>saver()
# Default used [1] >>>saver()
# Grows on each call! [1, 1] >>>saver()
[1, 1, 1]
Some see this behavior as a feature—because mutable default arguments retain their state between function calls, they can serve some of the same roles as static local function variables in the C language. In a sense, they work sort of like global variables, but their names are local to the functions and so will not clash with names elsewhere in a program.
To most observers, though, this seems like a gotcha, especially the first time they run into it. There are better ways to retain state between calls in Python (e.g., using classes, which will be discussed in Part VI).
Moreover, mutable defaults are tricky to remember (and to
understand at all). They depend upon the timing of default object
construction. In the prior example, there is just one list object
for the default value—the one created when the def
is executed. You don’t get a new list
every time the function is called, so the list grows with each new
append; it is not reset to empty on each call.
If that’s not the behavior you want, simply make a copy of the default at the start of the function body, or move the default value expression into the function body. As long as the value resides in code that’s actually executed each time the function runs, you’ll get a new object each time through:
>>>def saver(x=None):
...if x is None:
# No argument passed? ...x = []
# Run code to make a new list ...x.append(1)
# Changes new list object ...print(x)
... >>>saver([2])
[2, 1] >>>saver()
# Doesn't grow here [1] >>>saver()
[1]
By the way, the if
statement in this example could almost be
replaced by the assignment x = x or
[]
, which takes advantage of the fact that Python’s
or
returns one of its operand
objects: if no argument was passed, x
would default to None
, so the or
would return the new empty list on the
right.
However, this isn’t exactly the same. If an empty list were
passed in, the or
expression
would cause the function to extend and return a newly created list,
rather than extending and returning the passed-in list like the
if
version. (The expression
becomes [] or []
, which evaluates
to the new empty list on the right; see the section Truth Tests if you don’t recall why). Real program
requirements may call for either behavior.
Today, another way to achieve the effect of mutable defaults in a possibly less confusing way is to use the function attributes we discussed in Chapter 19:
>>>def saver():
...saver.x.append(1)
...print(saver.x)
... >>>saver.x = []
>>>saver()
[1] >>>saver()
[1, 1] >>>saver()
[1, 1, 1]
The function name is global to the function itself, but it need not be declared because it isn’t changed directly within the function. This isn’t used in exactly the same way, but when coded like this, the attachment of an object to the function is much more explicit (and arguably less magical).
In Python functions, return
(and yield
) statements are
optional. When a function doesn’t return a value explicitly, the
function exits when control falls off the end of the function body.
Technically, all functions return a value; if you don’t provide a
return
statement, your function
returns the None
object
automatically:
>>>def proc(x):
...print(x)
# No return is a None return ... >>>x = proc('testing 123...')
testing 123... >>>print(x)
None
Functions such as this without a return
are Python’s equivalent of what are
called “procedures” in some languages. They’re usually invoked as
statements, and the None
results
are ignored, as they do their business without computing a useful
result.
This is worth knowing, because Python won’t tell you if you
try to use the result of a function that doesn’t return one. For
instance, assigning the result of a list append
method won’t raise an error, but
you’ll get back None
, not the
modified list:
>>>list = [1, 2, 3]
>>>list = list.append(4)
# append is a "procedure" >>>print(list)
# append changes list in-place None
As mentioned in Common Coding Gotchas in Chapter 15, such functions do their business as a side effect and are usually designed to be run as statements, not expressions.
We described this gotcha in Chapter 17’s discussion of enclosing function scopes, but as a reminder, be careful about relying on enclosing function scope lookup for variables that are changed by enclosing loops—all such references will remember the value of the last loop iteration. Use defaults to save loop variable values instead (see Chapter 17 for more details on this topic).
This chapter wrapped up our coverage of built-in comprehension and iteration tools. It explored list comprehensions in the context of functional tools and presented generator functions and expressions as additional iteration protocol tools. As a finale, we also measured the performance of iteration alternatives, and we closed with a review of common function-related mistakes to help you avoid pitfalls.
This concludes the functions part of this book. In the next part, we will study modules—the topmost organizational structure in Python, and the structure in which our functions always live. After that, we will explore classes, tools that are largely packages of functions with special first arguments. As we’ll see, user-defined classes can implement objects that tap into the iteration protocol, just like the generators and iterables we met here. Everything we have learned in this part of the book will apply when functions pop up later in the context of class methods.
Before moving on to modules, though, be sure to work through this chapter’s quiz and the exercises for this part of the book, to practice what we’ve learned about functions here.
What is the difference between enclosing a list comprehension in square brackets and parentheses?
How are generators and iterators related?
How can you tell if a function is a generator function?
What does a yield
statement do?
How are map
calls and
list comprehensions related? Compare and contrast the two.
List comprehensions in square brackets produce the result list all at once in memory. When they are enclosed in parentheses instead, they are actually generator expressions—they have a similar meaning but do not produce the result list all at once. Instead, generator expressions return a generator object, which yields one item in the result at a time when used in an iteration context.
Generators are objects that support the iteration
protocol—they have a __next__
method that repeatedly advances to the next item in a series of
results and raises an exception at the end of the series. In
Python, we can code generator functions with def
, generator expressions with
parenthesized list comprehensions, and generator objects with
classes that define a special method named __iter__
(discussed later in the
book).
A generator function has a yield
statement somewhere in its code.
Generator functions are otherwise identical to normal functions
syntactically, but they are compiled specially by Python so as to
return an iterable object when called.
When present, this statement makes Python compile the
function specially as a generator; when called, the function
returns a generator object that supports the iteration protocol.
When the yield
statement is
run, it sends a result back to the caller and suspends the
function’s state; the function can then be resumed after the last
yield
statement, in response to
a next
built-in or __next__
method call issued by the
caller. Generator functions may also have a return
statement, which terminates the
generator.
The map
call is similar
to a list comprehension—both build a new list by collecting the
results of applying an operation to each item in a sequence or
other iterable, one item at a time. The main difference is that
map
applies a function call to
each item, and list comprehensions apply arbitrary expressions.
Because of this, list comprehensions are more general; they can
apply a function call expression like map
, but map
requires a function to apply other
kinds of expressions. List comprehensions also support extended
syntax such as nested for
loops
and if
clauses that subsume the
filter
built-in.
In these exercises, you’re going to start coding more sophisticated programs. Be sure to check the solutions in Part IV, Functions in Appendix B, and be sure to start writing your code in module files. You won’t want to retype these exercises from scratch if you make a mistake.
The basics. At the Python interactive prompt, write a function that prints its single argument to the screen and call it interactively, passing a variety of object types: string, integer, list, dictionary. Then, try calling it without passing any argument. What happens? What happens when you pass two arguments?
Arguments. Write a function called
adder
in a Python module file.
The function should accept two arguments and return the sum (or
concatenation) of the two. Then, add code at the bottom of the
file to call the adder
function
with a variety of object types (two strings, two lists, two
floating points), and run this file as a script from the system
command line. Do you have to print the call statement results to
see results on your screen?
varargs. Generalize the adder
function you wrote in the last
exercise to compute the sum of an arbitrary number of arguments,
and change the calls to pass more or fewer than two arguments.
What type is the return value sum? (Hints: a slice such as
S[:0]
returns an empty sequence
of the same type as S
, and the
type
built-in function can test
types; but see the manually coded min
examples in Chapter 18 for a simpler approach.) What happens if
you pass in arguments of different types? What about passing in
dictionaries?
Keywords. Change the adder
function from exercise 2 to accept
and sum/concatenate three arguments: def
adder(good, bad, ugly)
. Now, provide default values for
each argument, and experiment with calling the function
interactively. Try passing one, two, three, and four arguments.
Then, try passing keyword arguments. Does the call adder(ugly=1, good=2)
work? Why?
Finally, generalize the new adder
to accept and sum/concatenate an
arbitrary number of keyword arguments. This is similar to what you
did in exercise 3, but you’ll need to iterate over a dictionary,
not a tuple. (Hint: the dict.keys
method returns a list you can
step through with a for
or
while
, but be sure to wrap it
in a list
call to index it in
3.0!)
Write a function called copyDict(dict)
that copies its
dictionary argument. It should return a new dictionary containing
all the items in its argument. Use the dictionary keys
method to iterate (or, in Python
2.2, step over a dictionary’s keys without calling keys
). Copying sequences is easy
(X[:]
makes a top-level copy);
does this work for dictionaries, too?
Write a function called addDict(dict1, dict2)
that computes the
union of two dictionaries. It should return a new dictionary
containing all the items in both its arguments (which are assumed
to be dictionaries). If the same key appears in both arguments,
feel free to pick a value from either. Test your function by
writing it in a file and running the file as a script. What
happens if you pass lists instead of dictionaries? How could you
generalize your function to handle this case, too? (Hint: see the
type
built-in function used
earlier.) Does the order of the arguments passed in matter?
More argument-matching examples. First, define the following six functions (either interactively or in a module file that can be imported):
def f1(a, b): print(a, b) # Normal args def f2(a, *b): print(a, b) # Positional varargs def f3(a, **b): print(a, b) # Keyword varargs def f4(a, *b, **c): print(a, b, c) # Mixed modes def f5(a, b=2, c=3): print(a, b, c) # Defaults def f6(a, b=2, *c): print(a, b, c) # Defaults and positional varargs
Now, test the following calls interactively, and try to explain each result; in some cases, you’ll probably need to fall back on the matching algorithm shown in Chapter 18. Do you think mixing matching modes is a good idea in general? Can you think of cases where it would be useful?
>>>f1(1, 2)
>>>f1(b=2, a=1)
>>>f2(1, 2, 3)
>>>f3(1, x=2, y=3)
>>>f4(1, 2, 3, x=2, y=3
) >>>f5(1)
>>>f5(1, 4)
>>>f6(1)
>>>f6(1, 3, 4)
Primes revisited. Recall the following code snippet from Chapter 13, which simplistically determines whether a positive integer is prime:
x = y // 2 # For some y > 1 while x > 1: if y % x == 0: # Remainder print(y, 'has factor', x) break # Skip else x -= 1 else: # Normal exit print(y, 'is prime')
Package this code as a reusable function in a module file
(y
should be a passed-in
argument), and add some calls to the function at the bottom of
your file. While you’re at it, experiment with replacing the first
line’s //
operator with
/
to see how true division
changes the /
operator in
Python 3.0 and breaks this code (refer back to Chapter 5 if you need a refresher). What can you
do about negatives, and the values 0
and 1
? How about speeding this up? Your
outputs should look something like this:
13 is prime 13.0 is prime 15 has factor 5 15.0 has factor 5.0
List comprehensions. Write code to
build a new list containing the square roots of all the numbers in
this list: [2, 4, 9, 16, 25]
.
Code this as a for
loop first,
then as a map
call, and finally
as a list comprehension. Use the sqrt
function in the built-in math
module to do the calculation (i.e.,
import math
and say math.sqrt(x)
). Of the three, which
approach do you like best?
Timing tools. In Chapter 5, we saw three ways to compute square
roots: math.sqrt(X)
, X ** .5
, and pow(X, .5)
. If your programs run a lot
these, their relative performance might become important. To see
which is quickest, repurpose the timerseqs.py script we wrote in this
chapter to time each of these three tools. Use the mytimer.py timer module with the
best
function (you can use
either the 3.0-ony keyword-only variant, or the 2.6/3.0 version).
You might also want to repackage the testing code in this script
for better reusability—by passing a test functions tuple to a
general tester function, for example (for this exercise a copy-and-modify approach is fine).
Which of the three square root tools seems to run fastest on your
machine and Python in general? Finally, how might you go about
interactively timing the speed of dictionary comprehensions versus
for
loops?
[43] These performance generalizations can depend on call
patterns, as well as changes and optimizations in Python itself.
Recent Python releases have sped up the simple for
loop statement, for example.
Usually, though, list comprehensions are still substantially
faster than for
loops and
even faster than map
(though
map
can still win for
built-in functions). To time these alternatives yourself, see
the standard library’s time
module’s time.clock
and
time.time
calls, the newer
timeit
module added in
Release 2.4, or this chapter’s upcoming section Timing Iteration Alternatives.
[44] Interestingly, generator functions are also something of
a “poor man’s” multithreading device—they
interleave a function’s work with that of its caller, by
dividing its operation into steps run between yield
s. Generators are not threads,
though: the program is explicitly directed to and from the
function within a single thread of control. In one sense,
threading is more general (producers can run truly
independently and post results to a queue), but generators may
be simpler to code. See the second footnote in Chapter 17 for a brief introduction to Python
multithreading tools. Note that because control is routed
explicitly at yield
and
next
calls, generators are
also not backtracking, but are more
strongly related to coroutines—formal
concepts that are both beyond this chapter’s scope.
[45] Also note how we must pass functions in to the timer manually here. In Chapters 38 and 39 we’ll see decorator-based timer alternatives with which timed functions are called normally.
[46] For more fun, apply a simple user-defined function like
def f(I): return(I)
in all
five iteration techniques timed. The results are similar to
using a built-in function like abs
: among the five iteration
techniques, map
is fastest
today if all five call a function, built-in or not, but slowest
when the others do not. That is, map
appears to be slower simply
because it requires function calls, and function calls are
relatively slow in general. Since map
can’t avoid calling functions, it
can lose by association.