4
\$\begingroup\$

This is some code that determines if a string of characters is a palindrome or not. My professor says that there is a performance issue with the program, but I can't quite put my finger on it. Can someone find out the 'performance' issue?

Initially, I thought maybe the process is slower as it uses two memory containers, as opposed to simply comparing two halves of a single string.

int main()
{
    char c;
    bool check = true;
    stack<char> cstack;
    queue<char> cqueue;
    cout << "Enter a string and press return." << endl;
    cin.get(c);
    while (c != '\n') {
        cstack.push(c);
        cqueue.push(c);
        cin.get(c);
    }
    while (check && !cqueue.empty()) {
        if (cstack.top() != cqueue.front())
            check = false;
        cstack.pop();
        cqueue.pop();
    }
    if (check)
        cout << "Yes it is!" << endl;
    else
        cout << "No it's not." << endl;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Is there a way to combine stack top/pop and queue front/pop in a single statement? \$\endgroup\$ – dfhwze Jul 7 at 16:14
  • 6
    \$\begingroup\$ As an aside, this is nearly a complete program. Consider giving the full program next time in a similar situation (changing this now is inadvisable). \$\endgroup\$ – Deduplicator Jul 7 at 19:08
11
\$\begingroup\$
  1. While it is not quite definitive, it looks like you use using namespace std;.
    That namespace is not designed for wholesale inclusion, being vast and subject to change at the whim of the implementation, aside from providing what is standardised.
    Read "Why is “using namespace std” considered bad practice?" for more detail.

  2. Synchronizing C++ iostreams with C stdio, as happens by default, is quite expensive. Call std::ios_base::sync_with_stdio(false); to fix that.

  3. You should desist from using std::endl, as spurious manual flushing flushes any pretense at performance down the drain.
    For those rare cases where it is actually necessary for correctness, use std::flush for explicitness.

  4. You assume reading from std::cin always succeeds. That's generally unsupportable, please handle failure gracefully.

  5. You are reading character-by-character. Each and every read has significant overhead, which you could simply avoid by using std::getline(). Using the proper abstraction is also significantly more readable.

  6. You are storing the input twice, once in a std::queue and once in a std::stack. Even only storing it in just one std::deque (the underlying implementation for both) would be a considerable improvement.

  7. Consider encapsulating the test whether the input is a palindrome into its own reusable function, separate from actually getting it.

  8. Testing whether something is a palindrome seems a favorite passtime of many beginners.
    Thus, there are a myriad posts on how to efficiently and elegantly do that in C++, for example "Check if a string is palindrome or two strings are the opposite of each other".
    The important points are avoiding expensive copies, and only comparing each element once.

  9. If you want one of two values, conditional on some expression, consider the conditional operator expr ? true_expr : false_expr. It is designed for that.

  10. return 0; is implicit for main(). Make of that what you will.

\$\endgroup\$
  • \$\begingroup\$ "You should desist from using std::endl, as spurious manual flushing flushes any pretense at performance down the drain." I can't imagine a context in which this would be an issue. If performance is an issue (e.g. printing in a loop), you shouldn't be printing at all. If performance isn't an issue, there's no reason to delay flushing. It could be useful for when debugging a loop, for example. If your program crashes, you know that your log provides an accurate trace of what happened, because all prints were flushed. \$\endgroup\$ – Alexander Jul 8 at 17:49
  • \$\begingroup\$ @Alexander Not printing at all is certainly faster. But not flushing after every line can also help significantly, even be an order of magnitude or more. The error-stream is unbuffered because there complete output until the crash is paramount. \$\endgroup\$ – Deduplicator Jul 8 at 20:19
  • \$\begingroup\$ @Deduplicator I didn't know that about the error stream, good to know. "But not flushing after every line can also help significantly, even be an order of magnitude or more." but still, it doesn't matter. You shouldn't be printing in a tight loop if performance is an issue. Buffering or not, you shouldn't be doing it at all. \$\endgroup\$ – Alexander Jul 8 at 20:33
4
\$\begingroup\$

I see two improvement points in the code.

  1. It is better to use getLine() and store the input in char* instead of reading each char and appending to a stack
  2. It is more than enough to iterate till half of the string as the remaining half is checked in the first half iteration cstack.top() != cqueue.front()
\$\endgroup\$
3
\$\begingroup\$

Initially, I thought maybe the process is slower as it uses two memory containers, as opposed to simply comparing two halves of a single string.

I think you hit on an excellent idea right there. I'd read a line of input into a string, the compare the first half of the string to the second half in reverse order.

  • You can use std::getline to read the string.
  • You can use your_string.size() / 2 to get half the length.
  • You can use your_string.cbegin() to get an iterator to the beginning of the string.
  • You can use your_string.crbegin() to get a reverse iterator to the string (one that iterates through from the end to the beginning).
  • You can use std::mismatch to compare the two halves of the string.
  • As Deduplicator pointed out, you probably want a function that does nothing but check whether a string is a palindrome.

If you wanted to minimize changes to your code, you could just read the string into the deque, then to do the comparison, pop one element from the front, and one element from the back, and compare them. The input was palindromic if and only if all the elements match until the deque has fewer than two elements.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.