Nested loops
-
Interesting article. However, according to these definitions a triple nested loop only has a complexity of 4, and the inventer suggested to break up code when exceeding a maximum complexity of 10(!).
(1)->(2)->(3)->(4)->(5)->(6)->(7)->(8)
^ ^ ^ | | |
| | | | | |
| | (9)<--- | |
| (0)<------------- |
(a)<-----------------------M = E − N + 2P = 13 - 11 + 2\*1 = 4Also, extracting the inner loop into a separate function does not even help, as it increases P:
(1)->(2)->(3)---(call)-->(4)->(5)->(6)
^ ^ | |
| | | |
| (7)<------------- |
(8)<-----------------------M1 = E1 − N1 + 2P1 = 9 - 8 + 2\*1 = 3(1)->(2)->(3)->(4)
^ |
| |
(5)<---M2 = E2 − N2 + 2P2 = 5 - 5 + 2\*1 = 2and
M = E - N + 2P = 14 - 13 +2*2 = 5So, by extracting a loop into another function, you are actually increasing the complexity, instead of reducing it!
"One common testing strategy, espoused for example by the NIST Structured Testing methodology, is to use the cyclomatic complexity of a module to determine the number of white-box tests that are required to obtain sufficient coverage of the module." The word module that they are referring to is basically a function. So the complexity generally gets measured on the function and not the whole program. Therefor braking a nested if into function calls will actually reduce/spread the complexity of each function making them simpler and easier to test. So instead of having one function with example a complexity of 25, you'll have 3 functions with a complexity of 10 each.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
-
That's just silly. Use as many nested loops as required for the algorithm and no more. It may be possible to re-factor and re-engineer the algorithm to make fewer loops, but that may make the code more complex, and harder to understand. Judicious use of The KISS principle is, I think, best.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von BraunAs many as necessary. And remember that code you call may itself have loops, so those should be considered nested as well. Refactoring nested loop to another method, class or module doesn't change the fact that it's nested.
Currently reading: "The Prince", by Nicolo Machiavelli
-
"One common testing strategy, espoused for example by the NIST Structured Testing methodology, is to use the cyclomatic complexity of a module to determine the number of white-box tests that are required to obtain sufficient coverage of the module." The word module that they are referring to is basically a function. So the complexity generally gets measured on the function and not the whole program. Therefor braking a nested if into function calls will actually reduce/spread the complexity of each function making them simpler and easier to test. So instead of having one function with example a complexity of 25, you'll have 3 functions with a complexity of 10 each.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
That's what I thought at first, too. But then, what is P?
-
for me personally if you are at a point of needing to deeper than two levels then you need to rethink the approach
Lobster Thermidor aux crevettes with a Mornay sauce, served in a Provençale manner with shallots and aubergines, garnished with truffle pate, brandy and a fried egg on top and Spam - Monty Python Spam Sketch
How about 3D plotting? Do we imagine the third axis?
"To alcohol! The cause of, and solution to, all of life's problems" - Homer Simpson "Our heads are round so our thoughts can change direction." ― Francis Picabia
-
How about 3D plotting? Do we imagine the third axis?
"To alcohol! The cause of, and solution to, all of life's problems" - Homer Simpson "Our heads are round so our thoughts can change direction." ― Francis Picabia
I've never been involved with 3d printing, at the moment I work on insurance solutions. So to be honest I wouldn't have the first clue where to start
Lobster Thermidor aux crevettes with a Mornay sauce, served in a Provençale manner with shallots and aubergines, garnished with truffle pate, brandy and a fried egg on top and Spam - Monty Python Spam Sketch
-
Follow up on the Variable names thread below, I would like to ask what is the level of nested loops that is acceptable in general? Most people would agree that three levels is acceptable, but I would say stop at two. The third loops gets a bit messy.
for(int i=0; i<100; i++) { //Okay
for(int j=0; j<100; j++) { //Acceptable
for(int k=0; k<100; k++) { //Messy
}
}
}I have a razor view for a model that contains categories, sub-categories and then the items. That's a 3 level foreach right there. Personally I don't think it's messy. Maybe the sub-categories could be refactored to a separate partial, but seeing as for now this is the only view using them I see no reason to do that:
var subCategoryGroups = Model.GroupBy(r => new { r.Category, r.SubCategory });
var categoryGroups = subCategoryGroups.GroupBy(r => r.Key.Category);foreach (var catGroup in categoryGroups)
{@catGroup.Key
@foreach (var subCatGroup in catGroup) {@subCatGroup.Key.SubCategory
@foreach (var item in subCatGroup) { @Html.ActionLink(item.DisplayName, "RunReport", new { item.ReportProcedureId }) } }}
-
That's what I thought at first, too. But then, what is P?
"For a single program (or subroutine or method), P is always equal to 1." Thus each function without having any loops/if-statements ect. starts with a complexity of 1.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
-
Follow up on the Variable names thread below, I would like to ask what is the level of nested loops that is acceptable in general? Most people would agree that three levels is acceptable, but I would say stop at two. The third loops gets a bit messy.
for(int i=0; i<100; i++) { //Okay
for(int j=0; j<100; j++) { //Acceptable
for(int k=0; k<100; k++) { //Messy
}
}
}The answer relates to performance. How does the nested loops effect performance? If it negatively impacts performance, can you refactor to get the same results with an increase in performance? If the answer is that it is negligible, and the code is easily comprehended, then how can you put a limit on what you genuinely need? If you were to unravel a three dimensional array in an application, would not three nested loops make sense? If not, then what? Would a series of self-pointing functions make more sense, have better performance, or be easier to read? I'd say no to all three points.
-
Making an arbitrary rule to have no more than one nested loop (two loops) *is* indeed a silly rule. See here[^] for an example where your arbitrary rule makes no sense. Your data structures, or database, or whatever may require more looping. Unrolling such loops usually results in harder-to-understand and often less efficient code. It may not be possible to re-engineer or re-factor the code without redoing the entire system. Often an unachievable goal for legacy and cost reasons. If this is a new system, then yeah, by all means go for it, if possible and truly better. I have found that often, it's not really better. See
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von BraunEvery situation is different, but too many levels of loops can overwhelm the maintenance programmer with complexity. Functions/methods exist to chop the logic into manageable chunks. After the first couple of loops, the rest can be abstracted away into a subroutine. This makes the function understandable, and if more detail is needed the subroutine can then optionally be examined.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
-
That's just silly. Use as many nested loops as required for the algorithm and no more. It may be possible to re-factor and re-engineer the algorithm to make fewer loops, but that may make the code more complex, and harder to understand. Judicious use of The KISS principle is, I think, best.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braunahmed zahmed wrote:
Use as many nested loops as required for the algorithm and no more.
I totally agree. But... One loop makes a problem linear on the number of items in the loop. Two loops generally makes it O(n squared). Three loops makes it O(n cubed). In most practical cases, once you get to three nested loops, you need to ask yourself, "Am I using an efficient algorithm to compute this result?" While there exist O(n cubed) algorithms, in the workaday world, you usually don't see them. Another thing, multiply nested loops so often happen because somebody didn't really understand lwhat they were iterating over. Many a gnarly function of hundreds of lines and loops nested three or four deep have I analyzed and converted to a far simpler form. The deep nesting is often a signal that you're "doing it wrong".
-
Follow up on the Variable names thread below, I would like to ask what is the level of nested loops that is acceptable in general? Most people would agree that three levels is acceptable, but I would say stop at two. The third loops gets a bit messy.
for(int i=0; i<100; i++) { //Okay
for(int j=0; j<100; j++) { //Acceptable
for(int k=0; k<100; k++) { //Messy
}
}
}Shameel wrote:
Most people would agree that three levels is acceptable, but I would say stop at two.
Not sure I have ever seen three. Certainly not recently. If I did it was only because it was spanning an array with 3 dimensions. I very seldom encounter two. I suspect that if this is something that you see more often than say once a year then someone is designing something wrong or your problem domain space itself leads to solutions that requires that. If the first then it is a design problem not a code problem. If the second then I would suspect that those working in that space should be comfortable with that idiom (more so than working in other domains) so it isn't a problem.
-
That's just silly. Use as many nested loops as required for the algorithm and no more. It may be possible to re-factor and re-engineer the algorithm to make fewer loops, but that may make the code more complex, and harder to understand. Judicious use of The KISS principle is, I think, best.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von BraunI like short functions - anything longer than 10 lines is suspicious, IMO, and I never encountered a case where I absolutely needed more than 200 lines in one function. If you have three levels of nesting, there's place for extracting a function, giving it a decent, speaking and reasonable name (occasionally a long one, but that's IMO still better than writing comments - compilers don't check comments). Thus, I'd say nesting beyond three is rarely justified. And extracting smaller functions just makes the code better readable, not worse.
-
mark merrens wrote:
c) Two: anything else is lunacy and must be stamped out: 2 dimensions is more than enough for anybody!
That statement pretty much reminds me of
someone once supposedly said:
No one will ever need more than 640KB of memory
In geometry, I can easily think of problems that require 6 or more nested loops. In tensor analysis, double that. I could imagine that top notch physicists and mathematicians may need even more, occasionally. How do you think they model their ideas about 10-, 20- or higher-dimensional space-time? You can not refactor away the need for a nested loop. End of story.
Suppose you have some operation operating on multidimensional arrays. You don't write distinct versions for each number of dimensions, you use recursion. Recursion for such cases doesn't require more than one nesting level.
-
for (int index = 0; index < 1000000; index++)
{
int k = index % 100;
int j = (index / 100) % 100;
int i = index / 10000;
}Don't think so. That might be the worst possible way to do it.
for (int i = 0; i < 100; i++)
{
innerLoop(i);
}Great. So you thought you found the actual logic? Nope, Chuck Testa a useless outer loop that tells you nothing about what's going on. This might work if you have code bubbles[^], but otherwise it's like you have to keep turning stones one by one until you finally find the interesting part. It's probably the "accepted way" anyway, but it sucks. Any possible way to do this sucks. Fortunately it's not very common.
You assume innerLoop() is what the inner loop should be. Suppose you need to multiply an n-dimensional array by a constant. How about multiplySliceBy(index, mutiplier)? As long as you have mulitplySliceBy() defined for with dimension count from 1 up to an arbitrary upper limit, I think it's speaking code.
-
If that's in your satnav you must have to drive really slowly for all those nested function calls to complete before you arrive at wherever you wanted it to direct you to.
That was the case with ancient compilers/interpreters. Nowadays function calls are cheap in most cases (unless you put huge frames on the stack - i.e. your functions have very long parameter lists (I mean, several dozen parameters). If you're smart and put all parameters except the loop counters/indexes in a struct, you only need to pass a pointer to the struct - it's something pointer-like even when you pass the object in C# or Java, so it can be made very cheap. In C++, you can declare the functions inline, which will tell the compiler to produce code as if there weren't any functions. Thus, you get the best of for everybody: optimized code for the computer and readable code for human readers.
-
You assume innerLoop() is what the inner loop should be. Suppose you need to multiply an n-dimensional array by a constant. How about multiplySliceBy(index, mutiplier)? As long as you have mulitplySliceBy() defined for with dimension count from 1 up to an arbitrary upper limit, I think it's speaking code.
-
I like short functions - anything longer than 10 lines is suspicious, IMO, and I never encountered a case where I absolutely needed more than 200 lines in one function. If you have three levels of nesting, there's place for extracting a function, giving it a decent, speaking and reasonable name (occasionally a long one, but that's IMO still better than writing comments - compilers don't check comments). Thus, I'd say nesting beyond three is rarely justified. And extracting smaller functions just makes the code better readable, not worse.
moving code of inner loops into functions doesn't reduce the nestedness, often complicates the understanding and seldom makes things simpler.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun -
for me personally if you are at a point of needing to deeper than two levels then you need to rethink the approach
Lobster Thermidor aux crevettes with a Mornay sauce, served in a Provençale manner with shallots and aubergines, garnished with truffle pate, brandy and a fried egg on top and Spam - Monty Python Spam Sketch
'tis said by Linus Torvalds that "If you need more than 3 levels of indentation, you're screwed anyway, and should fix your program."[^] While this is a quote from 1995, it is certainly a guideline worth thinking about. When you have many levels of nesting, what are the options? - Collapse your 2D array into a flat array and reference using a multiplicative index (much like the underlying work done with a 2D array anyway) - Call a function when at a given depth, splitting the complexity into separate pieces and cutting the indentation. - Rework the program logic to require less indentation in the first place, such as using external variables or handling exceptions separately. These all have their good and bad points, and as always it depends on circumstances. As people here have pointed out, situations such as iterating across 3D constructs does often require additional levels of indentation to use. It's down to the situation at hand; if it makes things easier to read/maintain, then simplify things where you can. If "simpler" is more twisty and fragmented, then just tolerate the extra indentation and get back to work.
Sometimes a fist in the face says more than a thousand honeyed words.
-
Follow up on the Variable names thread below, I would like to ask what is the level of nested loops that is acceptable in general? Most people would agree that three levels is acceptable, but I would say stop at two. The third loops gets a bit messy.
for(int i=0; i<100; i++) { //Okay
for(int j=0; j<100; j++) { //Acceptable
for(int k=0; k<100; k++) { //Messy
}
}
}I always use one more than necessary:
for($ocd=0; $ocd
But other than that one special idiosyncrasy, as many loops that are necessary. It's helpful to use Iterators whenever possible, for languages that support them. Three loops are what I typically see.
-
I like short functions - anything longer than 10 lines is suspicious, IMO, and I never encountered a case where I absolutely needed more than 200 lines in one function. If you have three levels of nesting, there's place for extracting a function, giving it a decent, speaking and reasonable name (occasionally a long one, but that's IMO still better than writing comments - compilers don't check comments). Thus, I'd say nesting beyond three is rarely justified. And extracting smaller functions just makes the code better readable, not worse.
This will blow a circuit in you. I work at a place where we have some really old legacy code (from the 1980s). Functions are 500 to 2000 lines long and have very large switch statements (many cases). [The code was originally done in C, ported to C++, and some of it ported into C#.] Yes, it sucks badly. But, how would you refactor the code to make the function smaller. What design pattern(s) would you use to make it meaningful (show off your software design skills)? Thanks.