Build with Python

Values on Demand

8 of 12 · 100 minLabState Over TimeLookup and Pointers

Values on Demand

Snake kept its whole world in memory and changed it on a clock. Plenty of data never fits that picture: a log file larger than your laptop's memory, a sensor that reports forever, the results of a search you might abandon after the first page. This lesson is about producing values one at a time, only when asked — and about the memory and the surprises that come with it.

The worked example is a log reader. The lab applies the same ideas to streams, a live chart, a memory measurement and functions that remember.

The protocol behind every for loop

A for loop looks like it walks through a list. What it actually does is ask an iterator for one value at a time:

lines = ["boot ok", "disk warning", "net error", "boot ok"]
cursor = iter(lines)
assert next(cursor) == "boot ok"
assert next(cursor) == "disk warning"
rest = list(cursor)                # takes whatever is left
assert rest == ["net error", "boot ok"]
assert list(cursor) == []          # an iterator is used up after one pass

iter(values) makes the cursor, next hands out one value and remembers the place, and when nothing is left, next raises StopIteration — which is exactly the signal a for loop listens for to stop.

That last line surprises people in interviews: a list can be looped over as often as you like, but an iterator is a single pass. If a function receives an iterator and looks at it twice, the second look finds nothing.

Generators: functions that pause

A function containing yield is a generator function. Calling it runs none of its body; it returns an iterator. Each next runs the body until the next yield, hands that value out, and pauses right there, keeping every local variable.

def matching(lines, word):
    for number, line in enumerate(lines, start=1):
        if word in line:
            yield number, line

found = matching(["boot ok", "disk warning", "net error"], "error")
assert next(found) == (3, "net error")

Nothing is read until someone asks. That property lets generators work on data that has no end:

from itertools import count, islice

def heartbeat():
    for tick in count():           # 0, 1, 2, ... forever
        yield "error" if tick % 5 == 4 else "ok"

first_errors = list(islice((t for t, s in enumerate(heartbeat()) if s == "error"), 3))
assert first_errors == [4, 9, 14]

islice takes the first three values and stops asking. An endless generator costs nothing until it is asked, and nothing more after the caller stops.

Pipelines

Generators combine like pipes: each stage pulls from the one before, one value at a time.

def strip_all(lines):
    for line in lines:
        yield line.strip()

def non_empty(lines):
    for line in lines:
        if line:
            yield line

raw = ["  boot ok\n", "\n", " net error \n"]
assert list(non_empty(strip_all(raw))) == ["boot ok", "net error"]

No stage builds a list. At any moment each stage holds one line, however long the input is. The invariant of a generator pipeline is worth stating plainly:

Each stage has read exactly the values it needed to produce what has been asked for so far, and holds only the values it is working on.

Keeping a little history

Sometimes a stream needs a short memory: "show the three lines before each error". A collections.deque with maxlen keeps the most recent items and drops the oldest automatically:

from collections import deque

def with_context(lines, word, before=2):
    recent = deque(maxlen=before)
    for line in lines:
        if word in line:
            yield list(recent), line
        recent.append(line)

log = ["a", "b", "c", "net error", "d"]
assert list(with_context(log, "error")) == [(["b", "c"], "net error")]

Memory stays at before lines no matter how long the log is. A deque also adds and removes at both ends in O(1), which is why Snake's body could live in one: appendleft a head, pop a tail, and nothing shifts.

Measuring instead of guessing

"Generators use less memory" is a claim you can check. tracemalloc records the peak memory Python allocated while some code ran:

import tracemalloc

def peak(make_values):
    tracemalloc.start()
    total = sum(make_values())
    top = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return total, top

as_list = peak(lambda: [n * n for n in range(50_000)])
as_stream = peak(lambda: (n * n for n in range(50_000)))
assert as_list[0] == as_stream[0]            # same answer
assert as_stream[1] < as_list[1] / 10        # a small fraction of the memory

The exact numbers depend on the Python version and platform — the lab measures them in your browser, so yours will differ from anyone else's — but the shape does not: the list holds every square at once, O(n) memory; the generator expression holds one, O(1).

Functions that remember

A generator remembers where it paused. An ordinary function can remember values too, by closing over a variable from the call that created it:

def make_tally():
    total = 0
    def add(amount):
        nonlocal total          # assign to the enclosing total, not a new local
        total += amount
        return total
    return add

tally = make_tally()
tally(5)
assert tally(3) == 8
other = make_tally()
assert other(1) == 1            # each call to make_tally has its own total

Without nonlocal, total += amount would try to create a new local total and fail. Remembering answers this way is the idea behind memoization, which Module 12 builds on; the standard library's functools.cache does it for any function in one line.

Where it goes wrong

  • Reading an iterator twice. The second pass is empty. If you need two passes, make a list — deliberately.
  • Hiding a list inside a "stream". sorted(stream) or list(stream) reads everything; so does keeping every value "just in case". The memory comes back.
  • Using None as the end marker when None is a real value. next(stream, None) returns None at the end, so it cannot tell a finished stream from one that yielded None. When None can be data, pass a private marker: DONE = object(), then next(stream, DONE) is DONE.
  • A mutable default for remembered state. def remember(f, saved={}) shares one dictionary among every call. Create it inside the function.

In the lab

The lab hands out batches from a single stream while the picture colors each value as it leaves, writes a running-total generator that never reads ahead, streams sensor readings into a ten-value deque on a clock, measures a list against a generator with tracemalloc, and builds a counter and a remember wrapper from closures. The mastery challenge gives you an endless stream and names no technique: you choose the plan, state what stays true, predict its cost, and explain why the obvious alternative fails.

Preparing the guided lab…