Breaking out of a nested loop

Started by
50 comments, last by ExErvus 7 years, 10 months ago

Its hard to give another approach given how abstract the code samples are, but as braindigitalis say if you are searching for something change the storage to something more suitable to perform a lookup. Also have others have said create a function that does the scan and returns the result so the return does the break.

From you sample this is faster to do the same lol

int i = 2;

int j = 0;

Ignore the try/catch exception route as it carries costs that make it perform worse than the other solutions presented.

Advertisement

If you've got two for loops you're looking at O(n*n) execution times.

I'd be tempted to refactor the code and eliminate the for loops if possible but that's just me...


In all seriousness, I'd be interested to see that.

for(int i = 0; i < 100; ++i)
{
    if(((i / 10) - 1) == ((i % 10) + 1))
        break;
}
at least 1 is gone and we only need a normal break :P

This is apparently common in Python (not just for breaking out of inner loops - iterators throw an exception when they reach the end of the container!), but in C++ I wouldn't recommend this. Even in Python I'm leery of doing this, since as ferrous points out exceptions are supposed to be for exceptional cases meaning abusing exceptions like this dilutes their meaning.

Python exceptions are not meant to represent exceptional error conditions alone, so it isn't an "abuse." As you point out, sequence iteration is terminated by raising StopIteration. This kind and level of exception usage is key to Python's dynamic, introspective nature.

As to the OP's question about breaking out of nested loops, assuming the code can not be refactored into a function a pair of adjacent linear iterations, and your language does not have labeled breaks, just use a goto.

(Amusingly, this very topic was covered in this very forum as far back as 2006, with the same conclusions drawn. The more things change…)

In all seriousness, I'd be interested to see that.


In idiomatic Python:

[(i, j) for i, j in itertools.product(range(10), range(10)) if i - 1 == j + 1]

C++ lacks the cartesian product built-in, but it isn't all that hard to write one in terms of iterator ranges.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

There was a lengthy debate/argument about this topic on the ISO C++ mailing lists earlier this year.

The take away I got was that few people on the committee want to spend any energy complicating C++ to handle the situation better under the strong belief that nested loops are bad code and just shouldn't be used.

I disagree with the reasoning, naturally, but it'll take someone with more eloquence than I and a very thorough and well-defended paper to change things, I think.

Sean Middleditch – Game Systems Engineer – Join my team!

If you've got two for loops you're looking at O(n*n) execution times.

I'd be tempted to refactor the code and eliminate the for loops if possible but that's just me...


In all seriousness, I'd be interested to see that.

for(int i = 0; i < 100; ++i)
{
    if(((i / 10) - 1) == ((i % 10) + 1))
        break;
}
at least 1 is gone and we only need a normal break tongue.png

And suddenly the code is more complicated and about 10-100x slower, because the divisions are taking many more cycles than the other simple operations.

Look ma! no breaks!


int i, j;

for(i = 0; i < 2; i++) {
    for(j = 0; j < 10; j++) {
        // if(i - 1 == j + 1) <- will be true for i==2 and j==0
    }
}

seriously though, how often will you have a situation where you need a nested loop and break out on an arbitrary condition and continue work after the loop?

Smells to me like a violation of SRP.

Some possible solutions depending on the actual algorithm:

Factor out the loop into another function and just return instead of breaking

or calculate the terminating condition beforehand and adjust the loop boundaries

or collect the affected elements and iterate over all of them

Awesome approach. But then again, it's setting up a lambda object (with captures and all) for no good reason. The compiler might optimize that out again, but that isn't granted.
Similar is true for any such construct involving function calls of which you can assume but don't know for sure that the compiler will optimize them away.


Just because I marked the lambda as capturing doesn't mean it necessarily will capture. It will (should?) only capture symbols that it references. That lambda should take up no space on the stack besides the argument to it. I'd be pretty disappointed with my compiler if it didn't optimize out the lambda.

Python exceptions are not meant to represent exceptional error conditions alone, so it isn't an "abuse." As you point out, sequence iteration is terminated by raising StopIteration. This kind and level of exception usage is key to Python's dynamic, introspective nature.


How so? What is done with exceptions that don't represent an error condition that can't be done with any other construct and is so essential to Python's nature?
One situation where I find myself doing this is when searching a 2-D board for a spot that satisfies some condition. I am perfectly happy to use a goto here, and some of the solutions that have been proposed wouldn't work (I don't want to change the looping variables, because I am interested in them, putting the loops in a function and using `return' might require writing a function that I cannot give a decent name to (a big no-no in my book) and having to pass a bunch of local variables for no good reason and returning two indices is messy...).
Honestly, I think it's hard to do better than the lambda solution, as far as clarity goes
    int i, j;
    [&] () {
        for(i = 0; i < 10; i++) {
            for(j = 0; j < 10; j++) {
                if(i - 1 == j + 1)
                    return;
            }
        }
    }();

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

This topic is closed to new replies.

Advertisement