Breaking out of two loops at once

Sunday 25 March 2012

This is a question that crops up often:

I have two nested loops, and inside, how can I break out of both loops at once?

Python doesn't offer a way to break out of two (or more) loops at once, so the naive approach looks like this:

done = False
for x in range(10):
    for y in range(20):
        if some_condition(x, y):
            done = True
            break
        do_something(x, y)
    if done:
        break

This works, but seems unfortunate. A lot of noise here concerns the breaking out of the loop, rather than the work itself.

The sophisticated approach is to get rid of, or at least hide away, the double loop. Looked at another way, this code is really iterating over one sequence of things, a sequence of pairs. Using Python generators, we can neatly encapsulate the pair-ness, and get back to one loop:

def pairs_range(limit1, limit2):
    """Produce all pairs in (0..`limit1`-1, 0..`limit2`-1)"""
    for i1 in range(limit1):
        for i2 in range(limit2):
            yield i1, i2

for x, y in pairs_range(10, 20):
    if some_condition(x, y):
        break
    do_something(x, y)

Now our code is nicely focused on the work at hand, and the mechanics of the double loop needed to produce a sequence of pairs is encapsulated in pairs_range.

Naturally, pairs_range could become more complex, more interesting ranges, not just pairs but triples, etc. Adapt to your own needs.

As with any language, you can approach Python as if it were C/Java/Javascript with different syntax, and many people do at first, relying on concepts they already know. Once you scratch the surface, Python provides rich features that take you off that track. Iteration is one of the first places you can find your Python wings.

tagged: » 18 reactions

Comments

[gravatar]
gruszczy 10:29 AM on 25 Mar 2012

Why not put double loop in a function and return instead of break?

def foo():
  for x in range(10):
    for y in range(20);
      if some_condition(x, y):
        return
      do_something(x, y)
Looks super simple to me.

However I still think this code is super ugly. This is better:
from itertools import product

for x, y in product(range(10), range(20)):
  if some_condition(x, y):
    break
  do_something(x, y)
I think that's the right way to do this. Double loops are evil.

[gravatar]
dima 10:30 AM on 25 Mar 2012

Have a look to http://docs.python.org/library/itertools.html#itertools.product

[gravatar]
Yannick 10:38 AM on 25 Mar 2012

You can also use itertools.product() instead of two explicit loops

for x, y in itertools.product(range(limit1), range(limit2)):
    ... 

[gravatar]
Ned Batchelder 10:46 AM on 25 Mar 2012

Thanks for the itertools.product suggestion. I was trying to show a simple example of abstracting a loop, without pulling in itertools just yet. Itertools is another great example of how Python provides interesting ways of abstracting away iteration details.

@gruszczy: putting the loops into a function is another option, true, though I'm not sure I find your solution better, since it would break up the larger code that this loop is in, without abstracting the double loop from the work in the loop.

[gravatar]
Juho Vepsäläinen 11:56 AM on 25 Mar 2012

I agree with the guys above. itertools.product definitely fits this case well. If you want to go functional, perhaps something like this might look nice (not so sure about perf):

if any([some_condition(a, b) for a, b in product(range(10), range(20)]):
    pass # do something

[gravatar]
Ned Batchelder 12:01 PM on 25 Mar 2012

@Juho: Your functional equivalent doesn't do the same thing as the original loop. The original would stop when some_condition was true, yours won't do anything until it is true, and has no access to the a and b value in any case.

[gravatar]
Juho Vepsäläinen 12:31 PM on 25 Mar 2012

@Ned: Good point. That's why I hinted about possible perf issue. It's true access to the values is a bit problematic as well. I guess "some_condition" could return a tuple you could then unpack. That in turn adds some extra logic to the code (uncool).

The situation would be a lot different if the whole clause was evaluated lazily (ie. a la Haskell). In that case the environment would take care of little perf tweaks such as this.

[gravatar]
David Boddie 1:04 PM on 25 Mar 2012

Or just raise an exception, catching it outside the loops...

[gravatar]
Marius Gedminas 1:23 PM on 25 Mar 2012

I'm sure the best way of dealing with this issue varies with the details of the particular bit of code where you encounter it.

The cases I've encountered personally were all certain bits of processing inside the outer loop (before the inner one), so abstracting the iteration away wouldn't have worked. Extracting the double loop into a function and using 'return' for early exit worked fine.

[gravatar]
Ned Batchelder 2:34 PM on 25 Mar 2012

@Juho, I'm sorry, I don't understand what performance issue you are talking about. Our two snippets of code do two different things, so there's no point comparing performance, is there?

@Marius, indeed, the actual code, and the extra complexity real code would introduce, will heavily influence the solution chosen.

Thanks, everyone, for adding ideas!

[gravatar]
MichaƂ Bartoszkiewicz 4:44 PM on 25 Mar 2012

You can always do

  (x, y) = next((x, y) for x in range(10) for y in range(20) if some_condition(x, y))
;)

[gravatar]
Nick Coghlan 9:35 PM on 25 Mar 2012

Was this post prompted specifically by the recent python-ideas thread that (yet again) proposed loop labels, or is that just a random coincidence?

[gravatar]
Ned Batchelder 10:09 PM on 25 Mar 2012

@Nick: it was prompted by a question in #python on freenode, though the python-ideas thread may have helped create a sense of "common question" in my mind...

[gravatar]
Mike 1:09 AM on 26 Mar 2012

How about using a generator expression. It keeps all the logic in one place instead of breaking it out into a separate function.

pairs = (i1, i2 for i1 in range(10) for i2 in range(20))
for x,y in pairs:
    if some_condition(x, y):
        break
    do_something(x, y)

[gravatar]
Paddy3118 3:54 AM on 26 Mar 2012

+1 on Mikes suggestion. It succinctly defines what is truly being iterated over, that is a pair and seems clear to me.

[gravatar]
Grant Rettke 3:31 PM on 26 Mar 2012

zip is what you are looking for Mike:

x = range(1,6)
y = range(6,11)
for xval, yval in zip(x,y):
	print xval, yva

[gravatar]
Mike 4:41 PM on 26 Mar 2012

Although it's not pretty, here's a solution that lets you perform some work inside an outer loop, before an inner loop starts. You can even do some work after the inner loop finishes.

The trick is to use the else-clause of the for loop. The else-clause is executed when a loop terminates normally, but is skipped on a 'break'.

As shown below, it can also be used for more deeply nested loops:

for x in range(10):
    a = function_of_x(x)

    for y in range(20):
        b = function_of_y(y)

        for z in range(30):
            if some_condition(a, b, z):
                break # out of for z in ... loop

            do_something(x, y, z)

        else:

            do_something_after_inner_loop(x,y)

            continue # for y in ...

        break # out of for y in ...

    else:
        continue # for x in ...

    break # out of for x in ...
@Grant: zip() does not provide the desired functionality. For
zip(range(10), range(20)), x and y would take on the sequence (0,0), (1,1), (2,2), ... (9,9).

For the generator expression, itertools.product, or the nested loops shown above, x and y take on the sequence: (0,0), (0,1), (0,2), ... (1,0), (1,1), ... (9,19).

[gravatar]
Eric Snow 10:58 PM on 27 Mar 2012

@Mike - here's a similar example (a snippet but you get the idea):

filename = getattr(module, "__file__", None)
for Loader, filetype in _MODULE_TYPES.items():
    for suffix in Loader.SUFFIXES:
        if filename.endswith(suffix):
            break  # breaks all the way out!
    else:
        continue
    break
else:
    # the condition inside the inner loop was not met
    msg = "Could not identify loader for {}"
    raise ImportError(msg.format(filename))

Add a comment:

name
email
Ignore this:
not displayed and no spam.
Leave this empty:
www
not searched.
 
Name and either email or www are required.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.