Advanced Generators
This lesson includes the following topics:
Generators were added to Python to allow computation with sequences without having to actually build a data structure to hold the values of the sequence. This can yield large savings in memory. Earlier you saw that generators obey the same iteration protocol that other iterators do, and that you can write generator functions and generator expressions to avoid the creation of such sequences.
You can also use generators as "filters," to remove some of the values from an input sequence. The general pattern of such a filter is:
def filter(s):
for v in s:
if some_condition_on(v):
yield v
This technique can easily be used to "stack" filters, by providing one filter as the argument to another. To demonstrate this technique, suppose that you wanted to examine a file, ignoring blank lines and lines beginning with a "#." While there are several ways to do this, it would be fairly simple to use generators (remembering that text files are generators too, in Python). Create filterfile.py as follows.
"""
Filter file contents using a sequence of generators.
"""
def nocomment(f):
"Generate the non-comment lines of a file."
for line in f:
if not line.startswith("#"):
yield line
def nospaces(f):
"Generate the lines of a file without leading or trailing spaces."
for line in f:
yield line.strip()
def noblanks(f):
"Generate the non-blank lines of a file."
for line in f:
if line:
yield line
if __name__ == "__main__":
for line in nocomment(noblanks(nospaces(open("py08-01.txt")))):
print(line)
Now, create the text file as shown:
# Excluded because a comment
# This is also a comment, and the next two lines are blank
This line should be the first of four lines in the output
# The next line contains spaces and tabs, and should not appear
And this should be the second
# This should not appear (leading spaces but a comment)
# Neither should this (leading tabs but a comment)
This should be the third line of output
And this should be the last.
Save it as py08-01.txt.
Run filterfile.py and you should see:
This line should be the first of four lines in the output And this should be the second This should be the third line of output And this should be the last.
The essence of this program is the for loop guarded by the if __name__ == "__main__": condition. open("py08-01.txt") is used to generate the raw text lines from the file, then the nospaces() generator strips the spaces from the lines, after which the noblanks() generator removes blank lines, and then finally the nocomment() generator yields only the lines that aren't comments.
Each individual filter performs a very simple task, but used in combination they can be much more powerful. (This is the philosophy behind the UNIX operating system, by the way: provide simple primitive commands but allow them to be combined together to create more powerful commands).
| Modern Python | Python 3.3 introduced yield from (PEP 380) for delegating to a
sub-generator. The three filter functions above hand-roll their delegation loops, which is
perfectly clear here. An equivalent nospaces using yield from
would look like:
def nospaces(f):
yield from (line.strip() for line in f)
The yield from expr form is most valuable when you are delegating to another
generator wholesale, rather than transforming individual values — use whichever reads most
clearly for your case.
|
You can never create all the values of an infinite sequence. With a generator, you can generate as many members of a sequence of indefinite length as you like, which is useful when you do not know in advance how many values will be required. This can occur, for example, when you need to generate a value for each member of a sequence of unknown length. Such requirements can arise in many contexts—when the user is entering a series of values, when you are processing the output of another generator, and so on. (The one major advantage of sequences over generators is that you can always find out how many elements they contain.)
This is the result of generators' "lazy evaluation"—the values are not all produced first and then consumed by the client code. Instead, when another value for the sequence is required, the generator produces it, and is then suspended (retaining the values of all local variables from the function call) until it is resumed to produce the next value in the sequence. So as long as the client code eventually stops asking for values, there really is no problem with an infinite generator. Just don't expect it to ever produce all its values—that would take an infinite amount of time!
Once generators and generator expressions were introduced into the language, iteration became a focus for development. This led to the introduction of the itertools module, first released with Python 2.3. itertools contains many useful functions to operate on generators and sequences. The algorithms are implemented in C, and so they run a lot faster than pure-Python equivalents. When you look at the Python documentation for the module, however, you will find that many of the functions are documented to include broadly-equivalent Python to explain them more fully.
It's important to remember that generators are a "one-shot deal": once data is consumed, it isn't possible to go back and retrieve that data again. Therefore, most of the operations you perform on generated sequences are not repeatable, unlike operations on tuples, lists, and strings.
tee takes two arguments: the first is a generator and the second is a count (2, if not specified). The result is the given number of generators that can be used independently of each other.
| Note | Because the resulting generators can be used independently, the implementation must store any values that have been consumed from one of the result generators but not from all the others. Consequently, if your code consumes most of the values from one of the result generators before the rest, you may find it more efficient to simply construct a list and use multiple iterations over that. |
"""
Demonstrate simple use of itertools.tee.
"""
import itertools
actions = "save", "delete"
data = ["file1.py", "file2.py", "save", "file3.py", "file4.py",
"delete", "file5.py", "save", "file6.py",
"file7.py", "file8.py", "file9.py", "save"]
saved = []
deleted = []
def datagen(d):
"A 'toy' data generator using static data"
for item in d:
yield item
commands, files = itertools.tee(datagen(data))
for action in commands:
if action in actions:
for file in files:
if file == action:
break
if action == "save":
saved.append(file)
elif action == "delete":
deleted.append(file)
print("Saved:", ", ".join(saved))
print("Deleted:", ", ".join(deleted))
The program tees a single data source containing filenames and commands into two separate generators. It then iterates over the first generator until it finds a command. Once the command is found, it iterates over the second generator, performing the requested action on the files it retrieves until it "catches up" with the first generator (detected because the command is seen). This avoids the need to save the filenames in an ancillary list until the program knows what to do with them.
Run it and you should see this:
Saved: file1.py, file2.py, file5.py, file6.py, file7.py, file8.py, file9.py Deleted: file3.py, file4.py
The chain() function can be called with any number of sequences as arguments. It yields all the elements of the first sequence, followed by all the elements of the second sequence, and so on until the last sequence argument is exhausted.
It isn't possible to subscript a generator like it is a sequence such as a list or a tuple, because subscripting requires all the elements of a sequence to be in memory at the same time. Sometimes, however, you need to select elements from a generated sequence in much the same way you do for an in-memory sequence. The itertools module allows you to do this with its islice function.
It takes up to four arguments: (seq, [start,] stop [, step]). If only two arguments are provided, the second argument is the length of the slice to be generated, starting at the beginning of the sequence. When three arguments are provided, the second argument M is the index of the starting element and the third argument N is the index of the element after the last one in the result. This closely parallels the seq[M:N] of standard sequence slicing. Finally, when all four arguments are present, the last argument is a "stride", which determines the gap between selected elements. As mentioned above, slicing operations on generated sequences will not be repeatable because the operation consumes data from the sequence, and each value can be produced only once.
The following interactive example demonstrates the use of chaining and slicing on generated sequences.
>>> import itertools >>> s1 = (1, 3, 5, 7, 11) >>> s2 = ['one', 'two', 'three', 'four'] >>> def sqq(n): ... for i in range(n): ... yield i*i ... >>> s3 = sqq(10) >>> >>> input = itertools.chain(s1, s2, s3) >>> list(itertools.islice(input, 2, 7, 2)) [5, 11, 'two'] >>> list(itertools.islice(input, 3)) ['three', 'four', 0] >>>
It is important here to observe that the second operation on the chained sequences starts with the first element not consumed by the previous operation.
These three functions provide convenient infinite sequences for use in other contexts. count(start=0, step=1) generates a sequence starting with the value of its start argument and incremented by the step amount (with a default of 1) for each call. cycle(i) takes an iterable argument i and yields each one until the sequence is exhausted, whereupon it returns to the start of the sequence and starts again. repeat(x) simply yields its argument x every time a value is requested.
Sometimes you only want to deal with the end of a sequence, and sometimes you only want to deal with the beginning. These functions allow you to do so by providing a predicate function that is used to determine when to start or stop yielding elements. The function is applied to successive values in the sequence. In the case of dropwhile(), elements are discarded until one is found for which the function returns False, after which the remaining values are yielded without testing them. takewhile(), on the other hand, returns elements of the sequence until it encounters one for which the function returns False, at which point it immediately raises a StopIteration exception.
You can learn a little more about these functions in an interactive console session.
>>> import itertools >>> def lt5(n): ... return n<5 ... >>> s1 = [1, 3, 2, 4, 6, 4, 2, 3, 1] >>> list(itertools.dropwhile(lt5, s1)) [6, 4, 2, 3, 1] >>> list(itertools.takewhile(lt5, s1)) [1, 3, 2, 4] >>>
For any function f and sequence s:
list(takewhile(f, s)) + list(dropwhile(f, s)) == list(s)
The two functions are therefore complementary in nature.
This has "scratched the surface" of the itertools module, but there is plenty more to reward your reading of its documentation should you feel so inclined.
In the same way that list comprehensions offer a more succinct way to create lists, generator expressions help you to use generators without having to write a generator function.
Since list and tuple creation is relatively fast in Python, you will probably find that you have to be working with fairly large data sets in order to see compelling advantages for generators over lists. Try it with some sample random data to get a feel for the relative speed of lists. In this example, we'll sum a bunch of numbers from a list of random numbers between 0 and 1 in two ways: the first sums the values using a generator expression, the second creates a list and sums that.
| Note | The lists get so large it is entirely possible that there is not enough memory to create the larger ones. In that case, you may see MemoryError exceptions such as the one demonstrated below (this particular run was made on a testing machine with limits on the amount of memory one process can use, so you may not see the exception because you are using better-resourced production machines in your lab sessions). Once an interpreter process has suffered a memory error, it may not be able to reclaim all that memory, so it is best to start a fresh session if that happens. |
>>> from random import random
>>> from timeit import timeit
>>> for i in (10000, 100000, 1000000, 10000000, 20000000, 50000000):
... lst = [random() for j in range(i)]
... print("Length", i)
... print(timeit("sum(x+1 for x in lst)", "from __main__ import lst", number=1))
... print(timeit("sum([x+1 for x in lst])", "from __main__ import lst", number=1))
...
Length 10000
0.00158104889511
0.00227248575142
Length 100000
0.0177263913609
0.0243493450655
Length 1000000
0.193913529809
0.410940463442
Length 10000000
1.99618459393
4.07905032771
Length 20000000
3.79710857443
7.48326630071
Traceback (most recent call last):
File "<console>", line 2, in <module>
File "<console>", line 2, in <listcomp>
MemoryError
The code uses timeit's number argument to ensure that only one timed operation of the sample code is run. This means that the timings are not necessarily repeatable, but are at least indicative of the relative times of the different operations. It seems that, the longer the sequence, the more improvement you can expect to see from using a generator expression. For comparison with the timings on Windows, here is the output from a MacOS machine (with more memory) running the same code in a new Python console session.
Length 10000 0.00169491767883 0.00142598152161 Length 100000 0.017655134201 0.0198609828949 Length 1000000 0.18835401535 0.206699848175 Length 10000000 1.77904486656 2.16294407845 Length 20000000 3.62438511848 4.16168618202 Length 50000000 9.03414511681 76.5883550644 >>>
You can see that there is sufficient memory for this computer to create the larger lists. While the performance of the list-based technique and the generator expressions are the same, the difference does not seem to be quite as marked. These tests were run on a different operating system, which may have something to do with it. Note that with fifty million elements in the last test iteration, the creation of the list starts to add large overhead, and the generator expression is markedly faster.
You have already come across list comprehensions such as [x*x for x in sequence]. You can, if you want, think of list comprehensions as generator expressions surrounded by list brackets. The brackets tell the interpreter that it is required to create a list, so it runs the generator to exhaustion and adds each element to a newly-created list. There is no essential difference between the expression above and list(x*x for x in sequence), but the latter does seem to be about 25% slower on implementations current at the time of writing, whether the sequence is a list or a generator function.
| Modern Python | Generator expressions remain the idiomatic choice for lazy evaluation, and
the advice here holds true in Python 3.14. The performance gap between generator expressions
and list comprehensions depends heavily on what you do with the result: if you need the
entire sequence in memory anyway (e.g. for sorting or random access), build the list
directly. If you are passing the result to a single-pass consumer such as sum(),
max(), or a for loop, a generator expression saves both memory
and (for large sequences) time. Note also that the timeit setup string
("from __main__ import lst") used here is the older API; in interactive
sessions the globals parameter is more convenient:
timeit("sum(x+1 for x in lst)", globals=globals(), number=1). |
Generators, while a relatively late addition to the Python language, are rapidly becoming an essential part of it. When you are dealing with large data sets, a good command of generators can make all the difference between a slow program and a fast one. It is therefore important to be aware of their possibilities. This is not too difficult, once you realise that they are often simply a faster and more efficient way to handle data.