retuor89's blog

Undone by strlen()
By retuor89, 10 years ago, In English

Greetings !

Another day , another opportunity to thank the brilliant minds out here for teaching me something valuable. I am a novice in competitive programming , as evident from my graph and the kind of mistakes I make. But today was an all new low.

Problem B for Div 2 had pretty simple logic using a Greedy approach. To mention two of my submissions:

7587946 : Timed out on TC 21

7599421 : Accepted.

The only difference b/w the submissions is that earlier,while fetching the character frequencies, I had used strlen() to find the loop boundaries. Yes , it was extremely stupid since the length of the string was already provided in the input. Another classic rookie mistake !! When I ran some tests on my local machine , I could find a 5x increase in the execution times with strlen().

After reading a bit on strlen() , I learnt about it's iterative nature in calculating the length of the string. What I cannot help wonder is the reason for such an implementation. Since strings are stored contiguously in the thread stack, wouldn't it better to simply calculate the total memory occupied by the string. That itself would give its length.

Can anyone shed some light on this?

Thanks!!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

But how would you calculate such a length? In C(++), a C-string (char*) is just a pointer to the beginning of a string. It does not know anything about the end, or what block of memory this string belongs to, etc.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cause strlen works in O(length) time, if you want to iterate with strlen, just do like int len=strlen(s); for(int i=0;i<len;i++)

Atleast I think that strlen is going through string until it finds an \0, but I'm not 100% sure

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes. strlen() just keep going on until \0 is found

    C++ string object holds more things than only a pointer to the front. So string::size() works in O(1) since it already knows where the string ends and only need a simple subtraction.

    → Reply