4
\$\begingroup\$

I didn't know this site existed before now... awesome!

I just made a thread here: https://stackoverflow.com/questions/8511620/c-palindrome-finder-optimization

#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

bool isPal(string);

int main()
{
    vector<string> sVec;
    vector<string> sWords;
    vector<string> sTwoWords1;
    vector<string> sTwoWords2;
    char myfile[256]="/home/Damien/Test.txt";
    ifstream fin;
    string str;
    fin.open(myfile);
    if(!fin){
        cout << "fin failed";
        return 0;
    } 
    while(fin){
        fin >> str;
        sWords.push_back(str);
        if(!fin){
            break;
        }
        if(isPal(str)){
            sVec.push_back(str);
        }
        else{
            getline(fin, str);
        }
    }
    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){ 
        cout << sVec[i] << " is a Palindrome " <<endl;
    } 

    // Test 2 
    for(int i=0; i<sWords.size(); i++)
    {                                         
        for(int j=(i+1); j<sWords.size(); j++){ 
            str = sWords[i]+sWords[j];
            if(isPal(str)){
                sTwoWords1.push_back(sWords[i]);
                sTwoWords2.push_back(sWords[j]);
            }
        }
    }
    fin.close();
    for(int i=0; i<sTwoWords1.size();i++){ 
        cout << sTwoWords1[i] << " and " << sTwoWords2[i] << " are palindromic. \n";
    } 
    return 0;
}
bool isPal(string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

About optimizing some code, assuming that I take the revision to my isPal function, what else can I do to optimize the hell out of my code?

Thanks a lot for any / all recommendations!

Wordfile: http://www.filedropper.com/ospd3

\$\endgroup\$
4
\$\begingroup\$

Reading a file:

while(fin){ 

    fin >> str; 
    sWords.push_back(str); 
    if(!fin){ 
        break; 
    } 

You push the value str before checking it worked. It should be:

while(fin)
{ 
    fin >> str; 
    if(!fin){ 
        break; 
    } 
    sWords.push_back(str); 

Or even better would be:

while(fin >> str)
{    
    sWords.push_back(str); 

Why are you doing this:

    else{
        getline(fin, str);
    }

Mixing operator >> and getline() makes the code hard to read.
Either use all operator >> or use getline() to get a line at a time then parse the line internally.

Note:: operator>> will ignore the '\n' at the end of the line and work. So if your file is a list of words one per line there is no need to use getline(). If on the other hand your file is a lot of text and you only want the first word on each line then you need to use getline().

Method 1: Use operator>>

 // If your input file has one word per line (or you want to use all words)
 while(file >> word)
 {
      // Do stuff
 }

Method 1: Use getline()

 // If your input file contains lots of words
 // But you only want to use the first word on each line
 while(std::getline(file, line))
 {
     std::stringstream  linestream(line);
     linestream >> word;

     // Do stuff
 }

You seem to reversing the line just to print it:

reverse(sVec.begin(), sVec.end());                          
for(int i =0; i < sVec.size(); i++){                                
    cout << sVec[i] << " is a Palindrome " <<endl;                                  
}                                                                                           

Rather than reversing the array, just iterate it in reverse order:

for(std::vector<std::string>::const_iterator& loop = sVec.rbegin(); loop != sVec.rend(); ++ loop)
{                               
    cout << (*loop) << " is a Palindrome " <<endl;                                  
}                                                                                           

Note on efficiency:

Using push_back() on an vector can be in-effecient if you are pushing a lot of data. As evertime the vector runs out of space it must allocate more memory and copy the string to the new buffer. You help by pre-allocting space.

sVec.reserve(1000); // Guess at the size
                    // Note when the vector runs out of space it will approximately
                    // double its internal buffer.
\$\endgroup\$
  • \$\begingroup\$ Whoops, I actually parsed two different revisions of my code, thank you very much for bringing this to my attention. I was actually using getline(fin, str) as my while statement but then I changed it to fin >> for a different test I was running. Thank you so much for pointing those errors out. \$\endgroup\$ – HunderingThooves Dec 14 '11 at 21:49
3
\$\begingroup\$
#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm> 

You forgot to #include <string>.

using namespace std;

Although this might be acceptable in books and on this site to shorten lines, don't use using namespace std in real code.

    vector<string> sVec;
    vector<string> sWords;
    vector<string> sTwoWords1;
    vector<string> sTwoWords2;
    char myfile[256]="/home/Damien/Test.txt";
    ifstream fin;
    string str;

This is an outdated style. Even in C, your variabled don't have to be declared at the top anymore. Declare each variable on the line it's initialized.

    char myfile[256]="/home/Damien/Test.txt";

Don't use char arrays, use std::string (or in rare cases: std::vector<char>).

    ifstream fin;
    fin.open(myfile);

Why two lines where one would be enough, and why using open()? Replace it with:

    std::ifstream fin(myfile.c_str());

As myfile should be a std::string.

    while(fin){
        fin >> str;
        sWords.push_back(str);

The other answer has already corrected the bug in this statement.

    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){ 

Use iterators to loop over a container. In this case, use reverse iterators and you won't even need to call reverse().

    fin.close();

The destructor will close it anyway. Is there any reason to explicitly close it at this point? If there was any, just make sure that the life-time of fin ends at this point, e.g. by making a separate function of reading all input. Your main() is way too long anyway.

            str = sWords[i]+sWords[j];
            if(isPal(str)){

Bug! "aab" and "aa" will turn out to be a palindrome pair, as "aabaa" is a palindrome.

bool isPal(string& testing) {

That should be a const reference.

bool isPal(string);
....
bool isPal(string& testing) {

Those don't match.

    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());

Cool! Finally some real C++ code! Even the std:: is present!

\$\endgroup\$
  • \$\begingroup\$ Ouch, brutal answer. \$\endgroup\$ – HunderingThooves Dec 15 '11 at 10:22

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.