Nested loops
-
a) good point. b) never had to do anything like that so don't really care. c) Two: anything else is lunacy and must be stamped out: 2 dimensions is more than enough for anybody!
"If you think it's expensive to hire a professional to do the job, wait until you hire an amateur." Red Adair. nils illegitimus carborundum me, me, me
OK. We shall have a road roller run over you to flatten you into two dimensions. :laugh:
-
Shameel wrote:
I would like to ask what is the level of nested loops that is acceptable in general?
Zero! What's Wrong with the For Loop[^]
From that article: Here's a common example: double sum = 0;for (int i = 0; i < array.length; i++) { sum += array[i];} What's going on here? I've been programming for years, and I'm comfortable speed-reading this idiom; it's obviously a summation of a set of values in an array. But to actually read this block of code, I need to process about 30 tokens spread out over four lines. And here are programmers writing pragma, karma and dogma at the beginning of their programs and they have the gall to complain about a for loop? :wtf:
-
I never go further than 26 levels, because then I've run out of variables to control the loops with. I could of course start using aa, ab, ac...but that gets confusing.
Wrong of you to use a thru z as control variables. Use a1, a2, ......... and it will not be confusing at all! :laugh:
-
ahmed zahmed wrote:
That's just silly.
No, it's not.
ahmed zahmed wrote:
It may be possible to re-factor and re-engineer the algorithm to make fewer loops
That's the whole point of making this post. :-) I've seen loops neck deep where the reviewer would find commiting suicide easier than coming out of it.
If there are nested loops, most of the time they are necessary. The only way to refactor that would be to extract the inner loop(s) into a new method, but that would not remove the loops. If a loop could be refactored into something not requiring the equivalent of a loop (such as recursion), then you should 'refactor your programmer', not your code! ;) So I agree with ahmed zahmed, that in general the notion you expressed is silly. It's quite different if you got nested branching (if or switch statements). There are many ways to rewrite an algorithm in a way that avoids nested branching, and too much nesting often indicates a bad structure that does require refactoring. Of course there are always exception, but in general nested loops cannot be sensibly refactored, whereas nested branching can and often should be.
-
As many as required, but no more. Limiting the number of nested loops is like prescribing a length for variable names: "Variable names must be at least six characters and no more than 31 characters in length, must begin with an upper case alphabetic character, may not include an underscore, and must consist of one or more complete English words, signified through use of upper case characters at the beginning of each word". Picking names will be like playing Scrabble...
Software Zen:
delete this;Sounds like a valid password policy!
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood 'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
-
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 would say that a rule is ok and if that rule gets broken, a good justification as to why it was broken needs to be given. One can always refactor code to eliminate loops/complexity. I feel that it is especially important if the code needs to be tested to make such a rule. (else the testing cost more money than you're making on the project) Bad Example:
String name[100][100] = fill_string();
void loop_level_1()
{
for(int i=0; i<100; i++)
{
loop_level_2(i);
}
}void loop_level_2(int i)
{
for(int j=0; j<100; j++)
{
loop_level_3(i, j);
}
}void loop_level_3(int i, int j)
{
for(int k=0; k<100; k++)
{
print(k + ": " + name[i][j]);
}
}This way, each function can be tested in isolation.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
-
a) good point. b) never had to do anything like that so don't really care. c) Two: anything else is lunacy and must be stamped out: 2 dimensions is more than enough for anybody!
"If you think it's expensive to hire a professional to do the job, wait until you hire an amateur." Red Adair. nils illegitimus carborundum me, me, me
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.
-
I would tend to refactor the loops into smaller methods so that I can follow it easier:
public void IterateOverRoadNetwork(RoadSegments[] segments)
{
foreach (RoadSegment segment in segments)
{
CheckNetworkSpeeds(segment);
}
}
public void CheckNetworkSpeeds(RoadSegment segment)
{
foreach (Vehicle vehicle in segment.Vehicles)
{
CheckForImpossibleRoute(vehicle);
}
}
public void CheckForImpossibleRoute(Vehicle vehicle )
{
foreach (VehicleRestriction restriction in vehicle.Restrictions)
{
//
}
}By doing this, I can name methods for their intent, so I can see what they are trying to do. That's my preferred option.
*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington
"Mind bleach! Send me mind bleach!" - Nagy Vilmos
My blog | My articles | MoXAML PowerToys | Mole 2010 - debugging made easier - my favourite utility
That's exactly the kind of pitfall DB programmers fall into. You have to see the whole picture if you wish to optimize such involved queries. You may have successfully hidden the fact there are 3+ nested loops, but that doesn't do away with them, and all you achieved is that it's now impossible to see any possible relations that may help you optimize away some of the looping: e. g. if you're checking a motorway network, you may want to restrict your loops only to such vehicles allowed on motorways in
CheckNetworkSpeeds(). By separating the loops you make it much harder to spot such optimizations. Wasn't the whole point of avoiding nesting to make the code easier to maintain? -
I would say that a rule is ok and if that rule gets broken, a good justification as to why it was broken needs to be given. One can always refactor code to eliminate loops/complexity. I feel that it is especially important if the code needs to be tested to make such a rule. (else the testing cost more money than you're making on the project) Bad Example:
String name[100][100] = fill_string();
void loop_level_1()
{
for(int i=0; i<100; i++)
{
loop_level_2(i);
}
}void loop_level_2(int i)
{
for(int j=0; j<100; j++)
{
loop_level_3(i, j);
}
}void loop_level_3(int i, int j)
{
for(int k=0; k<100; k++)
{
print(k + ": " + name[i][j]);
}
}This way, each function can be tested in isolation.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
The question is why you think nested loops are broken in the first place? The only thing you achieve is separate the context in which the need for nested loops arose, and therefore remove the ability to spot possible optimizations easily.
-
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
}
}
}Care to share your definition of 'messy'? And why you think it needs to be fixed? What is your suggested fix, and why do you think that would be an improvement?
-
The question is why you think nested loops are broken in the first place? The only thing you achieve is separate the context in which the need for nested loops arose, and therefore remove the ability to spot possible optimizations easily.
-
The question is why you think nested loops are broken in the first place? The only thing you achieve is separate the context in which the need for nested loops arose, and therefore remove the ability to spot possible optimizations easily.
Refer to: http://en.wikipedia.org/wiki/Cyclomatic_complexity[^] more specifically the section on "Implications for Software Testing", for a better understanding from where I'm coming from.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
-
Refer to: http://en.wikipedia.org/wiki/Cyclomatic_complexity[^] more specifically the section on "Implications for Software Testing", for a better understanding from where I'm coming from.
"Program testing can be used to show the presence of bugs, but never to show their absence." << please vote!! >>
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!
-
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!! >>