padfoot1717's blog

Why is this faster?
By padfoot1717, history, 4 years ago, In English

Friends during the previous contest (656 div-3) for problem-1385D - a-Good String i had submitted this solution 87151676 and it gave TLE, after looking at the model solution in the editorial i changed my normal "string" argument to "const string&" argument in the function that i had written and submitted this solution 87188378 which got easily accepted. Can anyone please explain the reason because of which such huge difference in execution time came just by changing the "string" argument to "const string&" argument"?

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

This might help...
The allocation of the string object's internal buffer is similar to a malloc of a char *, so you should see little or no differences between the two.
Now, if your char * are in truth char[SOME_CONSTANT_SIZE], then you avoid the malloc (and thus, will go faster than a std::string).

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

Same thing happened in my case. Point here to note is that when we pass arrays to functions, they are by default passed by reference, but it is not true for strings, STL containers like vectors, maps, etc. They are passed by value to functions which creates multiple copies and creating copy every time the function is called is time consuming. So, it is recommended to pass them by reference.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

So you should understand two things 1.Pass By Value 2.Pass By Reference So in your 1st solution u are passing it by value which is creating a new object everytime u are calling that function which causes the TLE

but in your second solution u are passing it by reference Which means an alias for the object is passed and Adding the const qualifier to a reference (or a pointer) just says that the code promises not to alter the contents of the object being referenced

So always pass by reference whenever you are passing let's say vectors , strings etc.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Bro, you passed the string as a value which creates a copy of the string each time you call the recursive function that's why you are getting a TLE as verdict. While in the other solution the string is passed as a reference thus the verdict is AC. Whenever you are passing a variable down a function for reading purposes only, I prefer passing it as reference.

PS: I had the same situation as yours.

→ Reply