Block 1 · Exercise 5

Python Generators

Starter notebook: 05-generators-starter
Fabric path: /lakehouse/default/Files/data/solutions/05.generators/

Open the notebook 05-generators-starter in your workspace and run its first cell. It copies /lakehouse/default/Files/data/solutions/05.generators/starter/ next to the notebook, so the web log of Step 5 is there to open. Each step has a cell with a comment where your code goes.

Do one part at a time, 1a, 1b and so on, and compare with the expected output before you go on. The solution is in 05-generators-solution, under every part on the exercise site, and at the back of the exercises PDF.

Step 1Countdown class

The starter's Countdown class keeps its position in self.count and has only an __init__. Make it count down from its start value to 1.

1a

Done

Add an __iter__ method to Countdown. Then run c = Countdown(3) and print iter(c) is c.

Hint 1

The slide Iteration Protocol says what __iter__ returns when the object is its own iterator.

Hint 2

iter(c) is c asks whether __iter__ gives back the very same object.

Check your output

True

Show solutionHide solution

python

class Countdown:
    def __init__(self, start):
        self.count = start

    def __iter__(self):
        return self


c = Countdown(3)
print(iter(c) is c)

1b

Done

Add a __next__ method that returns the current value and then counts down by one. Ignore the end for now. Make a new Countdown(3) and print three calls of next() on it, on one line.

Hint 1

__next__ has to remember the value it is about to hand out, because self.count has changed by the time it returns.

Hint 2

Read the value into a local variable first, change self.count, then return the local variable.

Check your output

3 2 1

Show solutionHide solution

python

    def __next__(self):
        value = self.count
        self.count -= 1
        return value


c = Countdown(3)
print(next(c), next(c), next(c))

1c

Done

A fourth next() gives 0 now, then -1. Change __next__ so that it raises StopIteration when the count has run out. Call next() a fourth time on your Countdown(3) inside a try and print StopIteration when it is raised. Then loop over Countdown(5) with a for statement and print each value.

Hint 1

A for loop stops by catching StopIteration. So __next__ has to raise it, and it has to do so before it hands out a value.

Hint 2

Check self.count against 0 on the first line of __next__.

Check your output

StopIteration
5
4
3
2
1

Show solutionHide solution

python

    def __next__(self):
        if self.count <= 0:
            raise StopIteration
        value = self.count
        self.count -= 1
        return value


c = Countdown(3)
print(next(c), next(c), next(c))
try:
    next(c)
except StopIteration:
    print("StopIteration")

for n in Countdown(5):
    print(n)

1d

Done

Compare a list with a Countdown :

Call iter() twice on the list [1, 2, 3] and print whether the two results are the same object, with is
Do the same for one Countdown(3) instance
Turn one Countdown(3) instance into a list twice in a row and print both lists

Then write a comment that says why the list can be looped over again and again, and your Countdown cannot.

Hint 1

Where does a list keep its position while you loop over it? And where does Countdown keep its position?

Check your output

False
True
[3, 2, 1]
[]

Show solutionHide solution

python

numbers = [1, 2, 3]
print(iter(numbers) is iter(numbers))

countdown = Countdown(3)
print(iter(countdown) is iter(countdown))

print(list(countdown))
print(list(countdown))

# A list is iterable : every iter() call builds a new iterator that starts at the front.
# Countdown is its own iterator and keeps its position on the object, so one loop uses it up.

Step 2Generator functions

2a

Done

Write a generator function countdown(n) that yields n, n - 1 and so on down to 1, with no __iter__, __next__ or StopIteration. Print list(countdown(5)).

Hint 1

yield takes the place of return, and the function goes on from the same spot on the next call.

Hint 2

The state that Countdown kept in self.count is now a local variable. It has to change on every round, or the loop never ends.

Check your output

[5, 4, 3, 2, 1]

Show solutionHide solution

python

def countdown(n):
    while n > 0:
        yield n
        n -= 1


print(list(countdown(5)))

2b

Done

Write a generator function numbers() that yields the integers from 0 and never stops. Do not loop over it and do not call list() on it : both would run for ever. Take the first three values with next() and print them on one line.

Hint 1

An endless generator is a loop without an end condition. The yield inside is what lets the caller take a value and leave.

Check your output

0 1 2

Show solutionHide solution

python

def numbers():
    n = 0
    while True:
        yield n
        n += 1


gen = numbers()
print(next(gen), next(gen), next(gen))

2c

Done

Write a generator first_n(iterable, n) that yields only the first n items of any iterable, so it can put a limit on the endless one. Print list(first_n(numbers(), 10)).

Hint 1

You need to know how many items you have handed out. enumerate counts them for you as you loop.

Hint 2

return inside a generator ends it, and the caller sees StopIteration.

Check your output

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Show solutionHide solution

python

def first_n(iterable, n):
    for count, item in enumerate(iterable):
        if count >= n:
            return
        yield item


print(list(first_n(numbers(), 10)))

Step 3Fibonacci

3a

Done

Write a generator function fibonacci() that yields 0, 1, 1, 2, 3, 5 and so on, without end. Print the first fifteen numbers with your first_n from 2c.

Hint 1

Each number is the sum of the two before it, so the generator has to remember two numbers between one yield and the next.

Hint 2

Python can assign two names in one statement, a, b = b, a + b, so the old a is still there when the new b is worked out.

Check your output

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Show solutionHide solution

python

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b


print(list(first_n(fibonacci(), 15)))

3b

Done

Before you run these four lines, write a comment behind each one : has the body of fibonacci run yet, and what will it print?

python

fib = fibonacci()
print(fib)
print(next(fib))
print(next(fib))

Hint 1

Think of the slide Generator State : which call creates the object, and which call runs the body?

Check your output

<generator object fibonacci at 0x...>
0
1

Show solutionHide solution

python

fib = fibonacci()      # creates the generator object, no line of the body has run
print(fib)             # prints the object, still no line of the body
print(next(fib))       # runs the body up to the first yield : 0
print(next(fib))       # resumes after that yield, a and b intact : 1

3c

Done

Make a short generator with first_n(fibonacci(), 2). Print its two values on one line with two next() calls. Call next() a third time inside a try and print exhausted when StopIteration is raised.

Hint 1

The generator is finished when first_n reaches its return. The third next() is the call that finds out.

Check your output

0 1
exhausted

Show solutionHide solution

python

short = first_n(fibonacci(), 2)
print(next(short), next(short))
try:
    next(short)
except StopIteration:
    print("exhausted")

3d

Done

Call next() on short once more, in a try, and print still closed when it raises StopIteration.

Check your output

still closed

Show solutionHide solution

python

try:
    next(short)
except StopIteration:
    print("still closed")

Step 4Generator expressions

4a

Done

The starter defines numbers = [1, 2, 3, 4]. Write a list comprehension squares_list and a generator expression squares_gen that both square every number in numbers. Print both objects, not their contents.

Hint 1

The two differ in one pair of symbols : square brackets against parentheses.

Check your output

[1, 4, 9, 16]
<generator object <genexpr> at 0x...>

Show solutionHide solution

python

squares_list = [x * x for x in numbers]
squares_gen = (x * x for x in numbers)
print(squares_list)
print(squares_gen)

4b

Done

Loop over squares_gen and print each value. Loop over it a second time. What does the second loop print, and why?

Hint 1

Which of the two objects from 4a is an iterator, and what does the module say about iterators and a second loop?

Check your output

Show solutionHide solution

python

for value in squares_gen:
    print(value)

for value in squares_gen:
    print(value)      # nothing : the generator is used up

4c

Done

Print sys.getsizeof of [x * x for x in range(100000)] and of the same thing as a generator expression. Explain the difference in a comment.

Hint 1

One of them holds 100000 numbers. The other holds a recipe for making them.

Check your output

800984
208

Your numbers may differ a little from these.

Show solutionHide solution

python

print(sys.getsizeof([x * x for x in range(100000)]))
print(sys.getsizeof(x * x for x in range(100000)))
# The list holds all 100000 results. The generator holds only where it is, and makes each one when asked.

4d

Done

Print the sum of the squares of numbers with sum and a generator expression, without building a list. A generator expression that is the only argument of a call needs no parentheses of its own : max(len(word) for word in words).

Check your output

Show solutionHide solution

python

print(sum(x * x for x in numbers))

Step 5Pipeline

How many bytes did the web server transfer? The file access-log next to the notebook has seven lines like this one :

81.107.39.38 - - "GET /ply/ HTTP/1.1" 200 7587

The last column is the number of bytes, or a dash when it is missing. The column before it is the status. Open the file with with open("access-log") as wwwlog: in every cell of this step, and work inside that block.

5a

Done

Loop over the file and print the last column of every line. line.rsplit(None, 1)[1] gives it : it splits the line once from the right and takes the second part.

Check your output

Show solutionHide solution

python

with open("access-log") as wwwlog:
    for line in wwwlog:
        print(line.rsplit(None, 1)[1])

5b

Done

Add up the bytes with a for loop, an if that skips the dash, and a running total. Print Total and the sum.

Hint 1

Start a total at 0 before the loop. Inside the loop, add the number only when the column is not -.

Hint 2

The column is text, so it has to go through int() before you can add it.

Check your output

Total 135667

Show solutionHide solution

python

total = 0
with open("access-log") as wwwlog:
    for line in wwwlog:
        bytestr = line.rsplit(None, 1)[1]
        if bytestr != "-":
            total += int(bytestr)
print("Total", total)

5c

Done

Now the same total as a pipeline of generator expressions. Write the first stage, bytecolumn, which gives the last column of each line. Print one next() of it.

Hint 1

It is the loop of 5a written as a generator expression : the expression before for is what print showed.

Check your output

Show solutionHide solution

python

with open("access-log") as wwwlog:
    bytecolumn = (line.rsplit(None, 1)[1] for line in wwwlog)
    print(next(bytecolumn))

5d

Done

Add a second stage, byte_counts, that pulls from bytecolumn, skips the dashes and turns the rest into numbers. Print Total and sum(byte_counts), which should match 5b. Make a fresh bytecolumn first : the next() in 5c used up a value of the old one.

Hint 1

Nothing is read until sum starts pulling. If the total comes out as 0, look at where sum runs in relation to the with block.

Hint 2

A generator expression takes an if after its for, and that is where the dash is left out.

Check your output

Total 135667

Show solutionHide solution

python

with open("access-log") as wwwlog:
    bytecolumn = (line.rsplit(None, 1)[1] for line in wwwlog)
    byte_counts = (int(x) for x in bytecolumn if x != "-")
    print("Total", sum(byte_counts))

5e

Done

Add a stage that keeps only the lines with status 200, and print the total bytes of those requests.

Hint 1

The status is the second column from the right. line.rsplit(None, 2) splits twice from the right.

Hint 2

The filter has to come before the stage that takes the bytes column, because the bytes column no longer has the status in it.

Check your output

Total for status 200 135534

Show solutionHide solution

python

with open("access-log") as wwwlog:
    ok_lines = (line for line in wwwlog if line.rsplit(None, 2)[1] == "200")
    bytecolumn = (line.rsplit(None, 1)[1] for line in ok_lines)
    print("Total for status 200", sum(int(x) for x in bytecolumn))

If time permits Done

yield from. Read demo09_yield_from in the 05-generators demo notebook. Then write a generator combined(*sources) that presents several sources as one stream, first with an inner loop that relays every value, then with yield from. Test it with two of your own generators and check that both give the same output.
itertools. Every function in it is a lazy generator. Try these :
- islice(count(1), 5) takes a finite window out of an endless source. Use it to put a limit on your endless generator from Step 2, and compare it with the first_n you wrote by hand.
- zip(count(1), plates) numbers a sequence without an index variable. Try it on a list of strings.
- chain(a, b) reads several iterables as one stream. Compare it with your combined and decide which you would rather write.
- takewhile(pred, it) stops at the first item that fails the test, where filter keeps looking. Find a list where the two give different answers.
- accumulate(it) yields the running total rather than the final one.
- groupby(it, key) groups only items that are already adjacent. Group a list of records by a key without sorting first, observe that a group appears twice, then sort by the same key and try again.
Random numbers. Write a generator function that yields seven random integers.
The sieve of Eratosthenes. To find the primes below 1000, strike out the multiples of 2 except 2, then the multiples of 3 except 3, and so on ; what is left are the primes. Write it as a chain of generators, each filter pulling from the one before it.
Measure the difference. Sum the first ten million integers twice, once by building a list and once with a generator. Time both with time.perf_counter, then run each again under tracemalloc to compare peak memory. Tracing slows the program down, so do not time the traced run.
A recursive flatten with yield from. Take a nested list and yield the leaves in order : flatten([1, [2, [3, [4, 5]], 6], 7]) yields 1 to 7. Each recursive call is itself a generator, so the recursion needs delegation rather than a return.