Char Array Vs Strings

[newbie456]

Ok, So I'm trying to solve a problem which is supposed to run in less than 3.5 seconds.

Using same algorithm, I tried to solve it in two ways

1. Using Strings
// t is the number of test cases
while(t--)
{ string s; int count1=0; int day=0; int count=0;
cin>>s;
int n=s.length();
for(int i=1;i<n-1;i++)
{
if(s[i]=='.'){
if(count>=count1) count1=count;
count=0;
while(s[i]=='.')
{
count++;
i++;
}
if(count>count1) { day++; }
}

}
printf("%d\n",day);
}
--------------------------------------------------------------------------------

2. Using Char Array


while(t--)
{ char arr[1000001]; int day=0; int count1=0; int count=0;
scanf("%s",arr);
for(int i=1;i<strlen(arr);i++)
{
if(arr[i]=='.'){
if(count>count1) count1=count;
count=0;
while(arr[i]=='.')
{
count++;
i++;
}
if(count>count1) day++;
}

}
printf("%d\n",day);
}
--------------------------------------------------------------------------------

The second code runs in 0.34 secs while the first code gives Time Limit Exceeded. Any explanations why this is happening?

Note: It is given in the question that the string of array has to only store two
chars either '#' or '.'

Thanks!

[kbw]

It would help if you formatted your code.

As far as I can tell, the difference is one uses std::string, while the other uses a char array.

You need to show us your command line args ro the compiler. The only difference I can guess at is that std::string::operator[] isn't inlined.

[Peter87]

First of all, make sure to turn on compiler optimizations.

I guess some of the slowness of the first code comes from the dynamic allocations that the string has to do in each iteration. Declare the string s outside the loop and see if that makes a difference.

I noticed the first code uses >= while the second code uses > but I doubt that makes much of a difference, (It really shouldn't with optimizations turned on).

[BarryInPhoenix]

Perhaps arr is not null terminated.

[Stewbond]

There are three main differences:

1. cin>> versus scanf("%s", ). scanf is faster.
2. string s versus char arr[1000001]. This is definitely your issue. Allocating memory on the stack with (char[]) is very fast. String uses the heap and dynamically sizes itself as you add characters which is much slower. The solution is to create your string before your while(t--) loop and to use s.reserve(100001); before entering that while loop.
3. Operator[] which doesn't actually cause much lag.

[newbie456]

@ Stewbond and @Peter87: Thanks a lot, would keep that in my mind from next time. So, I declared string outside the while(t--) loop and used the s.reserve and it ran within the Time limit, just that it still takes 2.98 seconds compared to the 0.34 seconds of char array. Any explanations on that?

@ kbw: This is full code below, I can't understand what do you mean by inlining the [] operator, Please put some more light on that.

---------------------------------------------------------------------------------------------------
#include <iostream>
#include <cmath>
#include <string>

using namespace std;
int main ()
{ string s; int t; scanf("%d",&t);
while(t--)
{ int count1=0; int day=0; int count=0;
cin>>s;
int n=s.length();
for(int i=1;i<n-1;i++)
{
if(s[i]=='.'){
if(count>=count1) count1=count;
count=0;
while(s[i]=='.')
{
count++;
i++;
}
if(count>count1) { day++; }
}

}
printf("%d\n",day);
}
return 0;
}
------------------------------------------------------------------------------------------------

This one stops in 2.98 seconds over all test cases.

[Stewbond]

I'm really not surprised that cin is 10x slower than scanf. There are tons of lines of code behind that object which are not present in C.

Is this a question on codechef? If so, check out some of the other solutions. You'll see that asm is always faster than pascal which is always faster than C which is always faster than C++ which is always faster than Java/C#/etc. That's because there is so much more logic going on in C++ than C. There are so many uses for cin and so many ways that it can be modified. That amazing flexibility comes at a cost.

The disadvantage of lower-level languages is that you generally need to write far more code to get the same high-level task done.

[newbie456]

Yes, This is a codechef question indeed, how'd you figure out? :D
And yes, I did check other submissions and it turns out I reached the same conclusions as you what just said.

Thanks again!