CODEWITHSUNDEEP
cfor-loopoptimization
user6824588
user6824588

Reputation: 21

Optimizing a nested loop in C

I have a nested loop to find all possible combinations of numbers between 1 and x in groups of 4, where a < b < c < d.

A method is called as each group is discovered to do a simple equivalency test on the sum of those numbers.

The loop does work and produces expected output (1 set of numbers for this particular x), however it takes 12+ seconds to find this answer and another ~5 to test the remaining possibilities, which is definitely bad, considering the x values are < 1000.

I tried having the outer loop iterate a < x - 3 times, the b loop b < x - 2 times, down to d < x times which didn't make a noticeable difference.

What would be a better approach in changing this loop?

for (a = 1; a < x; a++) {
    for (b = a + 1; b < x; b++) {
        for (c = b + 1; c < x; c++) {
            for (d = c + 1; d < x; d++) {
                check(a, b, c, d);
            }
        }
    }
}

Upvotes: 1

Views: 399

Answers (1)

Oak
Oak

Reputation: 26868

With such a deep level of nesting, any early exit you can introduce - particularly at the outer loops - could net big gains.

For example, you write that check is testing a + b + c + d == x && a * b * c * d == x - so you can compute the intermediate sum and product, and break when you encounter numbers that would make any selection of later numbers impossible.

An example:

for (a = 1; a < x; a++) {
  for (b = a + 1; b < x; b++) {
    int sumAB = a + b;
    if (sumAB + sumAB > x) break;
    int prodAB = a * b;
    if (prodAB * prodAB > x) break;
    for (c = b + 1; c < x; c++) {
      int sumABC = sumAB + c;
      if (sumABC + c > x) break;
      int prodABC = prodAB * c;
      if (prodABC * c > x) break;
      for (d = c + 1; d < x; d++) {
        int sumABCD = sumABC + d;
        if (sumABCD > x) break;
        if (sumABCD != x) continue;
        int prodABCD = prodABC * d;
        if (prodABCD > x) break;
        if (prodABCD != x) continue;
        printf("%d, %d, %d, %d\n", a, b, c, d);
      }
    }
  }
}

This is just an example - you can constrain all the checks here further (e.g. make the first check be sumAB + sumAB + 3 > x). The point is to focus on early exits.

I added a counter for each loop, counting how many times it was entered, and tried your version and my version, with x = 100. My version has orders of magnitude less loop entries:

No early exits: 99, 4851, 156849, 3764376
With early exits: 99, 4851, 1122, 848

Upvotes: 2

Related Questions