By the end of this lesson you will be able to
- say what this course means by a step
- measure a function with
count_steps()and read the step count under every program - use
step_table()to see how the number of steps grows as the input grows - explain why a built-in function such as
max()or the wordinhides work - compare two solutions to the same problem by their steps, not by guessing
“It works on my laptop”
On her second day at Brightwater Books, Lucy Carter is asked to look at a small function that checks whether any customer has been entered twice in a list of customer numbers. It works. Arthur Blake, the senior developer who is showing her round, agrees that it works. “On the twenty test customers, it is instant,” he says. “Last night it ran on all forty thousand real customers and took most of the night. So the question is not does it work. The question is how much work does it do, and how that changes when the list gets bigger.”
Timing a program with a stopwatch is a poor way to answer that question. The same code runs faster on a new computer than an old one, faster when nothing else is running, and differently from one day to the next. Programmers need a measure that belongs to the method, not to the machine. That measure is the number of steps.
What counts as a step
In this course, one step is one line of your own code being carried out. If a line is inside a loop that goes round ten times, it counts ten times. Every code box shows the total under its output. Press Run on this one and look at the last line of the output.
Four lines, each carried out once: 4 steps. Now a loop. The for line itself is counted every time Python goes back to it to fetch the next value, plus one last time when it finds there is nothing left.
With range(5) the program takes 13 steps: 1 for total = 0, 6 for the for line (five values and one final check), 5 for the line inside the loop, and 1 for print. Change it to range(50) and it takes 103 steps. The exact number matters less than the pattern: about two steps for every item, plus a few extra.
Counting lines is not a perfect measure of time: some lines do more work than others. But it has two great strengths. It gives the same answer on every computer, every time. And, as you will see all through this course, it grows in exactly the same pattern as the real running time when the input gets bigger. The pattern is what we care about.
Measuring one function: count_steps
The step count under the output is for the whole program. To measure a single function, use count_steps(function, argument). It calls the function with that argument and gives back how many steps the call took. It is built into every box in this course (it is not part of ordinary Python).
Adding up the numbers from 1 to 10 takes 23 steps; to 100, 203 steps; to 1,000, 2,003 steps. Every time n is ten times bigger, the work is about ten times bigger. The number of steps grows in step with n.
A table of steps: step_table
Measuring by hand for one size after another is tedious, so there is a second helper. step_table(function, make_input, sizes) measures the function for each size in the list. make_input is a small function that builds the input for a given size. Here it is written with lambda, a short way to write a one-line function: lambda n: list(range(n)) means “given n, make the list 0, 1, 2, … up to n − 1”.
This is Lucy's duplicate checker. It compares every customer number with every number after it.
The table and the bars tell the story at a glance:
| Customers (n) | Steps | Compared with the row above |
|---|---|---|
| 10 | 112 | |
| 20 | 422 | about 4 times as many |
| 40 | 1,642 | about 4 times as many |
| 80 | 6,482 | about 4 times as many |
Each time the list doubles, the work goes up about four times. That is because the function compares pairs of customers, and the number of pairs grows much faster than the number of customers. Carry the pattern on. Doubling 80 customers nine times gives about 40,000, and every doubling multiplies the steps by about 4. Nine lots of “times 4” turn 6,482 steps into roughly 1,700,000,000: well over a billion and a half steps. That is why it ran all night.
Arthur asks Lucy: “If total(1000) takes 2,003 steps, roughly how many will total(4000) take?”
Lucy reasons: the steps grow in step with n, about 2 per number. Four times the input means about four times the steps: roughly 8,000. (The exact answer is 2 × 4,000 + 3 = 8,003.) For has_duplicate, the same question has a different answer: four times the customers means about sixteen times the steps, because doubling twice multiplies the work by 4 and then by 4 again.
Built-in functions hide steps
Here is something important to be honest about. The step counter only counts lines of your code. When you call one of Python's built-in functions, such as max(), sum(), sorted(), or use the word in to look for something in a list, Python does that work behind the scenes, and it counts as just one step. It is not free: max() still has to look at every item. It is simply hidden.
The loop version takes 3,002 steps (on this rising list every number beats the best so far, so the for, if and best = x lines all run for every number) and the built-in version takes 1, yet both look at all 1,000 numbers. The built-in is faster in real life (it is written in a faster language inside Python), but it does not do less work. Keep this in mind whenever a solution looks suspiciously cheap: x in some_list inside a loop is a loop inside a loop, even though you can only see one of them.
Two ways to solve one problem
Counting steps really pays off when you compare methods. There is an old trick for adding up 1 to n without a loop: pair the first number with the last (1 + n), the second with the second last (2 + n − 1), and so on. Every pair adds up to n + 1, and there are n ÷ 2 pairs, so the total is n × (n + 1) ÷ 2. step_table can measure two functions side by side if you give it a list of them.
Both give 500,500 for n = 1,000. The loop takes 2,003 steps; the formula takes 1 step for every size. A method whose work does not grow at all as the input grows is the best kind there is. In Lesson 1.3 you will learn short names for these patterns: work that stays the same, work that grows in step with n, and work that grows like n × n.
Exercises
Each exercise has a code box. Press Check my answer when you are ready: your function is tested on many inputs, not only the examples shown. Some exercises also check the number of steps your function takes.
Exercise 1 · Add up a list
Write a function add_all(items) that uses a for loop to add up the numbers in the list items and returns the total. An empty list should give 0. Do not use sum(): the point is to write the loop yourself.
Exercise 2 · Measure the duplicate checker
The box contains Lucy's has_duplicate function. Do not change it. Below it, use count_steps to store the steps it takes on a list of 50 different numbers in a variable called steps_50, and on a list of 100 different numbers in steps_100. Use list(range(50)) and list(range(100)) to make the lists. Print both.
Exercise 3 · The one-step total
Write total_formula(n) that returns 1 + 2 + … + n without a loop, using the pairing trick from the lesson: n × (n + 1) ÷ 2. Use // for the division so that the answer is a whole number. For n = 0 it should give 0. The checker will call it with n = 1,000,000 and allows only a handful of steps.
Exercise 4 · Predict, then check
The function count_evens is in the box. count_steps(count_evens, list(range(10))) gives 28. Without running anything, predict how many steps it will take on list(range(100)) and store your prediction as a number in guess. Then add a line that stores the real count in actual, and run it. Your guess must be within 10 of the real answer.
Exercise 5 · The largest order, by hand
Grace Holloway, the warehouse manager, wants the size of the largest order in a list. Write largest(orders) that returns the biggest number in a non-empty list, using a loop. Do not use max() or sorted(). Then run step_table on your function (the line is already in the box) and look at how its steps grow.
Quick check
Choose an answer to see whether you are right and why.
1. In this course, what is one step?
A step is one line of your code being carried out. A line inside a loop counts once for every time round the loop. Seconds depend on the computer; steps do not.
2. A function takes 500 steps on a list of 100 items and 1,000 steps on 200 items. About how many on 800 items?
Doubling the items doubled the steps, so the work grows in step with the length: 5 steps per item. 800 items × 5 = about 4,000 steps.
3. Doubling the input makes a function take about four times as many steps. What does that suggest?
Twice the items means about four times as many pairs. That pattern usually comes from a loop inside a loop, like Lucy's duplicate checker.
4. count_steps says a function using max(items) takes 1 step on a list of 10,000 numbers. What is true?
The counter counts only lines of your own code. Built-in functions do their work behind the scenes: it is hidden, not free.
Summary
- A step is one line of your own code being carried out. Every box shows the total steps under its output.
count_steps(f, x)measures one call off;step_table(f, make_input, sizes)measures it for several sizes and draws bars. Give it a list of functions to compare them.- What matters is how the steps grow as the input grows: not at all (a formula), in step with the input (one loop), or about four times for every doubling (a loop inside a loop).
- Built-in functions such as
max(),sum(),sorted()andinon a list count as one step, but still do the work. Hidden is not free. - To compare two solutions, measure them on the same inputs of several sizes.
Found a mistake on this page, or something unclear? Report a problem and mention “Algorithms Lesson 1.2”.