Jan 21, 2013 at 5:54am UTC
(Um,My english is not well) :)
My friend is learning C++ now,and he find a problem that I can't explain why.
The First Code ,it runs more than 2000MS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int ans[2000000];
char a[2000000];
int main()
{
scanf("%s\n" ,a);
int l=1,r=strlen(a);
for (int i=0;i<strlen(a);i++)
if (a[i]=='l' )
ans[r--] = i+1;
else
ans[l++] = i+1;
for (int i=1;i<=strlen(a);i++)
printf("%d\n" ,ans[i]);
return 0;
}
The Second Code,it runs 465MS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int ans[2000000];
char a[2000000];
int size;
int main()
{
scanf("%s" ,a);
int l=1,r=strlen(a);
size = r;
for (int i=0;i<strlen(a);i++)
if (a[i]=='l' ) ans[r--]=i+1;else ans[l++]=i+1;
for (int i=1;i<=size;i++)
printf("%d\n" ,ans[i]);
return 0;
}
The Third Code,it runs more than 2000MS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int ans[2000000];
char a[2000000];
int size;
int main()
{
scanf("%s" ,a);
int l=1,r=strlen(a);
size = r;
for (int i=0;i<size;i++)
if (a[i]=='l' ) ans[r--]=i+1;else ans[l++]=i+1;
for (int i=1;i<=strlen(a);i++)
printf("%d\n" ,ans[i]);
return 0;
}
The Last Code ,it runs 515MS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
int ans[2000000];
string a;
int main()
{
cin >>a;
int l=1,r=a.size();
for (int i=0;i<a.size();i++)
if (a[i]=='l' ) ans[r--]=i+1;else ans[l++]=i+1;
for (int i=1;i<=a.size();i++)
printf("%d\n" ,ans[i]);
return 0;
}
When input string size is 10^5
So , the reason is about second for loop.
And my question is why "strlen" function and print in for loop will make the code so slow?
c++
Last edited on Jan 21, 2013 at 7:23am UTC
Jan 21, 2013 at 6:41am UTC
possible realaization of strlen() function:
1 2 3 4 5 6 7
size_t strlen(char * in)
{
size_t len = 0;
while (in++)
++len;
return len;
}
What happens if you will call it 2000000 times?
Last edited on Jan 21, 2013 at 6:41am UTC
Jan 21, 2013 at 7:50am UTC
printf is slow as hell. You commented it and get overral increase in speed.
Jan 21, 2013 at 8:34am UTC
@MiiNiPaa,
But I use puts or cout is same as printf
Jan 21, 2013 at 8:48am UTC
strlen is an O(n) algorithm, that is it gets slower linearly with the size of the string. And you're calling that thousands of time on a very large string ... it takes time.
You can improve your code by using:
for (size_t i=0, mx = strlen(a); i != mx; ++i)
The length is an unsigned (rather than signed value).
Pre-increment can be faster than post-increment.
I/O is and always has been slow. If you think printf is slow, you should see the C++ iostream equivalent.
Last edited on Jan 21, 2013 at 8:50am UTC
Jan 21, 2013 at 1:02pm UTC
If the length of the string is not changing during the execution of the loop, it would be more efficient to call strlen() just once before the start :
Instead of this
1 2 3 4
for (int i=0;i<strlen(a);i++)
{
// some code which doesn't alter the length of the string...
}
... do this:
1 2 3 4 5
int len = strlen(a);
for (int i=0;i<len;i++)
{
// some code which doesn't alter the length of the string...
}
Edit : Just realised I've said the same thing as kbw in a slightly different way.
Last edited on Jan 21, 2013 at 1:04pm UTC
Jan 21, 2013 at 1:36pm UTC
You can use stringstream to buffer your output and then pass it to cout.
Jan 21, 2013 at 2:06pm UTC
MiiNiPaa wrote:possible realaization of strlen() function:
A small (but significant) error in the code above.
It should look like this:
1 2 3 4 5 6 7
size_t strlen(char * in)
{
size_t len = 0;
while (*in++)
++len;
return len;
}
Notice
*in
at line 4.
Last edited on Jan 21, 2013 at 2:06pm UTC
Jan 21, 2013 at 11:58pm UTC
@all
I know strlen is an O(n) function,and what I said is to show the strange thing in the code.
Compare code 1 with code 2,you will find that if I use strlen(a) in first for-loop it is fast.
Compare code 1 with code 3,you will find that if I use strlen(a) in second for-loop it is slow.
But question is that when we compare code 2 with code 3,the strlen(a) runs same times,but the time is runs is extremely different.
So I think the problem is not about the strlen(a).
And what makes different is something "in" for-loops.
That's my problem.
Jan 22, 2013 at 2:58am UTC
@cire
I test the code in my computer and know that you are right.
And my statistics are from a website named coderforces,