3

In the question link , I first tried it using a character array. This solution exceeded the time limit. 

    char s[100000];
    cin >> s;
    int cnt[26];
    for(int i=0;i<26;++i)
        cnt[i]=0;
    for(int i=0;i<strlen(s);++i)
        cnt[s[i]-'a']++;
    int count =0;
    for(int i=0;i<26;++i)
        if(cnt[i]>0)
            count++;
    cout << count << endl;

But then I changed the above code to this: 

    string s;
    cin >> s;
    int cnt[26];
    for(int i=0;i<26;++i)
        cnt[i]=0;
    for(int i=0;i<s.length();++i)
        cnt[s.at(i)-'a']++;
    int count =0;
    for(int i=0;i<26;++i)
        if(cnt[i]>0)
            count++;
    cout << count << endl;

And the code passed with ease. And also the first one exceeded the time limit of 1 sec, while the second one passed with time of execution of 0.04 sec. Why is there such a large difference in time of execution?

yobro97
  • 1,125
  • 8
  • 23
  • What is the length of the input? – GMichael Oct 14 '16 at 05:52
  • size of string < 100000 – yobro97 Oct 14 '16 at 05:52
  • save yourself a `for` loop: `int cnt[26] = {0}`. And a bit of time can be saved here: `cnt[s.at(i)-'a']++;` because `at` tests that you haven't overrun the string. You've already guaranteed this with the bounds on the for loop so you can `cnt[s[i]-'a']++;`. There may be some optimizing games the compiler can play with a ranged for loop: `for(char ch: s) cnt[ch-'a']++;`. And if not, the code's a bit cleaner. – user4581301 Oct 14 '16 at 06:01

2 Answers2

4

std::string stores its length separately, so s.size() is an instant operation.

for(int i=0;i<strlen(s);++i) calls strlen(s) on every iteration, and strlen loops through the entire string to the end to find the length of the string. So this innocent looking loop is actually O(n2) complexity.

orlp
  • 112,504
  • 36
  • 218
  • 315
  • But in the question http://stackoverflow.com/questions/38681109/how-is-time-complexity-different , I had asked that whether strlen() is called once or every time in the loop. But then the answer given was that it is called only once....is it not so? – yobro97 Oct 14 '16 at 05:56
  • @yobro97 It depends on how smart the compiler is. It seems that in this case the compiler isn't smart enough. Are you compiling with optimization turned on? – orlp Oct 14 '16 at 05:58
  • @orlp....Actually I have run this program on an online competitive programming environment....so no idea...:( – yobro97 Oct 14 '16 at 05:59
  • 3
    @yobro97: That's not what the answers there say. It says the compiler, under ideal conditions with optimizations turned on, could _potentially_ optimize out the repeated `strlen` calls. There are no guarantees there. It's much better to be explicit about calling `strlen` once, so you're not dependent on the optimizer making a tough call correctly. Since you don't even control optimization settings, you have no way to know if it will even _try_. – ShadowRanger Oct 14 '16 at 06:01
  • its right.....I tried declaring `int n = strlen(s)` as mentioned by @doron and then use `n` instead of `strlen(s)` in the loop, it worked! – yobro97 Oct 14 '16 at 06:05
  • C does not have function purity so there is no guaratee that calling the same function more than once will return the same result. The means that the compiler is never allowed to cache the return value. – doron Oct 14 '16 at 06:57
  • @doron - On the other hand, everyone knows what `strlen` does, even the compiler. And it can optimize on that knowledge. – Bo Persson Oct 14 '16 at 07:35
  • Only if it is a compiler intrinsic and I don't think it is. – doron Oct 14 '16 at 09:41
1

The C strings do not store length explicily, they just have a null atbthe end. So to work out the length you need to iterate over the entire string character by character. 'sid::string::length' on the otherhand just returns the internally stored length.

You can easily speed up the C version though, by caching the length in a variable before the loop and using the cached length in the for statement.

doron
  • 27,972
  • 12
  • 65
  • 103