Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I was interested to know which words of the English language, when spelled backwards, are still valid words (e.g. "drawer", which when spelled backwards is "reward"), so I wrote a small program to go through a dictionary text file to search for them.

I don't know if there's a word to describe them, but because of the similarity to palindromes, I decided to call them pseudo-palindromes.

So, I wanted to know:

  • Is there a more efficient way to search for pseudo-palindromes? I believe my approach has \$O(n*log(n))\$ complexity. Is that right?
  • Are there ways to make my code more readable and/or maintainable?
  • Are there any other tips to enhance the performance or style?

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

// Load a dictionary file (line-separated strings) into a vector<string> and return the vector.
vector<string> loadFromDic(string filename)
{
  ifstream file;
  vector<string> strings;
  string aux;

  file.open(filename.c_str());
  while(!file.eof())
  {
    getline(file,aux);
    strings.push_back(aux);
  }

  return strings;
}


int main()
{
  // Load the dictionary from memory.
  vector<string> strings = loadFromDic("english_dic.txt");

  // Sort it alphabetically.
  sort(strings.begin(),strings.end());

  vector<string> ok_strings; // Will hold the strings which passed the test.
  string aux;
  vector<string>::iterator it;

  // For each string: 
  for(it = strings.begin() ; it != strings.end() ; it++)
  {
    // Reverse the string.
    aux = *it;
    reverse(aux.begin(),aux.end());

    // If the reversed string is a word contained in the dictionary, add it to the list.
    if(binary_search(strings.begin() , strings.end() , aux))
    {
      ok_strings.push_back(*it);
    }
  }

  // Sort ok_strings based on string length first and then alphabetically.
  sort
  (ok_strings.begin() , ok_strings.end() , 
    [](string a, string b)->bool
    {
      if(a.size() == b.size())
    return a < b;
      return a.size() < b.size();
    }
  );  

  // Display the strings which passed the test.
  for(it = ok_strings.begin() ; it != ok_strings.end() ; it++)
  {
    cout << *it << endl;
  }

  return 0;
}

The dictionary file I'm using is inside this .zip (renamed the US.dic -> english_dic.txt)

share|improve this question
2  
So you are looking for semordnilaps? –  Lucius Jun 7 at 10:00
1  
You nowhere specify the encoding of your file, which just happens to work because you're using this under windows.. or the file really only contains ASCII which is a naïve assumption even for english. –  Voo Jun 7 at 10:33

3 Answers 3

up vote 11 down vote accepted

I'd try to break some habits, and make others in their places.

  1. One habit to break is using while (!file.eof()) -- it's nearly always a problem (including this time).

  2. In its place, I'd consider initializing the array of input strings from a pair of std::istream_iterators.

  3. I'd try to form the habit of creating fstream objects initialized with the name of the name of the file you want to read/write, rather than creating an uninitialized object, then using open open the file afterwards.

  4. I'd also try to get in the habit of using better/more efficient data structures when possible. As pointed out below, in this case it doesn't make a big difference, but it does help a little, and it actually simplifies the code--a clear win.

  5. Finally, get in the habit of using standard algorithms where they apply. In this case, I think a non-standard algorithm really makes more sense--a transform_if, which I end up using quite a bit, as a matter of fact.

Putting these together, we could end up with something on this order:

#include <iostream>
#include <unordered_set>
#include <string>
#include <iterator>
#include <fstream>
#include <algorithm>

template <class InIt, class OutIt, class F, class P>
void transform_if(InIt b, InIt e, OutIt o, P p, F f) { 
    while (b != e) { 
        auto v = f(*b);
        if (p(v))
            *o++ = v;
        ++b;
    }
}

int main(){ 
    std::ifstream in("us.dic");
    std::unordered_set<std::string> words{
        std::istream_iterator<std::string>(in), 
        std::istream_iterator<std::string>()};

    std::vector<std::string> reversed;
    transform_if(words.begin(), words.end(), 
        std::back_inserter(reversed),
        [&](std::string const &s) { return words.find(s) != words.end(); },
        [](std::string const &s) { return std::string(s.rbegin(), s.rend()); });

    std::sort(reversed.begin(), reversed.end(),
        [](std::string const &a, std::string const &b) {
            if (a.length() < b.length())
                return true;
            return a < b;
        });
    for (auto const &s : reversed)
        std::cout << s << "\n";
}

I haven't tried to move much out of main, because in this case we've already reduced main to only 6 statements (though, admittedly, some of those are fairly long).

A few other miscellaneous points:

  1. I'd prefer to see #include directives formatted with a space before the header name (as I've done in my code above).
  2. Using an unordered_set helps the run time somewhat, but not drastically--on my machine, the CPU time is reduced from ~.35 seconds to ~.24 seconds. That's clearly faster, but not immensely so.
  3. Another possibility to consider would be to put the inputs into a sorted vector, but use an interpolation search instead of a binary search to find the pseudo-palindromes.
share|improve this answer
    
Perhaps this would benefit from having using namespace std in main()? –  Jamal Jun 7 at 5:15
    
You certainly could do that. Whether it'd be a benefit--I'm not sure. I'm accustomed enough to std:: that it doesn't bother me, but others might see it differently. –  Jerry Coffin Jun 7 at 5:21
    
I wasn't sure either, hence why "perhaps" was in italics. :-) –  Jamal Jun 7 at 5:24
    
I am not familiar with the transform_if(). Google(ing) it gives a couple of results which all seem to contradict each other (or be personal implementations). Can you explain it or provide a reference link (or C++ standard doc number (ie n3797) so I can download it). –  Loki Astari Jun 7 at 18:44
    
@LokiAstari: The implementation I'm using is in the answer (i.e., this is a personal implementation). –  Jerry Coffin Jun 7 at 18:46

Preparing the vector of \$n\$ words takes \$O(n \log n)\$ time, because that is how long it takes to sort the words. Thereafter, each lookup takes \$O(\log n)\$ time for a binary search. (The times also scale according to the average length of the words, which we can probably disregard.)

If you used a instead (such as a std::unordered_set), then the data structure would take \$O(n)\$ time to prepare, and each lookup would take \$O(1)\$ time.

share|improve this answer
    
HUGE improvement, great idea! –  JLagana Jun 7 at 4:27
    
I believe you're referring to std::unordered_map, which uses a hash table. std::map uses a binary search tree. –  Jamal Jun 7 at 4:30
    
@Jamal Thanks. Incorporated your correction in Rev 2. –  200_success Jun 7 at 5:06
    
That was my first thought. I don't know the standard structures available to C++ programmers, but I know that for Java programmers, between HashSet and LinkedHashSet there's almost no need for a TreeSet (I just... just don't see myself needing to iterate in sort order - if I do, sort order usually came from the database anyway, so I just order by there and it leverages an index and the sort cost is never incurred.) Just my experience, not saying they aren't useful in some cases, but I never seem to actually run into those cases. –  corsiKa Jun 8 at 6:02
  • For your headers:

    #include<iostream>
    #include<fstream>
    #include<vector>
    #include<algorithm>
    

    As @Jerry Coffin has mentioned, it's a little more readable to have a space after an #include. You could also organize them, such as alphabetically. This will help keep better track of them.

    #include <algorithm>
    #include <fstream>
    #include <iostream>
    #include <vector>
    
  • You should have the program terminate if the file cannot be opened (either return EXIT_FAILURE from main() or call exit(1) elsewhere). Otherwise, if loadFromDic() ends up returning just the declared vector of strings (nothing in it), there'd be no reason for the program to continue.

  • Under C++11, std::fstream::open() can now take an std::string argument.

    You could just pass the filename string itself:

    file.open(filename);
    

    Here is a bit of background info on this.

  • Use more functions so that main() doesn't have to do so much. You should just have it load the strings from a file and call the functions. You can have additional ones for each sub-routine in main(), such as sorting and displaying the string. That'll also cut down on all the comments, which will help keep the code cleaner.

  • Since you're using C++11, you don't need to declare vector<string>::iterator it; just use a range-based for-loop instead. You could also use auto with this loop.

    for (auto& iter : container)
    {
        std::cout << iter;
    }
    
share|improve this answer
    
Great ideas! I'd like to ask a follow-up question, if that's alright: regarding suggestion 2, I'm always unsure about when to encapsulate a block of code into a function to reduce clutter. For instance, the choice to put all the "file reading" lines into one function and call that at main() was obvious, because there were so many lines within the same context, but at the same time arbitrary, since my definition of "many lines" is vague. Is there any general guideline to follow here? What stops me from doing something like main(){findPseudoPalindromes(); printPseudoPalindromes(); return 0;} ? –  JLagana Jun 7 at 4:14
    
@h3now: The general guideline is just to encapsulate into functions as much as possible. Now, if the file-loading code was much shorter, you could just have that in main() (you could just return 1 if the file failed to open). The idea is to keep code contained so that if you need to fix something in particular, you know where it is. If you were to expand main(), it would become harder to follow. –  Jamal Jun 7 at 4:22
    
Not as precise as I would like to, but I think I got it. I'll experiment more on the subject... thank you! –  JLagana Jun 7 at 4:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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