33

My lecturer mentioned today that it was possible to "label" loops in Java so that you could refer to them when dealing with nested loops. So I looked up the feature as I didn't know about it and many places where this feature was explained it was followed by a warning, discouraging nested loops.

I don't really understand why? Is it because it affects the readability of the code? Or is it something more "technical"?

  • 4
    If I remember my CS3 course correctly it's because it often leads to exponential time which means if you get a large data-set your application will become unusable. – Travis Pessetto May 23 '13 at 20:01
  • 21
    One thing you should learn about CS lecturers is that not everything they say applies 100% in the real world. I'd discourage loops nested more than a few deep, but if you have to process m x n elements to solve your problem, you're going to do that many iterations. – Blrfl May 23 '13 at 20:09
  • 8
    @TravisPessetto Actually it is still polynomial complexity - O(n^k), k being the number of nested, not exponential O(k^n), where k is a constant. – m3th0dman May 23 '13 at 20:19
  • 1
    @m3th0dman Thanks for correcting me. My teacher wasn't the greatest on this subject. He treated O(n^2) and O(k^n) as the same. – Travis Pessetto May 23 '13 at 20:20
  • 2
    Nested loops increase cyclomatic complexity (see here), which decreases the maintainability of a program, according to some people. – Marco May 29 '13 at 10:26
61

Nested loops are fine as long as they describe the correct algorithm.

Nested loops have performance considerations (see @Travis-Pesetto's answer), but sometimes it's exactly the correct algorithm, e.g. when you need to access every value in a matrix.

Labeling loops in Java allows to prematurely break out of several nested loops when other ways to do this would be cumbersome. E.g. some game might have a piece of code like this:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

While code like the example above may sometimes be the optimal way to express a certain algorithm, it is usually better to break this code into smaller functions, and probably use return instead of break. So a break with a label is a faint code smell; pay extra attention when you see it.

  • 2
    Just as a side note graphics use an algorithm that has to access every piece of a matrix. However, the GPU is specialized to handle this in a time-efficient way. – Travis Pessetto May 23 '13 at 21:04
  • Yes, GPU does this in a massively-parallel way; the question was about a single thread of execution, I suppose. – 9000 May 23 '13 at 22:16
  • 2
    One of the reasons labels tend to be suspect is because there's often an alternative. In this case you could return instead. – jgmjgm Jan 30 at 11:24
22

Nested loops are frequently (but not always) bad practice, because they're frequently (but not always) overkill for what you're trying to do. In many cases, there's a much faster and less wasteful way to accomplish the goal you're trying to achieve.

For example, if you have 100 items in list A, and 100 items in list B, and you know that for each item in list A there's one item in list B that matches it, (with the definition of "match" left deliberately obscure here), and you want to produce a list of pairs, the simple way to do it is like this:

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

With 100 items in each list, this will take an average of 100 * 100 / 2 (5,000) matches operations. With more items, or if the 1:1 correlation is not assured, it becomes even more expensive.

On the other hand, there's a much faster way to perform an operation like this:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

If you do it this way, instead of the number of matches operations being based on length(A) * length(B), it's now based on length(A) + length(B), which means your code will run much faster.

  • 10
    With the caveat that the sorting setup takes a non-trivial amount of time, O(n log n) twice, if Quicksort is used. – Robert Harvey May 23 '13 at 20:45
  • @RobertHarvey: Of course. But that's still far less than O(n^2) for non-tiny values of N. – Mason Wheeler May 23 '13 at 22:00
  • 10
    The second version of the algorithm is generally incorrect. First, it assumes that X and Y are comparable via < operator, which generally cannot be derived from the matches operator. Secondly, even if both X and Y are numeric, the 2nd algorithm may still produce wrong results, for example when X matches Y is X + Y == 100. – Pasha May 23 '13 at 22:56
  • 9
    @user958624: Obviously this is a very high-level overview of a general algorithm. Like the "matches" operator, the "<" must be defined in a way that is correct in the context of the data being compared. If this is done correctly, the results will be correct. – Mason Wheeler May 23 '13 at 23:41
  • PHP did something like that last one with their array unique I think and/or the opposite to it. People would instead just use PHP's arrays which are hash based and it would be much quicker. – jgmjgm Jan 30 at 15:09
11

One reason to avoid nesting loops is because it's a bad idea to nest block structures too deeply, irrespective of whether they're loops or not.

Each function or method should be easy to understand, both it's purpose (the name should express what it does) and for maintainers (it should be easy to understand the internals). If a function is too complicated to easily understand, that usually means that some of the internals should be factored out into separate functions so they can be referred to in the (now smaller) main function by name.

Nested loops can get difficult to understand relatively quickly, though some nesting of loops is fine - providing, as others point out, that doesn't mean you're creating a performance issue by using an extremely (and unnecessarily) slow algorithm.

Actually, you don't need nested loops to get absurdly slow performance bounds. Consider, for example, a single loop that in each iteration takes one item from a queue, then possibly puts several back - e.g. breadth-first search of a maze. The performance isn't decided by the depth of nesting of the loop (which is only 1) but by the number of items that get put in that queue before it's eventually exhausted (if it's ever exhausted) - how big the reachable part of the maze is.

  • 1
    You can very often just flatten a nested loop and it still takes the same time. take for 0 to width;for 0 to height; You can instead just put for 0 to width times height. – jgmjgm Jan 30 at 15:05
  • @jgmjgm - yes, at the risk of complicating the code inside the loop. Flattening can simplify that too sometimes, but more often you're at least adding the complexity of recovering the indices that you actually want. One trick for that is using an index type that factors all the loop nesting out into the logic for incrementing a special compound index - you're not likely to do that just for one loop, but maybe you have multiple loops with similar structures or maybe you can write a more flexible generic version. Overheads for using that type (if any) can be worth it for clarity. – Steve314 Jan 30 at 23:55
  • I'm not suggesting it as a good thing to do but as just how surprisingly simple it can be to turn two loops into one but still not have an impact on the time complexity. – jgmjgm Feb 10 at 7:37
7

Given the case of many nested loops you end up with polynomial time. For example given this pseudo code:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

This would be considered O(n^2) time which would be a graph similar to: enter image description here

Where the y-axis is the amount of time your program takes to terminate and the x-axis is the amount of data.

If you get too much data your program will be so slow nobody will wait for it. and It's not that much around 1,000 data entries I believe will take it too long.

  • 10
    you might wish to reselect your graph: that is a exponential curve not a quadratic one, also recursion doesn't make stuff O(n log n) from O(n^2) – ratchet freak May 23 '13 at 20:44
  • 5
    For recursion I have two words "stack" and "overflow" – Mateusz May 23 '13 at 20:45
  • 10
    Your statement that recursion can reduce an O(n^2) operation to an O(n log n) is largely inaccurate. The same algorithm implemented recursively vs iteratively should have the exact same big-O time complexity. Furthermore, recursion can often be slower (depending on language implementation), since each recursive call requires the creation of a new stack frame, while iteration only requires a branch/compare. Function calls are typically cheap, but they aren't free. – dckrooney May 23 '13 at 21:36
  • 2
    @TravisPessetto I've seen 3 stack overflows in last 6 months while developing C# applications due to recursion or cyclic objects references. What is funny about it that it will crash and you don't know what hit you. When you see nested loops you know that something bad may happen, and exception about wrong index for something is easily visible. – Mateusz May 24 '13 at 6:03
  • 2
    @Mateusz also, languages like Java allow you to catch a stack overflow error. This with a stack trace should let you see what happened. I don't have much experience, but the only time I've seen a stack overflow error is in a PHP that had a bug causing an infinite recursion and PHP ran out of the 512MB of memory that was assigned to it. Recursion needs to have a final terminating value it isn't good for infinite loops. Like everything in CS there is a time and a place for all things. – Travis Pessetto May 24 '13 at 7:39
0

Driving a thirty ton truck instead of a small passenger vehicle is bad practice. Except when you need to transport 20 or 30 tons of stuff.

When you use a nested loop, it’s not bad practice. It’s either utterly stupid, or it’s exactly what is needed. You decide.

However, someone complained about labelling loops. The answer for that: if you have to ask the question, then don’t use labelling. If you know enough to decide yourself, then you decide yourself.

  • If you know enough to decide yourself, you know enough not to use labelled loops. :-) – user949300 Jan 29 at 15:39
  • No. When you have been taught enough, you have been taught to not use labelled use. When you know enough you transcend beyond dogma and do what is right. – gnasher729 Jan 29 at 17:59
  • 1
    The issue with the label is that it's rarely needed and a lot of people use it early on to work around flow control mistakes. Sort of like how people put exit all over the place when they get flow control wrong. Functions also make it largely redundant. – jgmjgm Jan 30 at 15:12
-1

There's nothing inherently wrong or necessarily even bad about nested loops. They do however have certain considerations and pitfalls.

The articles you were led to, likely in the name of brevity or due to a psychological process known as being burnt, skipping over the specifics.

Being burnt is when you have a negative experience of something with the implicating being you then avoid it. For example I might cut vegetables with a sharp knife and cut myself. I might then say sharp knives are bad don't use them to cut vegetables to try to make it impossible for that bad experience to ever happen again. That's obviously very impractical. In reality you just need to be careful. If you're telling someone else to cut vegetables then you have an even stronger sense of this. If I were instructing children to cut vegetables I would very strongly feel to tell them to not use a sharp knife especially if I can't supervise them closely.

The problem is in programming is that you'll not meet peak efficiency if you always prefer safety first. In this case the kids can only cut soft vegetables. Confronted with anything else and they're only going to make a mess of it using a blunt knife. It's important to learn the proper use of loops including nested loops and you can't do that if they're deemed bad and you never try to use them.

As many answers here point out a nested for loop is an indication of the performance characteristics of your program which may get exponentially worse each nesting. That is, O(n), O(n^2), O(n^3) and so on which comprises O(n^depth) where depth represents how many loops you have nested. As your nesting grows, the time required grows exponentially. The problem is with this is that it's not a certainty either that your time or space complexity will be that (quite often a * b * c but not all nest loops may run all the time either) nor is it a certainty that you'll have a performance problem even if it is that.

For many people, particularly students, writers and lecturers who to be frank, rarely program for a living or on a day to day basis for loops may also be something they're not used to and that induced too much cognitive load on early encounters. This is a problematic aspect because there's always a learning curve and avoiding it wont be effective in converting students into programmers.

Nested loops can go wild, that is they can end up nested very deeply. If I go through each continent, then through each country, then through each city, then through each shop, then through each shelf, then through each product if it's a can of beans through each bean and measure it's size to get the average then you can see that'll nest very deeply. You'll have a pyramid and a lot of wasted space away from the left margin. You may even end up going off the page.

This is a problem that would be more significant historically where screens were small and of low resolution. In those cases even a few levels of nesting could genuinely take up a lot of space. This is a lesser concern today where the threshold is higher though it can still present a problem if there's enough nesting.

Related is the aesthetics argument. Many people do not find nested for loops aesthetically pleasing in contrast to layouts with more consistent alignment this may or may not be linked to what people are used to, eye tracking and other concerns. It is however problematic in that it tends to be self reinforcing and may ultimately make code harder to read as breaking up a block of code and encapsulating loops behind abstractions such as functions also risks breaking up the mapping of the code to the flow of execution.

There's a natural tendency towards what people are used to. If you're programming something in the simplest way the probability of needing no nesting is highest, the probability of needing one level drops off by an order of magnitude, the probability for another level drops off again. The frequency dropping and essentially meaning the deeper the nesting the less trained the human senses are to anticipate it.

Related to that is that in any complex construct, which a nested loop can be considered, then you should always ask is that the simplest possible solution as there's potential for a missed solution needing less loops. The irony is that a nested solution often is the simplest way to produce something that works with the minimum amount of effort, complexity and cognitive load. It's often natural to nest for loops. If you consider for example one of the answers above where the much faster way than a nested for loop is also far more complex and consists of significantly more code.

A great deal of care is needed as it's often possible to abstract loops away or flatten them yet with the end result ultimately being a cure worse than the disease particularly if you're not for example receiving a measurable and significant performance enhancement from the effort.

It's very common for people to frequently experience performance problems in association to loops which are telling the computer to repeat an action many times and will inherently often be implicated in performance bottlenecks. Unfortunately responses to this can be very superficial. It becomes common for people to see a loop and see a performance problem where there is none and then hide the loop from sight to no real effect. The code "looks" fast but put it on the road, key in the ignition, floor the accelerator and take a look at the speedometer and you might find it's still about as fast as an old lady walking her zimmer frame.

This kind of hiding is similar to if you have ten muggers on your route. If instead of having a straight route to where you want to go you arrange it so that there's a mugger behind every corner then it gives the illusion as you start your journey that there are no muggers. Out of sight out of mind. you're still going to get mugged ten times but now you wont see it coming.

The answer to you're question is that it's both, but neither concerns is absolute. They're either entirely subjective or only contextually objective. Unfortunately sometimes the entirely subjective or rather opinion takes precedent and dominates.

As a rule of thumb, if it needs a nested loop or that seems like the next obvious step, it's best not to deliberate and simply do it. However if any doubts linger then it should be later reviewed.

Another rule of thumb is that you should always check the cardinality and ask yourself is this loop going to be a problem. In my previous example I went through cities. For testing I might only go through ten cities but what's a reasonable maximum number of cities to expect in real world usage? I then might multiply that by the same for continents. It's a rule of thumb to always consider with loops especially that iterate a dynamic (variable) amount of times what that might translate to down the line.

Regardless always do what works first. The way when you do see an opportunity for optimisation your can compare your optimised solution against the easiest to get working and confirm that it yielded the benefits expected. You can also spend too long prematurely optimising before the measurements are in and that leads to YAGNI or a lot of wasted time and missed deadlines.

  • The sharp <-> blunt knife example isn't great, as blunt knives are generally more dangerous for cutting. And O(n) -> O(n^2) -> O(n^3) is not exponential in n, it's geometric or polynomial. – Caleth Jan 29 at 11:06
  • That dull knives are worse is a bit of an urban myth. In practice it varies and is usually specific to the case where dull knives are particularly unsuitable usually requiring a lot of force and involving a lot of slippage. You're right though, there's an hidden but inherent limitation there, you can only cut soft vegetables. I'd consider n^depth exponential but you're right those example on their own aren't. – jgmjgm Jan 30 at 9:22
  • @jgmjgm: n^depth is polynomial, depth^n is exponential. It's not really a matter of interpretation. – Roel Schroeven Jan 30 at 10:03
  • x^y is different to y^x? The mistake you made is that you never not read the answer. You've grepped for exponential and then grepped for equations that on their own aren't exponential. If you read you'll see I said it increases exponentially for each layer of nesting and if you put that to the test yourself, time for(a=0;a<n;a++);for(b=0;b<n;b++);for(c=0;c<n;c++); when adding or removing loops then you'll see that it is indeed exponential. You'll find one loop performs at n^1, two perform at n^2 and three perform at n^3. You fail to understand nested :D. Gemoetric subsets exponential. – jgmjgm Jan 30 at 10:32
  • I guess this does prove a point that people really do struggle with nested constructs. – jgmjgm Jan 30 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.