Iterators and Generators

What this session is for

• Write iteration logic with yield, far more concisely than with classes
• Keep iterables and iterators apart, and avoid the “works only once” trap
• Replace hand-written boilerplate with itertools and collections
• Measure for yourself what a generator saves

Problems

13-1 Basic generators

Implement three:

def evens(n: int):
    """Yield the first n positive even numbers: 2, 4, 6, ..."""

def repeat_each(items: list[str], k: int):
    """Yield each element k times.
    repeat_each(['a','b'], 2) → a, a, b, b"""

def running_max(nums: list[int]):
    """Yield the maximum seen so far.
    running_max([3,1,4,1,5]) → 3, 3, 4, 4, 5"""

All three must use yield. Building a list and returning it is not acceptable.

13-2 Chaining generators

Implement:

def read_records(lines: list[str]):
    """Yield non-blank lines, stripped."""

def parse_records(lines):
    """Take a generator; yield (name, score) tuples. Skip malformed lines."""

def passing_only(records):
    """Take a generator; yield only those scoring 60 or more."""

Then chain them:

data = ["Alex 87", "", "Blake 45", "malformed", "  Chen 92  "]
result = list(passing_only(parse_records(read_records(data))))
# expected: [("Alex", 87), ("Chen", 92)]

Answer in your notes: if data were a 10 GB file, how much memory would this chain use, and why?

13-3 Debugging: why the answers are wrong

All four snippets are broken, and none of them raises — they quietly give wrong answers. Find each cause and fix it.

# A
def stats(nums):
    gen = (x * 2 for x in nums)
    return sum(gen), max(gen), len(list(gen))

# B
import itertools
data = ["apple", "carrot", "banana", "celery"]
key = lambda w: "fruit" if w in ("apple", "banana") else "veg"
groups = {k: list(g) for k, g in itertools.groupby(data, key=key)}

# C
def first_big(nums, threshold):
    big = [x for x in nums if x > threshold]
    return big[0]

# D
counts = {}
for word in ["a", "b", "a"]:
    counts[word] += 1

13-4 An infinite generator

Implement primes(), an infinite generator of prime numbers.

import itertools
print(list(itertools.islice(primes(), 20)))
# expected: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Requirement: no upper bound may be fixed in advance. Your primes() must be able to keep going.

Answer in your notes: how would you write this without a generator, and what problem would you hit?

13-5 Simplify with the standard library

Each snippet below can be replaced by one tool from itertools or collections. Rewrite them and say which you used.

# A: word frequency
counts = {}
for w in words:
    if w in counts:
        counts[w] += 1
    else:
        counts[w] = 1

# B: group by first letter
groups = {}
for w in words:
    if w[0] not in groups:
        groups[w[0]] = []
    groups[w[0]].append(w)

# C: running totals
totals = []
s = 0
for x in nums:
    s += x
    totals.append(s)

# D: every pairing of two lists
pairs = []
for a in list1:
    for b in list2:
        pairs.append((a, b))

# E: keep only the most recent 100 records
recent.append(item)
if len(recent) > 100:
    recent.pop(0)

13-6 Measuring memory

Write code comparing these two at n = 10^5, 10^6, 10^7, measuring both memory (via sys.getsizeof) and creation time:

a = [x ** 2 for x in range(n)]
b = (x ** 2 for x in range(n))

Produce a table, and answer in your notes:

1. How does the list’s memory scale with n? And the generator’s?
2. How long does creating a generator take, and why?
3. If you only need sum(), which is better? What if you need sorted()?

13-7 Implementing the protocol by hand

Without yield, implement Fibonacci as an iterable class:

class Fibonacci:
    def __init__(self, limit: int) -> None:
        """Yields the first `limit` Fibonacci numbers."""
    def __iter__(self): ...

Requirement: it must be traversable more than once.

fib = Fibonacci(10)
print(list(fib))
print(list(fib))     # must match the first

Then rewrite it with yield and compare the line counts. Answer in your notes: can the yield version be traversed repeatedly? If not, what change would make it so?

Before you submit

• All three generators in 13-1 use yield and build no lists
• 13-2 answers the 10 GB memory question
• 13-3 diagnoses all four, and C is rewritten with a generator
• 13-4’s primes() fixes no upper bound
• 13-5 rewrites all five and names the tool used
• 13-6 has a complete table and answers all three questions
• 13-7 implements both versions and answers the re-traversal question
• AI usage declaration written