Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 went home and 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"?

share|improve this question
3  
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
10  
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
2  
@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
    
@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
    
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
add comment

4 Answers

up vote 31 down vote accepted

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
2  
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
5  
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. –  user958624 May 23 '13 at 22:56
2  
@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
add comment

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.

share|improve this answer
8  
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
3  
For recursion I have two words "stack" and "overflow" –  Mateusz May 23 '13 at 20:45
    
@Mateusz while a stack overflow is possible most programs will not have this problem given modern OS stacks. The two biggest causes and more information is listed on devx.com/tips/Tip/14276 –  Travis Pessetto May 23 '13 at 21:11
5  
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
show 3 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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