A problem about strlen && printf



(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
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
@MiiiNipaa
But if my code is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
    }

it's fast。
printf is slow as hell. You commented it and get overral increase in speed.
@MiiNiPaa,
But I use puts or cout is same as printf
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
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
You can use stringstream to buffer your output and then pass it to cout.
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
@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.
I'm guessing you didn't compile these with optimizations. I took the liberty of putting together a similar experiment without timing output functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <string>
#include <sstream>
#include <chrono>
#include <algorithm>
#include <string>
#include <random>

typedef void(*testFunc)();

void test1() ;
void test2() ;
void test3() ;
void test4() ;

testFunc tests[] =
{
    test1, test2, test3, test4
};

const unsigned numTests = sizeof(tests) / sizeof(tests[0]) ;

const unsigned size = 2000000 ; 

int ans[size] = {} ;
char a[size] = {} ;

std::string str ;

void populate_strings() ;

int main()
{
    using std::chrono::duration_cast ;
    using std::chrono::milliseconds ;

    populate_strings() ;

    for ( unsigned i=0; i<numTests; ++i )
    {
        std::chrono::high_resolution_clock hrc ;
        auto begin = hrc.now() ;
        
        const unsigned iterations = 2000 ;
        for ( unsigned j=0; j< iterations; ++j )
            tests[i]() ;

        auto end = hrc.now() ;

        std::cout << "Test " << i+1 << ": " 
            << duration_cast<milliseconds>((end-begin)).count() / static_cast<double>(iterations) 
            << " ms\n" ;
    }
}

void populate_strings()
{
    std::mt19937 rng((std::random_device()())); 
    std::uniform_int_distribution<int> alpha_range('a', 'z') ;

    for ( unsigned i=0 ; i < size-1; ++i )
        a[i] = alpha_range(rng) ;

    str = a ;
}


void test1()
{
    int l=1,r=std::strlen(a);
    
    for (unsigned i=0;i<std::strlen(a);i++) 
        if (a[i]=='l')
            ans[r--] = i+1;
        else
            ans[l++] = i+1;
}

void test2()
{
    unsigned len = std::strlen(a) ;

    int l=1,r=len;
    
    for (unsigned i=0;i<len;i++) 
        if (a[i]=='l')
            ans[r--] = i+1;
        else
            ans[l++] = i+1;
}

void test3()
{
    int l=1,r= str.size();
    
    for (unsigned i=0;i<str.size();i++) 
        if (str[i]=='l')
            ans[r--] = i+1;
        else
            ans[l++] = i+1;
}

void test4()
{
    int l=1,r=str.size();
    unsigned i ;

    for ( auto ch : str )
        if ( ch == 'l' )
            ans[r--] = ++i;
        else
            ans[l++] = ++i;
}


With somewhat different results.

Test 1: 5.304 ms
Test 2: 5.304 ms
Test 3: 4.157 ms
Test 4: 3.385 ms


Huzzah, range based for loop!
@cire
I test the code in my computer and know that you are right.
And my statistics are from a website named coderforces,
Topic archived. No new replies allowed.