CODEWITHSUNDEEP
c#performance
NominSim
NominSim

Reputation: 8511

Is there a more efficient method for omitting for loop instances

If I have a standard for loop is there a more efficient way to omit certain occurances?

For example:

A:

        for (int i = 0; i < n; i++)
        {
            if (i != n / 2 && i != n / 3 && i != n / 4)
            {
                val += DoWork(i);
            }
            else
            {
                continue;
            }
        }

B:

        for (int i = 0; i < n / 4; i++)
        {
            val += DoWork(i); ;
        }
        for (int i = n / 4 + 1; i < n / 3; i++)
        {
            val += DoWork(i);
        }
        for (int i = n / 3 + 1; i < n / 2; i++)
        {
            val += DoWork(i);
        }
        for (int i = n / 2 + 1; i < n; i++)
        {
            val += DoWork(i);
        }

C:

        for (int i = 0; i < n; i++)
        {
            if (i == n / 2 || i == n / 3 || i == n / 4)
            {
                continue;
            }
            else
            {
                val += DoWork(i);
            }
        }

For n = int.MaxValue the results were as follows: A Results: 57498 milliseconds. B Results: 42204 milliseconds. C Results: 57643 milliseconds.

EDIT BASED ON @Churk 's answer. I added another test case method D as follows:

D:

        for (int i = 0; i < n; i =  (i != n / 2 -1 && i != n / 3 -1  && i != n / 4-1) ? i+1: i+2)
        {
            val += DoWork(i);
        }

and got the following results:

A Results: 56355 milliseconds. B Results: 40612 milliseconds. C Results: 56214 milliseconds. D Results: 51810 milliseconds.

Edit2: After pre-calculating values for n/2 n/3 and n/4 outside the loop got:

A Results: 50873 milliseconds. B Results: 39514 milliseconds. C Results: 51167 milliseconds. D Results: 42808 milliseconds.

The D loop seems to be close again to the "unrolling" of B, with A and C still taking significantly more time.

Which are about what I expected, as far as comparisons between each of the methods.

My question is, is there a more efficient way of doing this?

Upvotes: 1

Views: 173

Answers (7)

Hector Correa
Hector Correa

Reputation: 26690

You could calculate the values outside of the loop and then just skip them: 

  int skip1 = n/2;
  int skip2 = n/3;
  int skip3 = n/4;
  for (int i = 0; i < n; i++)
  {
      if (i != skip1 && i != skip2 && i != skip3)
      {
         val += DoWork(i);
      }
  }

Not sure if this will save enough milliseconds to be worthwhile, though.

Update: I've just noticed that @surfen suggested this in the comments.

Upvotes: 0

Mike Dunlavey
Mike Dunlavey

Reputation: 40669

First, just pause it a few times during that 40-60 seconds, so you get a fair idea what fraction of time is in DoWork. If you could even make your looping take no time at all, you'd still have to spend that part.

Now look at your comparisons. Each one is asking a question. If the answer to a question is almost always True or almost always False, it is an opportunity to get speedup. (All the log(n) and n*log(n) algorithms work by making their decision points more like fair coins.)

So you can see why your B is faster. It is asking fewer questions per loop, on average. You can make it even faster, by unrolling the loops (asking the questions even less often).

(I know, I know, compilers can unroll loops. Well, maybe. Do it yourself and you won't have to bet on it.)

Upvotes: 1

surfen
surfen

Reputation: 4692

I wouldn't bother complicating code with such modifications (as many have already commented on your question)

Instead, you might want to run your DoWork simultanuously in multiple threads using Pararell.ForEach. This would have a much larger impact on performance, if your DoWork() does anything.

Upvotes: -1

Yochai Timmer
Yochai Timmer

Reputation: 49251

You can count operations...

Option A:
n checks on i in the for loop and then 3 checks on each i that isn't that value... so there's 4n operations just for the checks.

option B:
You're just looping through intervals, so you're doing n-3 operations.

option C:
Same as option A, 4n operations.

Upvotes: -1

C.Evenhuis
C.Evenhuis

Reputation: 26446

If DoWork() isn't the bottleneck, it is a small enough method to embed into the loop, so you won't need the call which costs time by itself. If DoWork() does most of the work though, you're the one wasting time :)

Upvotes: -1

aKzenT
aKzenT

Reputation: 7895

It depends a bit on the context. One possiblitiy in many scenarios is to cheat. So instead of omitting the numbers, just include them and later reverse the result from the numbers you didn't want:

    for (int i = 0; i < n; i++) 
    { 
        val += DoWork(i); 
    } 
    val -= DoWork(i/2);
    val -= DoWork(i/3);
    val -= DoWork(i/4);

The time you save from comparisons might outweigh the results from calculating some numbers twice, depending on how expensive the DoWork operation is.

Upvotes: 3

Churk
Churk

Reputation: 4637

Embed your secondary condition into you for loop

Untested:

for (int i = 0; i < n || (i != n / 2 && i != n / 3 && i != n / 4); i++)
  val += DoWork(i);
}

I think this will work as long as one of those condition is true it will keep going

Upvotes: 2

Related Questions