Nested loops are where a program stops being a list of steps and starts doing real work, like comparing every row with every column, or checking every option against every rule. They are also where programs get slow, and where break quietly does less than you expect it to do. Python has one more loop construct that looks like a mistake until you see its purpose, which is a for loop with an else clause that runs only when nothing was found.
The previous lesson in this module covered "while Loops and Breaking Out Safely", and this lesson is the last one in the Python if-else and Loops module.
What happens when you put one loop inside another?
The outer loop runs once for each item, and the inner loop runs all the way through for each of those. A nested loop over two collections of ten items therefore executes a hundred iterations. That multiplication is the whole cost story, and it is why nested loops are the first thing to reconsider when a program becomes slow.
for row in range(3):
for column in range(4):
if (row + column) % 2 == 0:
print('o', end=' ')
else:
print('.', end=' ')
print()
Here is the detail that catches people out. break and continue apply to the loop that they sit inside, and to nothing else. A break in the inner loop leaves the inner loop and carries on with the next round of the outer one. There is no built-in way to break out of two loops at the same time.
numbers = [1, 2, 3]
print('break leaves the inner loop only:')
for outer in numbers:
for inner in numbers:
print(' outer=', outer, 'inner=', inner)
break
print(' back in the outer loop')
How can you stop both loops at once?
There are three approaches, and the best one is usually the simplest. Do not nest the loops at all. If you are looking for the first matching pair, return as soon as you find it, and the function ends with both loops gone.
def find_pair(values, target):
"""Return the first pair that adds up to target, or None."""
for index, value in enumerate(values):
for other in values[index + 1:]:
if value + other == target:
return value, other
return None
print('found ->', find_pair([3, 7, 11, 15], 26))
print('missing ->', find_pair([1, 2, 3], 100))
Returning is clean, because it carries the answer with it as well. The slice values[index + 1:] stops the function from comparing an element with itself, and it stops the same pair from being found twice in a different order.
When you genuinely cannot return, a flag variable is the straightforward approach. Set it when you find what you are looking for, then check it after the outer loop and break out of that. It works, and it reads worse than the version that returns. The third option, which is a break inside the inner loop followed by a condition check in the outer loop, is the same idea with more moving parts.
values = [3, 7, 11, 15]
target = 26
found = None
for outer in values:
for inner in values:
if outer + inner == target:
found = (outer, inner)
break
if found is not None:
break
print('flag version ->', found)
Compare that with the returning version from a moment ago, and you can see why the early return is worth preferring. The flag version has to keep the answer somewhere, it has to keep a second condition, and it has to remember to check that condition after the inner loop. The returning version has a single path through the code.
What is the loop-else construct, and why does it exist?
Python lets you attach an else block to a for or while loop. The block fires when the loop ends normally, and it does not run if you left the loop with break. In other words, the else block means "the loop finished without being interrupted".
def locate(values, target):
for index, value in enumerate(values):
if value == target:
print('found', target, 'at index', index)
break
else:
print(target, 'is not in the list')
return None
return index
print(locate([10, 20, 30], 20))
print(locate([10, 20, 30], 99))
This is exactly the shape of a search. The else block is the "not found" branch, and it replaces the flag variable that older languages force you to declare, to initialise, and to remember to check later. The while version works in the same way.
attempts = 0
while attempts < 3:
attempts += 1
print('attempt', attempts)
else:
print('the loop finished without a break')
print('---')
attempts = 0
while attempts < 3:
attempts += 1
if attempts == 2:
print('stopping early')
break
else:
print('this line is skipped because we broke out')
Most people meet this construct and assume that it is a mistake, because an else after a loop looks like it should mean "when the condition was false". It nearly does. The else runs when the loop ends without a break, which for a while loop means that the condition became false, and for a for loop means that the iterable ran out.
When should you avoid nesting loops?
Whenever the inner loop is doing a lookup that a dictionary can do for you. Searching a list of pairs for each item is quadratic work, and indexing the pairs once and then looking each item up directly is linear.
rows = [('a', 1), ('b', 2), ('c', 3)]
targets = ['a', 'c', 'z']
# A nested search.
found = []
for target in targets:
for name, value in rows:
if name == target:
found.append((target, value))
break
# One lookup instead.
lookup = dict(rows)
found = []
for target in targets:
if target in lookup:
found.append((target, lookup[target]))
print('found ->', found)
Two other habits keep nesting under control. Give the inner loop a meaningful name, because i and j make a three-level nest impossible to read. And if you find yourself needing a third level of nesting, it is usually a sign that the data should be restructured rather than that the loop should be deeper.
It also helps to keep the body of the inner loop trivial. A nested loop whose inner body runs for twenty lines is hard to think about, because you have to hold two pieces of state in your head at the same time. When that happens, take the inner work out into a function and call it, so that each level has one clear job.
Your turn: find pairs in a grid
- Write a function that takes a list of numbers and a target, and returns every pair that adds up to the target, using two nested loops. Print the pairs for
[3, 7, 11, 15, 20]and26. - Add a guard so that the same pair is never reported twice, and confirm that the count of results matches what you expect by hand.
- Rewrite the function so that it returns immediately on the first match, and check that it finds the same pair as the version that collects everything.
- Now write a search function that reports "not found" using the
for ... elseconstruct instead of a flag variable, and confirm that the message appears only when the item is genuinely missing. - Finally, build a small two-dimensional list of numbers, print it as a grid, and use a nested loop to find every position that holds the maximum value. Print the coordinates.
Patterns to remember
- A nested loop multiplies the work, so ten by ten is a hundred iterations.
breakandcontinueonly affect the loop that they are written in.- Return early instead of trying to break out of two loops at the same time.
- The
elseclause of a loop runs only when the loop finished without abreak, which makes it the natural home for "nothing was found". - Replace an inner search loop with a dictionary lookup when the inner work is really a lookup.