Questions regarding efficiency

user_13628232 0
Viewed 122

So while working through a course on Udemy over C++ one of the challenges was to check a string to see whether it was a palindrome or not. I completed the task successfully but went about it a different way than the instructor. I understand there are a multitude of ways to complete a task but I am wondering which is more efficient and why? It may seem stupid to be wondering about this while reteaching myself coding but I feel this is something I should be keeping in mind. 

//Instructors code//

# include<iostream>
using namespace std;

/*program for reverse a string and check a string is a palidrome

*/
int main()
{
    string str="MADAM";
    string rev="";
    int len=(int)str.length();
    rev.resize(len);
    for(int i=0, j=len-1; i<len; i++, j--)
    {
        rev[i]=str[j];
    }
    rev[len]='\0';  
    if(str.compare(rev)==0)
        cout<<"palindrome"<<endl;
    else
        cout<<"not a pallindrome"<<endl;
    return 0;
}

My Approach

#include <iostream>
using namespace std;

int main(){
    string str1="test";
//    cout << "Enter a string to check if it is a Palindrome: ";
//    getline(cin,str1);

    string str2;

    string::reverse_iterator it;
    for(it=str1.rbegin(); it!= str1.rend(); it++)
    {
        str2.push_back(*it);

    }
    if(!str1.compare(str2))
        cout << "\nPalindrome";
    else
        cout << "\nNot a Palindrome";
    return 0;
}

Thank you in advance.

c++
3 Answers

In theory the code from your instructor is more efficient, but both examples have issues.

With your instructors code the main issue is the use of 

int len=(int)str.length();

In this example, it is okay because we know the size of the string will fit in a int, but if you were getting a string from an outside source, this could be a problem. A std::string using an unsigned integer type to store the size of the string and that means you can have a string who's size is larger then what can fit in an int. If that were to happen, then code is not going to work correctly.

With your code you a avoid all that, which is great, but you also leave some performance on the table. In theory your code of

for(it=str1.rbegin(); it!= str1.rend(); it++)
{
    str2.push_back(*it);

}

is going to cause str2 to have multiple buffer allocations and copies from the old buffer to the new buffer as it grows. This is a lot of extra work that you don't need to do since you already know how much space you need to allocate. Having

str2.reserve(str1.size() + 1);

before the loop pre-allocates all the space you need so you don't have those potential performance hits.

Then we come to the fact that both of your examples are using a second string. You don't need another string to check for a palindrome. What you can do is just check and see if the first and last characters are the same, and if they are move on to the first+1 and last-1 character and so on until you reach the middle or they don't match. You can do that using a construct like

bool is_palindrome = true;
for (auto start = str.begin(), end = str.end() - 1; 
     start < end && is_palindrome; 
     ++start, --end)
{
    if (*start != *end)
        is_palindrom = false
}
if (is_palindrome)
    std::cout << "palindrome\n";
else
    std::cout << "not a pallindrome\n";
user_43424980

The simplest and most efficient way (no copying required) would be something like this:

inline bool is_palindrome(const std::string& u) {
    return std::equal(u.begin(), std::next(u.begin(), u.length() / 2), u.rbegin());
}
user_136465030

I would say that both are almost the same, but as mentioned in the comments, the line:

str2.push_back(*it);

Is actually very inefficient, since std::string may copy the existing string to a new location in the memory, and then append the next char to the string, which is wasteful.

But I am wondering, why to create the copy in the first place?

It is very simple to run both from start to end, and from end to start to check it out, meaning:


bool is_polindrom(const std::string& str)
{
    for (std::size_t idx = 0, len = str.length(); idx < len / 2; ++idx)
    {
        if (str[idx] != str[len - 1 - idx])
        {
            return false;
        }
    }

    return true;
}

Running the code with:


int main()
{
    const std::string right1 = "MADAM";
    const std::string right2 = "MAAM";
    const std::string wrong1 = "MADAAM";
    const std::string wrong2 = "MEDAM";

    std::cout << "MADAM result is: " << is_polindrom(right1) << std::endl;
    std::cout << "MAAM result is: " << is_polindrom(right2) << std::endl;
    std::cout << "MADAAM result is: " << is_polindrom(wrong1) << std::endl;
    std::cout << "MEDAM result is: " << is_polindrom(wrong2) << std::endl;
}

Will yield:

MADAM result is: 1

MAAM result is: 1

MADAAM result is: 0

MEDAM result is: 0

You don't need extra memory in this case, since it is possible to iterate over a string from the end to the beginning, and you need to run on it exactly once (and notice that I stop when idx >= len / 2 since you don't really need to check each letter twice!).

user_70148370
Related