patterncppMajor
Close to the metal C++ Palindrome Program
Viewed 0 times
closetheprogrammetalpalindrome
Problem
I am attempting to reinvent the wheel by writing my own palindrome checking program in C++, using only basic loops and mathematical operations. I have arrived at a solution, but was wondering if it's the best solution and if it could be improved. I'm doing this primarily as a learning exercise. My code:
I think at the moment I'm doing about 2x the number of loops I need to do, and so wasting CPU time. Also, there may be further optimizations. Any help really appreciated as I really want to understand this stuff properly and contribute to code-bases, rather than just doing everything with other people's higher-level code.
#include // cout
#include // printf
#include
using namespace std;
bool is_palidrome(string inputString) {
int num_to_parse = inputString.size();
/* immediately return on single letter string as all single letter strings are palindromes -- saves CPU time as programme does not need to enter the loop */
if(num_to_parse == 1) {
return true;
}
for(int i=0; num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] == inputString[point_end]) {
continue;
} else if (i == num_to_parse) {
return true;
} else {
return false;
}
}}
int main() {
// Change the value of inputString to test different palindromes
string inputString = "caabaac";
printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome."); // ternary: test condition ? return this if true : return this if false
return 0;
}I think at the moment I'm doing about 2x the number of loops I need to do, and so wasting CPU time. Also, there may be further optimizations. Any help really appreciated as I really want to understand this stuff properly and contribute to code-bases, rather than just doing everything with other people's higher-level code.
Solution
for(int i=0; num_to_parse; i++)wut
Why is
num_to_parse your condition? Then you have if (i == num_to_parse) in there, too? That's odd. I'd rewrite this as:for(int i=0; i < num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] == inputString[point_end]) {
continue;
} else {
return false;
}
}
return true;If you want to simplify that even further, you can just do this:
for(int i=0; i <= num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] != inputString[point_end]) {
return false;
}
}
return true;Take note of the different condition. There are a couple of other simplifying improvements, but they're mentioned in another answer.
While I was writing that, I realized that your indentation is... odd, to say the least. Please don't use things like
}} in code; while there are a few rare cases where it might be OK (nested namespaces that, as is typical, you didn't indent), none of them apply here.using namespace std is a bad idea. Please don't do it.printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome.");This is just... weird. I mean, first of all, you don't have a trailing newline, so it might never output anything at all. In my C IDE, for example, it would, but on my Bash console, it'd definitely look odd (
This is a palindrome.q@my-hostname ~>), if it prints at all. Even ignoring that inconsistency... why do it like that? The ternary just makes it more complicated than it has to be.If you insist on using C functions (more on that later), do this:
if (is_palindrome(inputString)) {
puts("This is a palindrome.");
} else {
puts("Not a palindrome.");
}The C++ equivalent should be fairly straightforward; replace the
puts(...) with std::cout << ... << "\n";, or std::endl in place of "\n" if you want to be paranoid about flushing every single line instead of just ensuring that it's flushed in a few key places (which is what I do in performance-critical stuff, because writing to the console is slow, and until you tell them to, most C++ standard libraries will avoid doing it for as long as is reasonable)Now to talk about that "using C functions" thing. Why are you doing it at all? You have all of C++'s power to bring to bear, but you don't. If you want to write this in C, write it in C -- it'd only be changing, like four lines. Maybe less. Don't use just a tiny part of C++. Or, alternatively, just write C.
With regards to your original concern about speed, you're doing this in O(n) (as far as I can tell), which is the absolute lower limit. You're still iterating over every character, though, so it's not as fast as it could get -- you only need to iterate over half.
Finally, what do you mean by "close to the metal"? This is just C with a tiny sprinkling of C++, which are both high-level languages. Not as high-level as, say, Python, but the definition of a high-level language is that it's abstracted from any one particular machine, which C and C++ are. There's nothing close to the metal here. That would be machine code, or maybe Assembly.
Code Snippets
for(int i=0; num_to_parse; i++)for(int i=0; i < num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] == inputString[point_end]) {
continue;
} else {
return false;
}
}
return true;for(int i=0; i <= num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] != inputString[point_end]) {
return false;
}
}
return true;printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome.");if (is_palindrome(inputString)) {
puts("This is a palindrome.");
} else {
puts("Not a palindrome.");
}Context
StackExchange Code Review Q#161501, answer score: 41
Revisions (0)
No revisions yet.