0

I was solving a question and was getting constant TLE's, then I searched for the solution online and found the exact code was working flawlessy except there was one difference and that was char array and strings.

Looked up about the performance difference of these two DS but couldn't find anything that of that help.

Char array gives a time of 31ms on an online judge. Meanwhile the string one gives a TLE(2000ms). The maximum characters inputted are of size 131072.

Code snippet of char array :

char s[131073];

int getScore(int l, int r,char curr)
{
    int score = 0;
    for(int i=l; i<r; i++)
        if(s[i]!=curr)
            score++;
        
    return score;
}
 
int dnc(int left, int right, char curr)
{
    if(left == right) return 0;
    if(right == left+1) return s[left]==curr ? 0 : 1;
    int mid = (left+right)/2; 
 
    return min(getScore(left,mid,curr) + dnc(mid,right,curr+1),getScore(mid,right,curr) + dnc(left,mid,curr+1));
}

String code :

int getScore(string s, int l, int r,char curr)
{
    int score = 0;
    for(int i=l; i<r; i++)
        if(s[i]!=curr)
            score++;
        
    return score;
}
 
int dnc(string s, int left, int right, char curr)
{
    if(left == right) return 0;
    if(right == left+1) return s[left]==curr ? 0 : 1;
    int mid = (left+right)/2; 
 
    return min(getScore(s,left,mid,curr) + dnc(s,mid,right,curr+1),getScore(s,mid,right,curr) + dnc(s,left,mid,curr+1));
}

Solution Link: https://codeforces.com/contest/1385/submission/144376401 (TLE) https://codeforces.com/contest/1385/submission/144376593 (AC)

Ranjeet Bansode
  • 41
  • 4
  • 4
    The string version copies the string object every time a function is called. The char array version only copies a pointer to the data. To get better performance with the string version, pass by reference instead. – Karl Knechtel Jan 29 '22 at 04:28
  • Depending on how the input was done and if resize or reserve was not used for the string version I could see it taking more time. Unfortunately that part is missing. – Retired Ninja Jan 29 '22 at 04:30
  • Another way to avoid copying data is to use std::string_view. – Pepijn Kramer Jan 29 '22 at 04:31
  • passing by reference did solved my problem. I didn't knew that it was creating copies, thank you . – Ranjeet Bansode Jan 29 '22 at 05:07
  • @Ranjeet - Perhaps you might want to increase your knowledge at [learncpp.com](https://www.learncpp.com/) rather than using trial-and-error (which never works for C++). – BoP Jan 29 '22 at 09:04
  • @-BoP there are always something's that you miss out no matter how hard you try maybe this was one of these, but thank you for your advice. – Ranjeet Bansode Jan 29 '22 at 18:50

1 Answers1

1

I see that you're passing the string by value. Every time the function is being called, the string is being duplicated. Compare it to the example that's using char array, the array is declared once and being used without copying. Also online judges won't give you TLE for things like using string vs. char arrays.

heothesennoc
  • 541
  • 5
  • 10