optimization

hey guys,

I have the following code :

for (int =0;i<a.size();i++)
{
if(key==a[i])
printf("found");break;
}


can anyone tell how can achieve the same without checking i with the condition lessthan a.size()(which is the size of the array a).

thanx
krithi

Put your question more into context. If that runs too slow, you could just check the size of the string outside the loop once and assign it to a variable. Then just check if I is below the variable. Other than a possible speed problem, I see nothing wrong with your code. Add a pice of outside code if it would help with answering your question.

Code:

---

for (int i = 0; i < a.size(); ++i)
{
    if (key==a[i]) {
        printf("found"); break;
    }
}

---

Draco: That shouldn't make a difference, as the compiler would calculate a.size() only once.

There's no real way to directly optimize your code. You're obviously searching through something, so the only route for optimization is to perhaps choose a better search algorithm, perhaps one that searches only the areas of the array that could contain key (thus, a would have to be sorted).

Quote:

---

Originally posted by rmullen3

Draco: That shouldn't make a difference, as the compiler would calculate a.size() only once.

---

Not necissarily. In many cases the compiler can't know that the size function will be returning the same value anytime.

As rmullen3 pointed out a.size() is only calculated once. It can be faster to write for loops like this:

Example

Code:

---


int i = a.size();

for(;i--;) {
  if(key == a[i]) {
    printf("found");
    break;
  }
}

---

Nonetheless, the most optimized (at least speed wise) would be to write your loop like this:

Example

Code:

---


const char *cpy = a.c_str();

for(;*cpy;cpy++) {
  if(key == *cpy) {
    printf("found");
    break;
  }
}

---

Like all loops that scan for something sometimes it is faster to go backwards through a loop then forwards. That is why you should put some thought into which way you loop through arrays.

By the way, this is the C board. You really should post C++ questions there.

Quote:

---

Originally posted by master5001
As rmullen3 pointed out a.size() is only calculated once..

---

Again, it is very likely that it will be called every time

Well it may be called every time, but for a loop this small the compiler will typically optimize the loop so it is only called once. Though keep in mind I am only making assumptions from what I've observed my compilers to do in this situation. A for loop could be broken down into this:

Code:

---


int i = 0;

label1:
if(i < a.size()) {
  // do stuff
  goto label1;
}

---

However, compilers are geared towards optimizing loops so it would most likely move a.size() into one register and compare the regiser to i (which may also be a register). That is why in both my examples I didn't compare it to a.size().

Quote:

---

Originally posted by master5001
Well it may be called every time, but for a loop this small the compiler will typically optimize the loop so it is only called once. Though keep in mind I am only making assumptions from what I've observed my compilers to do in this situation. A for loop could be broken down into this:

Code:

---


int i = 0;

label1:
if(i < a.size()) {
  // do stuff
  goto label1;
}

---

However, compilers are geared towards optimizing loops so it would most likely move a.size() into one register and compare the regiser to i (which may also be a register). That is why in both my examples I didn't compare it to a.size().

---

In most cases that's not a possibility. The only time it could possibly do that is if the function is in the same module as the for loop.

Why?

Because the optimization you are describing is a compile-time optimization. In order to know enough to make that optimization, the for loop would have to have direct knowledge of the implementation of that function.

If the implementation for the size member function is in another source file (which it usually would be), then the for loop wouldn't be able to see the implementation at compile time. It would have to make the assumption that the results would vary (hence it would have to call the funciton for every single iteration).

In this case, the person writing the code can do his own optimization (because here he knows more than the compiler) and explicitly store the result of the size function and use that as a comparison in the for loop.

Your point is valid. Though it does make sense I do believe in this example it could still be optimized in the way I described above, since std::string::size() is an inline function that is does not use any volatile variables it may (I'm not 100% sure on this one) be calculated only once. Then again I never personally take guesses at what my compiler does. I never write loops like that (even in my examples). I'll have to agree with Polymorphic though, a.size() may not always be calculated once, though looking at the loop I would bet that it is, there is a possibility it is not.

Sorry, when I posted I was thinking of the evaluation of an expression, not the calling of function. So, it may be a good idea to get the size into a variable first.