I don't like nested for-loops, is that bad?

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

34 Replies - 3950 Views - Last Post: 20 April 2015 - 12:32 AM

#1 kathy025   User is offline

  • D.I.C Head

Reputation: 41
  • View blog
  • Posts: 190
  • Joined: 19-December 14

I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:19 PM

Whenever a problem arises where I need a nested for-loop, I will always find an alternative method that does not require it (which succeeds most of the time). Only as a last resort will I use nested for-loops if I do not find anything else. Reason being, I find nested for-loops messy to read and trace.

Is avoiding nested for-loops a bad idea?
Is This A Good Question/Topic? 0
  • +

Replies To: I don't like nested for-loops, is that bad?

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 14761
  • View blog
  • Posts: 59,010
  • Joined: 12-June 08

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:23 PM

Actively avoiding a viable option because you have trouble tracing the flow of the code or understanding the inter operation of the program is indeed a bad thing. It highlights a deficiency you are intentionally going out of your way to not correct or shore up.
Was This Post Helpful? 1
  • +
  • -

#3 Martyr2   User is online

  • Programming Theoretician
  • member icon

Reputation: 5338
  • View blog
  • Posts: 14,233
  • Joined: 18-April 07

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:27 PM

Yes, you need to get comfortable with nested for loops. Because even if you can avoid them, others do not and it is very common practice to see nested loops. In addition to this, often code that you write to get around a nested for loop is going to be either less efficient or not exactly the same... not to mention most likely more verbose.

Now what you should not do or see happening is nested for loops more than three levels deep. If you see this, you most likely can take out the inner loops and put them into their own functions (refactoring) to make things easier to read.

But nested for loops are definitely a thing you will run into a lot and need to write a lot. Especially if you find yourself working with multi-dimensional arrays, record sets or anything in a tabular format. Even things like collections often have nested loops.

Just practice with them and attack them head on. You will get more and more comfortable with them. One trick to help is just make sure you label all your indexes appropriately. If you find it hard to read when using variables like "i, j and k" then give them real names like "row" or "column" etc.

:)

This post has been edited by Martyr2: 14 April 2015 - 12:27 PM

Was This Post Helpful? 2
  • +
  • -

#4 kathy025   User is offline

  • D.I.C Head

Reputation: 41
  • View blog
  • Posts: 190
  • Joined: 19-December 14

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:40 PM

Hey guys, thanks. What do you make of articles that discourage nested for-loops due to complexity and apparently "slower performance"?

http://programmers.s...ed-bad-practice
Was This Post Helpful? 0
  • +
  • -

#5 andrewsw   User is offline

  • awks lol ffs
  • member icon

Reputation: 6693
  • View blog
  • Posts: 27,474
  • Joined: 12-December 12

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:49 PM

The accepted answer at that link emphasises a point that modi123_1 has already made:

Quote

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

The second answer:

Quote

In many cases, there's a much faster and less wasteful way..

I think I would prefer to say "in some cases".

This post has been edited by andrewsw: 14 April 2015 - 12:54 PM

Was This Post Helpful? 1
  • +
  • -

#6 BetaWar   User is offline

  • #include "soul.h"
  • member icon

Reputation: 1597
  • View blog
  • Posts: 8,418
  • Joined: 07-September 06

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:56 PM

Learning nested loops and becoming comfortable with them will help out in the long run as has been said. For example, if you have a 3D array passed in which would you rather look at?

struct index3d
{
  int i;
  int j;
  int k;
};

index3d findValue(int value, int*** array, index3d sizes)
{
  int i;
  int j;
  int k;
  for(i = 0; i < sizes.i; i++)
  {
    for(j = 0; j < sizes.j; j++)
    {
      for(k = 0; k < sizes.k; k++)
      {
        if (array[i][j][k] == value)
        {
          return {i, j, k};
        }
      }
    }
  }
  return {-1, -1, -1};
}




Or:
struct index3d
{
  int i;
  int j;
  int k;
};

index3d findValue(int value, int*** array, index3d sizes)
{
  int i;
  for(i = 0; i < sizes.i * sizes.j * sizes.k; i++)
  {
    int a = i / (sizes.j * sizes.k);
    int b = (i - (a * sizes.j * sizes.k)) / (sizes.k);
    int c = i - (a * sizes.j * sizes.k) - (b * sizes.k);
    if (array[a][b][c] == value)
    {
      return {a, b, c};
    }
  }
  return {-1, -1, -1};
}



NOTE - I am not 100% sure that the math is correct on the second example, but as you can see it isn't as intuitive to understand what is going on in the second example (at least, that's the case for me).
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11392
  • View blog
  • Posts: 19,431
  • Joined: 19-March 11

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 12:59 PM

*
POPULAR

While nested loops are a legitimate practice and often required, there is some benefit in trying to avoid them, both from an efficiency standpoint and from a style standpoint. Efficiency is obvious: nested loops over structures imply poor scaling. If there's an alternative that actually avoids the need to count up to n, n times, you should consider it - if it actually gets the job done.

Sometimes, you actually need to nest a loop, though. And then, in terms of style and readability, it might well be worth naming the operation of the inner loop and turning it into a function. This has the advantage of making the code simpler and easier to read, but there is the drawback of potentially hiding some computational complexity. Having the nested loop in front of your face really makes the algorithmic load pretty obvious.

So, as always, it's a tradeoff. Absolutes are to be avoided at all costs.
Was This Post Helpful? 5
  • +
  • -

#8 kathy025   User is offline

  • D.I.C Head

Reputation: 41
  • View blog
  • Posts: 190
  • Joined: 19-December 14

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 01:01 PM

I see. This came to my mind because we were trying to work on an exercise removing duplicates from a char[] in PHP. We tried nesting 2 foreach-loops, but didn't get the desired results, until we found the array_unique() from the documentation that does it in a cleaner way.

There was a similar time in Java, where I used the HashSet to check for duplicates, since add() returns false if it is a duplicate.

When iterating lists-of-lists though, I have no choice haha.

View Postjon.kiparsky, on 15 April 2015 - 03:59 AM, said:

in terms of style and readability, it might well be worth naming the operation of the inner loop and turning it into a function.

...

So, as always, it's a tradeoff. Absolutes are to be avoided at all costs.

This is nice. Will keep this in mind.

This post has been edited by kathy025: 14 April 2015 - 01:08 PM

Was This Post Helpful? 0
  • +
  • -

#9 BetaWar   User is offline

  • #include "soul.h"
  • member icon

Reputation: 1597
  • View blog
  • Posts: 8,418
  • Joined: 07-September 06

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 01:11 PM

View Postjon.kiparsky, on 14 April 2015 - 08:59 PM, said:

Sometimes, you actually need to nest a loop, though. And then, in terms of style and readability, it might well be worth naming the operation of the inner loop and turning it into a function. This has the advantage of making the code simpler and easier to read, but there is the drawback of potentially hiding some computational complexity. Having the nested loop in front of your face really makes the algorithmic load pretty obvious.


Once again, I would say this depends. For instance, if you are working in a storage product in the IO path each instruction matters. Not because adding one or two takes a lot of time on the processor, but because those 1 or 2 extra ticks grow exponentially over 100,000+ IOPs. I have had times where I was told I had to clean up a function and eliminate duplicate code between two functions without adding a single extra assembly instruction to the output.

Assuming that an assembly instruction can be run at 3.4GHz (3.4 billion ticks per second) with an incoming 100,000 IOPs (I/O per second). A single instruction (assuming it takes 1 tick to complete) added to the code path adds latency, which slows down the product, and in the storage world speed and redundancy are _very_ important.

What this all comes down to, is me saying that there are certain times where every instruction counts.
Was This Post Helpful? 2
  • +
  • -

#10 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,020
  • Joined: 11-December 07

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 02:26 PM

I like to think of code as malleable.

Some ways to remove nested loops are:
- extracting a method
- unrolling a loop
- using modulo arithmetic (as above)

Some ways to create nested loops are:
- inlining a method
- statements to loop (reverse of unrolling)
- if to while (google transformation priority premise)

If you can become comfortable moving code around then you can forget about making arbitrary rules and shoot for the code that best describes the problem. After all, if you are comfortable manipulating code, you can always choose a different organisation later on.
Was This Post Helpful? 2
  • +
  • -

#11 Martyr2   User is online

  • Programming Theoretician
  • member icon

Reputation: 5338
  • View blog
  • Posts: 14,233
  • Joined: 18-April 07

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 02:42 PM

kathy025 if you are really interested in this sort of thing I recommend reading the book "Code Complete 2" by Steve McConnell. In there they talk about looping and when it can get tricky. It also covers some ways to avoid tricky nested loops but at no point do you see him trying to eliminate them if the situation calls for them.

And as the second answer in that link you posted, their example has to have all these requirements in order to make sure it runs properly (sorted, same size etc etc). Part of the reason why if you had gone with a straight nested loop you could avoid making "whitty" or "clever" algorithms that lead to crappy code just to avoid using a legitimate control structure.

I think we can all agree that nested loops are necessary if the problem warrants it and it is the cleanest solution. I think we can all agree that you will also see it often in other code and will see others writing them. Like them or hate them, they are a part of the programmer toolbox. Use where appropriate. The ultimate goal here is clean readable and maintainable code.

:)
Was This Post Helpful? 0
  • +
  • -

#12 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11392
  • View blog
  • Posts: 19,431
  • Joined: 19-March 11

Re: I don't like nested for-loops, is that bad?

Posted 14 April 2015 - 07:35 PM

View PostBetaWar, on 14 April 2015 - 03:11 PM, said:

Once again, I would say this depends.


Well, yes. I think that's kind of what I said - it's a tradeoff. The trick is knowing what you're trading for what, and knowing how to value the one and the other.
Was This Post Helpful? 0
  • +
  • -

#13 kathy025   User is offline

  • D.I.C Head

Reputation: 41
  • View blog
  • Posts: 190
  • Joined: 19-December 14

Re: I don't like nested for-loops, is that bad?

Posted 15 April 2015 - 03:08 AM

Thanks everyone. I have decided to use methods if the API already provides it. Like in this Java example:
class DuplicatesInArray {
	public static void main(String[] args) {
		String[] strArray = {"abc", "def", "mno", "xyz", "pqr", "xyz"};

		// 1. Using Brute Force Method

		for(int i = 0; i < strArray.length-1; i++) {
			for(int j = i+1; j < strArray.length; j++) {
				if((strArray[i].equals(strArray[j])) && (i != j)) {
					System.out.println("Duplicate Element is : " + strArray[i]);
				}
			}
		}

		// 2. Using HashSet

		HashSet<String> set = new HashSet<String>();

		for(String arrayElement : strArray)
		{
			if(!set.add(arrayElement)) {
				System.out.println("Duplicate Element is : " + arrayElement);
			}
		}
	}
}


Source: http://javaconceptof...ts-in-an-array/

I personally find the HashSet approach cleaner and readable than the brute-force approach.

Quote

you can always choose a different organisation later on.

This is also a nice tip.

It seems the general consensus is "use when necessary". :)
Was This Post Helpful? 0
  • +
  • -

#14 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,020
  • Joined: 11-December 07

Re: I don't like nested for-loops, is that bad?

Posted 15 April 2015 - 04:29 AM

That is a good idea but don't be shy to create your own methods too. For example, you could separate finding duplicates from printing them, which would make the "finding" method more generally useful.

	void printDuplicates(Object... arr) {
		for(Object o : findDuplicates(arr))
			System.out.println(o + " is duplicated.");
	}

	<T> List<T> findDuplicates(T... arr) {
		List<T> all = new ArrayList<>(Arrays.asList(arr));
		for(T t : new HashSet<>(all))
			all.remove(t);
		return all;
	}


Was This Post Helpful? 1
  • +
  • -

#15 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6718
  • View blog
  • Posts: 22,932
  • Joined: 05-May 12

Re: I don't like nested for-loops, is that bad?

Posted 15 April 2015 - 07:25 AM

View Postjon.kiparsky, on 14 April 2015 - 03:59 PM, said:

... in terms of style and readability, it might well be worth naming the operation of the inner loop and turning it into a function.

And other times it maybe worth converting the outer structure of the loop into a function or set of functions.

So instead of:
void ScanAllCells(DataSet dataset, Action doIt<Cell> doIt)
{
    for (var table in dataset.Tables)
    {
        for (var row in table.Rows)
        {
            for (var cell in row.Cells)
            {
                doIt(cell);
            }
        }
    }
}



You could have:
void ScanAllCells(DataSet dataset, Action doIt<Cell> doIt)
{
    for (var cell in EnumCells(EnumRows(dataSet.Tables)))
        doIt(cell);
}

IEnumerable<Row> EnumRows(IEnumerable<Table> tables)
{
    return tables.SelectMany(table => table.Rows);
}

IEnumerable<Cell> EnumCells(IEnumerable<Row> rows)
{
    return rows.SelectMany(row => row.Cells);
}



Or:
void ScanAllCells(DataSet dataset, Action doIt<Cell> doIt)
{
    for (var cell in dataSet.Tables
                            .SelectMany(table => table.Rows)
                            .SelectMany(row => row.Cells))
    {
        doIt(cell);
    }
}



In the cases above SelectMany() is another function that essentially does:
static IEnumerable<TResult> SelectMany<TSource, TResult>
        (
            this IEnumerable<TSource> source,
            Func<TSource, IEnumerable<TResult>> selector
        )
{
    for (var item in source)
    {
        for (var result in selector(item))
        {
            yield return result;
        }
    }
}



Again we are hiding the outer structure of the loops inside functions.

This post has been edited by Skydiver: 15 April 2015 - 07:45 PM
Reason for edit:: Fixed function name.

Was This Post Helpful? 1
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3