Lessons · Python · loop inside a loop
A loop inside a loop multiplies
If the outer loop runs n times and the inner runs n times, the body runs n times n times. 1,000 becomes a million.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
This is how a feature that works on the demo data times out on real data. Recognising the shape lets you fix it before it ships.
How to think about it
When you write a loop inside a loop over the same data, ask: is the inner loop searching? If so, replace it with a dict or set lookup. If both loops are needed (a grid), accept it and keep the body tiny.
Worked example
for a in names:n names.
for b in names:n again: n times n comparisons.
if a == b: ...Searching for a match is what dicts are for.
seen = set(names) # insteadOne pass to build, one step per lookup: n, not n times n.
Your turn
Every cell of a 3x3 grid needs visiting. Which loops?
for row in range(3):
for col in range():
visit(row, col)Solve one with the tests running
The trap
Calling something inside the inner loop that itself loops (like list.index or 'in list'). Three loops hiding as two.