C# - Most efficient way to iterate through multiple arrays/list

Question

I have five arrays of varying lengths and I need to iterate through all of them generating all possible combinations of the contents. I'm currently using 5 nested for loops like so:

for (int a = 1; a < Array1.Length - 1; a++)
  {
    for (int b = 1; b < Array2.Length - 1; b++)
      {
        for (int c = 1; c < Array3.Length - 1; c++)
          {
            for (int d = 1; d < Array4.Length - 1; d++)
              {
                for (int e = 1; e < Array5.Length - 1; e++)
                  {
                    //do something
                  }
              }
          }
      }
  }

Due to the size of the arrays, I end up with more than 456 million iterations. I'm pretty new to programming in general, and C# specifically. I'm just curious if there is a more efficient way to accomplish this.

Thank you.

Q: Why do you "need to iterate through all of them generating all possible combinations of the contents"? — Mitch Wheat
– Mitch Wheat, Commented Dec 1, 2012 at 0:57
Just as aside, your counters in loops should start from 0 (c# uses zero based indexes) and go up until Length (counter < Length not counter < Length-1) — Nikola Davidovic
– Nikola Davidovic, Commented Dec 1, 2012 at 0:58
Regardless how the code looks, if there are 456 million combinations to be made, there will be 456 total iterations of all the elements. — jcolebrand
– jcolebrand, Commented Dec 1, 2012 at 0:58
The number of permutations of the five arrays will be >456 million no matter what technique you use to generate them. For a linq approach that handles an arbitrary number of arrays, see blogs.msdn.com/b/ericlippert/archive/2010/06/28/… — phoog
– phoog, Commented Dec 1, 2012 at 0:59
Is he asking about ways of making the loops faster (peephole optimizations)? — RonaldBarzell
– RonaldBarzell, Commented Dec 1, 2012 at 0:59

Sergey Kalinichenko · Accepted Answer · 2012-12-01 01:00:33Z

5

You go though that many iterations because there are that many combinations: this is called combinatorial explosion. You cannot do it more efficiently if you must go through all possible combinations.

You can code it with fewer lines of code or without hard-coding the number of arrays (five in your case) by using recursion. However, the number of iterations is not going to change, only the number of lines of code.

void processCombination(int[] combination) {
    // combination[i] has the index of array #i
    ...
}
void combine(int p, int[] indexes, int[] sizes) {
    if (p == indexes.Length) {
        processCombination(indexes);
    } else {
        for (indexes[p] = 0 ; indexes[p] != sizes[p] ; indexes[p]++) {
            combine(p+1, indexes, sizes);
        }
    }
}

answered Dec 1, 2012 at 1:00

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

sybkar Over a year ago

Well, that's not entirely true. If he know's something the compiler doesn't, he could unroll some of the loops / order them to benefit caching, but the improvement will likely be minimal.

Alexei Levenkov Over a year ago

+1. Direct iteration over array (with correct ranges :)) is definitely most efficient way in C#. (Usefulness of 456M items is questionable, but it is not what was asked in the question).

N_A Over a year ago

Another point: in C# if you iterate over the array from 0 to array.length(as is done in the example in the question, more or less), the jitter will remove the bounds checks on the indexing, resulting in a performance improvement of about a factor of 3 over keeping the bounds checks in.

Sergey Kalinichenko Over a year ago

@sybkar In situations like that the limiting factor is usually the "payload" of the algorithm, not the loops themselves (with the exception of, perhaps, the Floyd-Warshall's algorithm). So I decided not to touch this topic: if the OP can optimize the number of times he must execute the innermost body, the effect is going to beat unrolling hands-down :)

sybkar Over a year ago

@dasblinkenlight Yup, as I said, likely minimal. It may be more of an issue if the array's items are large, but this is all getting into micro optimization...

|

Collectives™ on Stack Overflow

C# - Most efficient way to iterate through multiple arrays/list

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related