Rules of the duel

Budgets without clocks

Why it matters You will meet these measuring tools in every problem. Five minutes with them now saves confusion later.

The lab kit lives in creative.budget. It has four ways to count cost.

Reads: Tape

A Tape is a read-only list that counts every item you read. Looping, indexing, in and copying all count. len() is free.

from creative.budget import Tape
t = Tape([5, 3, 8, 1])
print(8 in t, t.reads)     # True 3  (it stopped at the 8)
print(t[0], t.reads)       # 5 4

Steps: steps()

steps(fn, *args) runs fn and counts the lines of your own code that ran. Work done inside built-ins (like sum() or x in some_list) is not counted, which is why problems about speed hand you a Tape instead.

from creative.budget import steps
result, n = steps(my_function, data)

Memory: kept()

kept(obj) counts the items a structure holds, all the way down. A list of 3 numbers is 4 (the list, plus 3).

Code size: code_size()

code_size(source) counts syntax nodes. Comments and blank lines are free, so it rewards less logic, not shorter names.

Recap Tape for reads, steps() for your own lines, kept() for memory, code_size() for simplicity. The same answer gets the same count on every machine.

Your turn

Write two helpers you will reuse: reads_used(fn, items) wraps items in a Tape, calls fn(tape) and returns how many reads it made; steps_used(fn, *args) returns just the step count from steps(). Then set cheaper to "first" or "last": which of the two functions in the starter reads fewer items on the list range(1000)?

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus