Continuing to an outer loop

Continuing to an outer loop

Rate This
  • Comments 39

When you have a nested loop, sometimes you want to “continue” the outer loop, not the inner loop. For example, here we have a sequence of criteria and a sequence of items, and we wish to determine if there is any item which matches every criterion:

match = null;
foreach(var item in items)
{
  foreach(var criterion in criteria)
  {
    if (!criterion.IsMetBy(item))
    {
      // No point in checking anything further; this is not
      // a match. We want to “continue” the outer loop. How?
    }
  }
  match = item;
  break;
}

There are many ways to achieve this. Here are a few, in order of increasing awesomeness:

Technique #1 (ugly): When you have a loop, the “continue” statement is essentially a “goto” which branches to the bottom of the loop, just before it does the loop condition test and pops back up to the top of the loop. (Apparently when you spell “goto” as “continue”, the “all gotos are all evil all the time” crowd doesn’t bother you as much.) You can of course simply make this explicit:

match = null;
foreach(var item in items)
{
  foreach(var criterion in criteria)
  {
    if (!criterion.IsMetBy(item))
    {
      goto OUTERCONTINUE;
    }
  }
  match = item;
  break;
OUTERCONTINUE:
  ;
}

Technique #2 (better): When I see a nested loop, I almost always consider refactoring the interior loop into a method of its own.

match = null;
foreach(var item in items)
{
  if (MeetsAllCriteria(item, critiera))
  {
    match = item;
    break;
  }
}

where the body of MeetsAllCriteria is obviously

foreach(var criterion in criteria)
  if (!criterion.IsMetBy(item))
    return false;
return true;

Technique #3 (awesome): The “mechanism” code here is emphasizing how the code works and hiding the meaning of the code. The purpose of the code is to answer the question “what is the first item, if any, that meets all the criteria?” If that’s the meaning of the code, then write code that reads more like that meaning:

var matches = from item in items
              where criteria.All(
                criterion=>criterion.IsMetBy(item))
              select item;
match = matches.FirstOrDefault();

That is, search the items for items that meet every criterion, and take the first of them, if there is one. The code now reads like what it is supposed to be implementing, and of course, if there are no loops in the first place then there’s no need to “continue” at all!

The biggest thing I love about LINQ is that it enables a whole new way to think about problem solving in C#. It’s gotten to the point now that whenever I write a loop, I stop and think about two things before I actually type “for”:

* Have I described anywhere what this code is doing semantically, or does the code emphasize more what mechanisms I am using at the expense of obscuring the semantics?

* Is there any way to characterize the solution to my problem as the result of a query against a data source, rather than as the result of a set of steps to be followed procedurally?

 

  • [OK, I understand that solving the initial question is not the point of the article ;) ]

    Do you have problems with the following code, that has been written, tried and run by generations of programmers :

    match = null;

    foreach(var item in items)

    {

     foreach(var criterion in criteria)

     {

       HasMatch=true;

       if (!criterion.IsMetBy(item))

       {

         // No point in checking anything further; this is not

         // a match. We want to “continue” the outer loop. How?

        HasMatch=false;

        break;

       }

     }

     if(HasMatch) {

        match = item;

        break;

     }

    }

    BTW, does the compiler optimizes out the building of the list of matches that you don't care about ?

  • I love the concepts of LINQ and find it very useful for doing many the small tasks involved with datasets in a very quick and easy to understand manner.  I really like that you can read a function and know what it is trying to accomplish rather than worrying about how... most of the time.

    My personal favorites are test grading queries:

    var numberCorrect = test.Questions.Count(question => question.SelectedAnswer == question.CorrectAnswer);

    I see you use the from/where/select syntax a lot, do you prefer it over the functional syntax?

  • This post brings to mind some performance considerations I came across while comparing LINQ to nested foreach loops, usually involving joining two lists. To get to the root of it, nested foreach statements seemed to perform better on smaller lists than LINQ; it seemed there would always be a few milliseconds consumed by LINQ, I suppose in some overhead. It was as the lists got progressively larger that LINQ shined; the loops would require significantly more time (geometrically or exponentially, I'm unsure of the appropriate term), whereas the LINQ results would only consume a minimal additional amount of time. On the one hand, I'm not sure if performance differences on smaller lists would make me consider giving up the syntax of LINQ, because it really isn't all that much time and I'm not really making performance-critical applications. On the other hand, if I'm having to join large lists together (where LINQ really shines), perhaps I need to reconsider exactly how I'm dealing with data in my code.

    I should point out here that I have not actually been able to replicate my earlier findings on my machine here at work. At home, the performance differences were very consistent. Here, it's a bit hit-or-miss. I can only say there are differences between the two machines and the software used, but my home machine is actually the more powerful of the two. It's... odd. 

    We shipped some performance improvements (I think in a service pack, though I don't recall the details) to the way that where-followed-by-select works; that might account for some of the difference. -- Eric

  • I never understood the hate for goto. I would argue that the first method is as good as the second and definitely better than the one suggested by Mauvaisours. Of course the third method is the best but if goto is so bad then why is it in C# (and how is it worse than Java's break label)?

    Note that the C# goto was carefully designed to be less hazardous than other languages' gotos. Labels have similar scoping rules as locals, which means that you can "goto" within a block, or go from an inner block to an outer block, but you cannot branch in to the middle of a try block, a loop, and so on. That makes it easier to analyze the preconditions of a given hunk of code. -- Eric

  • Welcome, algorithms guy, to the specification pattern.

  • I've started to consider 'foreach' to be a code smell, unless it's in a library class. Once you've got the extensions to IEnumerable<T>, and added a relatively small set of extra methods, 'foreach' becomes unnecessary in 'proper' code.

    That sounds odd, but for the most part pulling out a looping method makes most code easier to read.

  • Steve Cooper: I hope you're not suggesting that we should be using .Foreach() extension methods to perform side effects. I mean, you can suggest that foreach is unnecessary, but it's "bad" to use functional notation to produce non-functional output.

  • "BTW, does the compiler optimizes out the building of the list of matches that you don't care about ?"

    No, but since LINQ uses lazy evaluation as much as possible, the list of matches you don't care about isn't actually built at all anyway.

    (So the compiler doesn't optimize it, LINQ does.)

  • For Technique #3 one can also use the IEnumerable.Any method which does a boolean check to see if the IEnumerable is empty or not.  That alleviates checking for null, and also makes it easier to work with "value types" (where the default value is non-null).

    Etan Bukiet

  • Other languages support labelled continue's. Why doesn't C#? For example,

    OuterLoop: for ...  {  // for, foreach, while, etc

       for ... {  // Inner loop

           if (...)

               continue OuterLoop;

       }

    }

  • - Make entire look and condition maching a new function

    - Avoid extra complexity for such a simple task non recursive task (avoid Linq)

    Keep it as simple as possible so that the code does not fail the 'Monday morning without sleep the night before' understandability test.  This makes the next guy inheriting the code not waste time and money trying to understand using 2 lines of Linq to replace 4 lines of regular code.

  • The LINQ implementation is definitely concise, and to those who've taken the time to learn LINQ it would certainly be a faster read.

    How does the performance compare for traditional looping approaches and the concise LINQ implementation?

  • Anything wrong with:

    item myItem = items.Where(criterion=>criterion.IsMetBy(item)).Select(item).FirstOrDefault();

    ??

    This isn't right. The lambda parameter "criterion" in your example is not of type Criterion, it's of type Item. Remember, the query is "find the first item that meets *all* the criteria." -- Eric

     

    I use this method often when I am looking for a single record...

    Dave

  • "How does the performance compare for traditional looping approaches and the concise LINQ implementation?"

    For simple selecting based on a single criteria (meaning no nested loops), it certainly appears a loop holds its own versus LINQ, at least in my ridiculously uncomplicated tests involving building a list of ints and then selecting all ints less than some arbitrary value. For my purposes, I had a list of 80000 integers and then selected all integers less than the midpoint. On average, a loop did that in 2 milliseconds, LINQ did it in 5.

    Introduce a nested loop where I was going through that same list of 80000 integers and comparing it with another list of 66,667 integers (or whatever the number). All integers that were equal between the two lists were added to a third. Incidentally, there were 53,333 matches. It tooks the nested loops 33,319 milliseconds to arrive at that result. LINQ did it in 53.

    These are large lists and the testing scenario was absurd (the first list was all integers less than 100,000 and not divisible by 5, the second was integers less than 100,000 not divisible by 3), but it just goes to show that LINQ will achieve tremendous performance gains the more data you are working with when you are pairing it against other large sets of data. For simple filtering, maybe loops still work, but then you have to figure the syntax of LINQ versus a loop.

    Again, I note that the performance on my work machine is different than my home machine and there are software, hardware, and OS differences between the two machines, but the larger point of LINQ performance versus nested loops on large data structures remains.

    This doesn't make any sense to me. LINQ is not *magic*. Behind the scenes, it's doing all the same loops as the original program, it's just providing a more convenient syntax. Are you sure you are measuring the *execution* of the query? I would expect the *creation* of the query to take a few milliseconds and the *execution* to take just as long as the original, if not longer. Remember, the result of a query expression is a *query*, not *the results of the query*. -- Eric

  • While the LINQ solution is great for readability and with foreach doesn't applies, if you switch the inner loop to a 'for', you don't have to use break/continue...

     criteriaValid=true;
     for (int index=0; index < criteria.Count && criteriaValid; index++)
     {
       if (!criteria[index].IsMetBy(item))
       {
         criteriaValid = false;
       }
     }

    You can even then act accordingly on the outher loop using 'criteriaValid'.

    Just my 2 cents

Page 1 of 3 (39 items) 123