Software optimization

Hey, i have writen a spell corrector class. But now i wanted it to be optimized/reviewed so that i can learn from my errors. Readability, performance, style, every suggestions is worths now:

Code:

---

/*
 * SpellChecker.h
 *
 * Copyright  (C)  2007  Felipe Farinon <[email protected]>
 *
 * Version: 1.0
 * Author: Felipe Farinon <[email protected]>
 * Maintainer: Felipe Farinon <[email protected]>
 * URL: http://scarvenger.wordpress.com/
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Commentary:
 *
 * See http://scarvenger.wordpress.com/.
 *
 * Code:
 */

#ifndef _SPELLCHEKER_H_
#define _SPELLCHEKER_H_

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

#include <boost/foreach.hpp>

using namespace std;

typedef map<string, int> Dictionary;
typedef pair<string, int> Pair;
typedef vector<string> Vector;

bool max(const Pair& left, const Pair& right)
{
        return left.second < right.second;
}

class SpellChecker
{
private:
        static const char alphabet[];
        Dictionary dictionary;

        void edits(string& word, Vector& result)
        {
                for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i)                  + word.substr(i + 1)); //deletions
                for (string::size_type i = 0;i < word.size() - 1;i++) result.push_back(word.substr(0, i) + word[i+1] + word.substr(i + 2)); //transposition

                for (char j = 'a';j <= 'z';++j)
                {
                        for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i) + j + word.substr(i + 1)); //alterations
                        for (string::size_type i = 0;i < word.size() + 1;i++) result.push_back(word.substr(0, i) + j + word.substr(i)    ); //insertion
                }
        }

        void known(Vector& results, Dictionary& candidates)
        {
                Dictionary::iterator end = dictionary.end();
                for (unsigned int i = 0;i < results.size();i++)
                {
                        Dictionary::iterator value = dictionary.find(results[i]);
               
                        if (value != end) candidates[value->first] = value->second;
                }
        }

        void stringToLower(string& text)
        {
                int lenght = text.size();
                for (int i = 0;i < lenght;i++)
                {
                        text[i] = tolower(text[i]);
                }
        }

public:
        bool load(const char* filename)
        {
                ifstream file(filename);
                char* data;
       
                file.seekg(0, ios_base::end);
                int lenght = file.tellg();
                file.seekg(0, ios_base::beg);

                data = new char[lenght+1];

                file.read(data, lenght);

                string line(data);

                delete [] data;
       
                stringToLower(line);

                string::size_type position = 0;
                while ((position = line.find_first_of(alphabet, position)) != string::npos)
                {
                        string::size_type endPosition = line.find_first_not_of(alphabet, position);

                        dictionary[line.substr(position, endPosition - position)]++;

                        position = endPosition;
                }

                return true;
        }

        string check(string word)
        {
                Vector result;
                Dictionary candidates;

                if (dictionary.find(word) != dictionary.end()) { return word; }

                edits(word, result);
                known(result, candidates);

                if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), max)->first; }

                for (unsigned int i = 0;i < result.size();i++)
                {
                        Vector subResult;
                        edits(result[i], subResult);
                        known(subResult, candidates);
                }

                if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), max)->first; }

                return "";
        }
};

const char SpellChecker::alphabet[] = "abcdefghijklmnopqrstuvwxyz";


#endif

---

I didn't actually look at the algorithms or techniques you used to solve the problems, but these are just a few comment about the style:

• I don't like the global typedefs. Dictionary is an ok name, but the names Pair and Vector are too generic to describe what the type actually is.
  
• >> data = new char[lenght+1];
  I prefer to use vector for this. In your code, it probably won't end up mattering, but using vector is safer because you won't have a memory leak no matter what and you don't have to worry about a memory leak. For example, what if you want to exit the function early if read() fails? You have to remember to delete [] data. If data was a vector, you wouldn't have to worry about it.
  
• You might as well use transform for your toLower function.
  
• I'd have load take a string. Then just call c_str() from the string. Your other functions use string, so it's best to keep a consistent interface.
  
• Your max function is oddly named. It is meant to sort pairs by the second value. Perhaps SortBySecond or something like that would make more sense?

using namespace std;

NEVER do this in a header file!
Otherwise you force everyone who uses your header file to import the entire std namespace whether they want to or not.

If you want to use a using statement, keep them in .cpp files AFTER all your #include statements.

Also, I don't know if you left out comments to shorten the post, but I think it's a good idea to always document your functions thoroughly so other people reading it know how/what it's supposed to do, and so you'll know 6 months from now when you look at your code again and scratch your head.
Here's an example of one of my functions where I use Doxygen style comments:

Code:

---

        /** This assignment operator copies the pointer held by rhs to this object, and also
        *  transfers ownership from rhs to this object by setting rhs to NULL.
        *
        *  Any existing pointer held by this object will be deleted before assigning the rhs
        *  pointer to this object.
        *
        *  @param rhs [IN] - This is a reference to another AutoPtr object which will be
        *                        copied into this object.  rhs will be set to NULL.
        *
        *  @return AutoPtr& - It will return a reference to this object (i.e.  *this).
        */
        AutoPtr<T_Type, T_Deletor>& operator=( AutoPtr<T_Type, T_Deletor>&  rhs )        // throw()
        {
                // Make sure we aren't assigning to ourself.
                if ( this != &rhs )
                {
                        // If the pointers aren't identical and our pointer isn't NULL, delete our pointer.
                        if ( m_Ptr != rhs.m_Ptr )
                        {
                                if ( m_Ptr != NULL )
                                {
                                        m_Deletor( m_Ptr );
                                }
                        }

                        // Copy the pointer and release rhs from ownership of the pointer.
                        m_Ptr = rhs.release();
                }

                return *this;
        }

---

Method bodies, particularly such large ones belong in a separate C++ file. So should non inline functions like max. In this case you can alternately just put the key word inline before the function.

You misspelled length as lenght.

Don't make your load function hard-coded to return true. It should either be able to return something different when it fails or it should throw an exception, in which case there's no point in returning anything upon success, as the lack of an exception being thrown says that it succeeded.

Simply checking spelling only involves determining if a word exists in the dictionary. (A trivial task once you've loaded the file in to a std::set).
You seem to be attempting to do spelling suggesting as well. However you've used a rather simplistic technique that will only catch pretty basic errors. Real spelling suggestors are much more advanced. They would also rate certain kinds of error as more likely and hence can provide more likely suggestions. They likely work very differently too.
You should probably read up on Minimum Edit Distance.

Quote:

---

Simply checking spelling only involves determining if a word exists in the dictionary. (A trivial task once you've loaded the file in to a std::set).
You seem to be attempting to do spelling suggesting as well. However you've used a rather simplistic technique that will only catch pretty basic errors. Real spelling suggestors are much more advanced. They would also rate certain kinds of error as more likely and hence can provide more likely suggestions. They likely work very differently too.
You should probably read up on Minimum Edit Distance.

---

My objective in the beggining is just to write a simple, small and fast spell corrector, but in the next days i will try to improve it, your reading will be very usefull to me, thank you.

Ok, have reviewed all suggestions and I thank you all, heres the result so far:

SpellCorrector.h

Code:

---

#ifndef _SPELLCORRECTOR_H_
#define _SPELLCORRECTOR_H_

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

typedef std::map<std::string, int> Dictionary;
typedef std::pair<std::string, int> Pair;
typedef std::vector<std::string> Vector;

class SpellCorrector
{
private:
        static const char alphabet[];
        Dictionary dictionary;

        void edits(std::string& word, Vector& result);
        void known(Vector& results, Dictionary& candidates);

public:
        void load(std::string filename);
        std::string correct(std::string word);
};

#endif

---

SpellCorrector.cpp

Code:

---

#include "SpellCorrector.h"

using namespace std;

const char SpellCorrector::alphabet[] = "abcdefghijklmnopqrstuvwxyz";

bool sortBySecond(const Pair& left, const Pair& right)
{
        return left.second < right.second;
}

void SpellCorrector::load(string filename)
{
        ifstream file(filename.c_str());
        char* data;
       
        file.seekg(0, ios_base::end);
        int length = file.tellg();
        file.seekg(0, ios_base::beg);

        data = new char[length+1];

        file.read(data, length);

        string line(data);

        delete [] data;
       
        transform(line.begin(), line.end(), line.begin(), tolower);

        string::size_type position = 0;
        while ((position = line.find_first_of(alphabet, position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_not_of(alphabet, position);

                dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }
}

string SpellCorrector::correct(string word)
{
        Vector result;
        Dictionary candidates;

        if (dictionary.find(word) != dictionary.end()) { return word; }

        edits(word, result);
        known(result, candidates);

        if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), sortBySecond)->first; }

        for (unsigned int i = 0;i < result.size();i++)
        {
                Vector subResult;
                edits(result[i], subResult);
                known(subResult, candidates);
        }

        if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), sortBySecond)->first; }

        return "";
}

void SpellCorrector::known(Vector& results, Dictionary& candidates)
{
        Dictionary::iterator end = dictionary.end();
        for (unsigned int i = 0;i < results.size();i++)
        {
                Dictionary::iterator value = dictionary.find(results[i]);
               
                if (value != end) candidates[value->first] = value->second;
        }
}

void SpellCorrector::edits(string& word, Vector& result)
{
        for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i)                  + word.substr(i + 1)); //deletions
        for (string::size_type i = 0;i < word.size() - 1;i++) result.push_back(word.substr(0, i) + word[i+1] + word.substr(i + 2)); //transposition

        for (char j = 'a';j <= 'z';++j)
        {
                for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i) + j + word.substr(i + 1)); //alterations
                for (string::size_type i = 0;i < word.size() + 1;i++) result.push_back(word.substr(0, i) + j + word.substr(i)    ); //insertion
        }
}

---

By the way, why should i implement the class functions in the separate .cpp? I have always done this but with no good reason to do that, and i think that header style implementations are easier to redistribute a library just like STL and some boost libraries do... More suggestions would be great.

Quote:

---

By the way, why should i implement the class functions in the separate .cpp? I have always done this but with no good reason to do that, and i think that header style implementations are easier to redistribute a library just like STL and some boost libraries do...

---

Unless the class is templated, implementing it in the header also makes compiling times longer, as well as throws code in that the user shouldn't see. With templates the class must be implemented in the header as virtually no compiler supports export keyword that would make the separation possible.

Now you should also move some of the #include directives from your header file to your .cpp file. Try to #include as little as possible in header files -- basically you would only need <string> <map> & <vector>. Everything else is only used in your .cpp file.

It, for one thing, makes it a mess to traverse the header to look at all the functions and members a class contains.

Quote:

---

Originally Posted by Elysia

It also makes it a mess to traverse the header to look at all the functions and members a class contains.

---

Yeah, that's one of the reasons I like C++ over Java. But then there's so many C++ things that I wish Java had...

The compiler doesn't automatically inline functions that are in header files, but you have to put inline functions in header files, for the compiler to do the replacement.

Also, from what I understand, even if you tell the compiler to inline a function, the compiler is free to do whatever it thinks is best. So inline is really more of a suggestion to the compiler.

Quote:

---

Originally Posted by cpjust

Also, from what I understand, even if you tell the compiler to inline a function, the compiler is free to do whatever it thinks is best. So inline is really more of a suggestion to the compiler.

---

This is correct, the compiler will only inline functions if it "feels it's a good idea", which has some pretty complex heuristics, e.g. a medium sized function may be inlined if it's only called a few times, but add a few more calls, and it will not be inlined, because the compiler says "it bloats the code too much". Very short functions are usually always inlined - assuming the compiler can figure out how to do that, that is. Virtual functions can only be inlined when the compiler can know for sure what the exact function to call is, for example [assuming all other criteria apply to make it inlined].

--
Mats

Microsoft's compiler, for example, has been completely ignoring the inline keyword (aside from the code folding requirement it implies) for quite a few versions now.

Quote:

---

Originally Posted by cpjust

If you want to use a using statement, keep them in .cpp files AFTER all your #include statements.

---

Because most code is contained within functions, you can do a "using namespace" inside function scope to make life easier without affecting users of the header file. Of course, you'd only have function code in a header if you were writing inline or template functions, but that's pretty common. For instance:

Code:

---

// File my_header.hh

using namespace std; // BAD

inline void some_inline_func()
{
    using namespace std; // OKAY

    code_that_uses_stuff_from_std;
}

---

Ok, i have done some modifications, here is the result:

Code:

---

#ifndef _SPELLCORRECTOR_H_
#define _SPELLCORRECTOR_H_

#include <map>
#include <vector>

class SpellCorrector
{
private:

        typedef std::map<std::string, int> Dictionary;
        typedef std::vector<std::string> Vector;

        static const char alphabet[];
        Dictionary dictionary;

        void edits(std::string& word, Vector& result);
        void known(Vector& results, Dictionary& candidates);

public:
        void load(std::string filename);
        std::string correct(std::string word);
};

#endif

---

Code:

---

#include <fstream>
#include <string>
#include <algorithm>

#include "SpellCorrector.h"

using namespace std;

const char SpellCorrector::alphabet[] = "abcdefghijklmnopqrstuvwxyz";

bool sortBySecond(const pair<std::string, int>& left, const pair<std::string, int>& right)
{
        return left.second < right.second;
}

void SpellCorrector::load(string filename)
{
        ifstream file(filename.c_str());
        char* data;
       
        file.seekg(0, ios_base::end);
        int length = file.tellg();
        file.seekg(0, ios_base::beg);

        data = new char[length+1];

        file.read(data, length);

        string line(data);

        delete [] data;
       
        transform(line.begin(), line.end(), line.begin(), tolower);

        string::size_type position = 0;
        while ((position = line.find_first_of(alphabet, position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_not_of(alphabet, position);

                dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }
}

string SpellCorrector::correct(string word)
{
        Vector result;
        Dictionary candidates;

        if (dictionary.find(word) != dictionary.end()) { return word; }

        edits(word, result);
        known(result, candidates);

        if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), sortBySecond)->first; }

        for (unsigned int i = 0;i < result.size();i++)
        {
                Vector subResult;
                edits(result[i], subResult);
                known(subResult, candidates);
        }

        if (candidates.size() > 0) { return max_element(candidates.begin(), candidates.end(), sortBySecond)->first; }

        return "";
}

void SpellCorrector::known(Vector& results, Dictionary& candidates)
{
        Dictionary::iterator end = dictionary.end();
        for (unsigned int i = 0;i < results.size();i++)
        {
                Dictionary::iterator value = dictionary.find(results[i]);
               
                if (value != end) candidates[value->first] = value->second;
        }
}

void SpellCorrector::edits(string& word, Vector& result)
{
        for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i)                  + word.substr(i + 1)); //deletions
        for (string::size_type i = 0;i < word.size() - 1;i++) result.push_back(word.substr(0, i) + word[i+1] + word.substr(i + 2)); //transposition

        for (char j = 'a';j <= 'z';++j)
        {
                for (string::size_type i = 0;i < word.size();    i++) result.push_back(word.substr(0, i) + j + word.substr(i + 1)); //alterations
                for (string::size_type i = 0;i < word.size() + 1;i++) result.push_back(word.substr(0, i) + j + word.substr(i)    ); //insertion
        }
}

---

I have some especific questions:
1) In the load functions isn&#180;t there any easier way to read all data from a file without affecting too much performance?

2) I have tried

Code:

---

string data;
getline(file, data, file.widen(EOF));

---

but it seems that performance gets affected by it, i tought it is because it checks each character of the file until EOF is reached, am i right?

3) It seems that the most intensive loop in my application, besides I/O, is the one that i break the lines and insert them into the map... is there any way i could do this faster?

I think your current load function is about as efficient as you can get. Is it actually measurably slow at the moment, and if so, what part of it is slow? [You can perhaps output a timestamp after each small section of your load process - I suspect you spend most of the time reading the file, followed by your while-loop processing the input data].

--
Mats

Code:

---

void SpellCorrector::load(string filename)
{
        ifstream file(filename.c_str());
        char* data;

        boost::timer t1;

        file.seekg(0, ios_base::end);
        int length = file.tellg();
        file.seekg(0, ios_base::beg);

        data = new char[length+1];

        file.read(data, length);

        string line(data);

        delete [] data;

        cout << "t1:" << t1.elapsed() << "s \n";

        boost::timer t2;

        transform(line.begin(), line.end(), line.begin(), tolower);

        cout << "t2:" << t2.elapsed() << "s \n";

        boost::timer t3;

        string::size_type position = 0;
        while ((position = line.find_first_of(alphabet, position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_not_of(alphabet, position);

                dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }
        cout << "t3:" << t3.elapsed() << "s \n";
}

---

This gives me the following output:
t1: 0.218s
t2: 0.125s
t3: 2.985s

So, the most CPU intensive loop is the string "splitting" part, how can i do it more efficiently? By the way, the file is about 6.3MB.

I don't know. Do you know which is the more cpu consuming, the finding in the string, or the update of your dictionary? How much time do you save if you remove the dictionary[]++ line [this is of course not a valid change ultimately, but it makes sense to understand which part of this function that is the more time consuming].

--
Mats

using the functions in this way

Code:

---

        string::size_type position = 0;
        while ((position = line.find_first_of(alphabet, position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_not_of(alphabet, position);
                string s (line.substr(position, endPosition - position));
                //dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }

---

t3 gives me an output of 0.969s. Then dictionary insertion is tooking a hell long time there uh?

You might probably gain something if you used a sorted vector of pair<string, int>. For that you might need to preprocess the dictionary file: read it as you do now and save the contents of the map.

Ah, sure, im planning to do that, but i wanted to improve the algorithm to read it in the first time, as we are doing now, no preprocessing.

I don't know if this will improve performance much, but in Item 29 of "Effective STL" Scott Meyers suggests using istreambuf_iterators for character-by-character input:

Code:

---

// Open filename.txt.
ifstream inputFile( "filename.txt" );

// Load entire file into fileData string.
string fileData( (istreambuf_iterator<char>( inputFile )),
                        istreambuf_iterator<char>() );

---

Quote:

---

Originally Posted by cpjust

Yeah, that's one of the reasons I like C++ over Java. But then there's so many C++ things that I wish Java had...

---

You might like C# then.

And by the way, using good programming practices you don't usually end up with that problem in Java or C#, because in order to keep classes loosely coupled (which should always be a major goal, especially if this is a class designed for other people to use), it should be implementing an interface. All you need to provide to the user of your class is your interface; how your class or classes implement it is irrelevant. This allows bare minimal coupling between your classes and theirs.

After some time spended i could achieve the following code:

Code:

---

void SpellCorrector::load(const std::string& filename)
{
        ifstream file(filename.c_str(), ios_base::binary | ios_base::in);

        boost::timer t1;

        file.seekg(0, ios_base::end);
        int length = file.tellg();
        file.seekg(0, ios_base::beg);

        string line(length, '0');

        file.read(&line[0], length);

        cout << "t1:" << t1.elapsed() << "s \n";

        boost::timer t2;

        transform(line.begin(), line.end(), line.begin(), tolower);

        cout << "t2:" << t2.elapsed() << "s \n";

        boost::timer t3;

        string::size_type position = 0;
        while ((position = line.find_first_of(alphabet, position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_not_of(alphabet, position);

                dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }
        cout << "t3:" << t3.elapsed() << "s \n";
}

---

with these marks:
t1:0.078s
t2:0.109s
t3:2.109s

I just wanted to optimize the sring parsing now and i would be happy... I will keep searching...

Erm, that's a big line.
Break it into lines and use code tags.

Sorry ;P, fixed.

You may find that it's quicker to not use the find_first[_not]_of function to find a (non-)alphabet character. As far as I can tell, there's no direct way to determine if a letter is NOT in the list, but by comparing it throughout the entire 26 characters. This PARTICULARLY applies to the "not of" case.

A better method would be to make a comparison with the start/end of the range you want it to be in/out of. If you create your own function for that, I predict it will be a little bit quicker - but of course, you still spend a significant time to insert the item in the dictionary, from previous profile analysis.

--
Mats

Sweet, thank you matsp you gave me a hell nice idea:

Code:

---

char filterNonAlphabetic(char& letter)
{
        if (isalpha(letter))
                return tolower(letter);
        return '-';
}


void SpellCorrector::load(const std::string& filename)
{
        ifstream file(filename.c_str(), ios_base::binary | ios_base::in);

        boost::timer t1;

        file.seekg(0, ios_base::end);
        int length = file.tellg();
        file.seekg(0, ios_base::beg);

        string line(length, '0');

        file.read(&line[0], length);

        cout << "t1:" << t1.elapsed() << "s \n";

        boost::timer t2;

        transform(line.begin(), line.end(), line.begin(), filterNonAlphabetic);

        cout << "t2:" << t2.elapsed() << "s \n";

        boost::timer t3;

        string::size_type position = 0;
        while ((position = line.find_first_not_of('-', position)) != string::npos)
        {
                string::size_type endPosition = line.find_first_of('-', position);

                dictionary[line.substr(position, endPosition - position)]++;

                position = endPosition;
        }

        cout << "t3:" << t3.elapsed() << "s \n";
}

---

Now i get these marks:
t1:0.063s
t2:0.188s
t3:1.5s

Nice increase huh?

How about cleaning up the file, so it always contains exactly one special character between words and you won't have to transform anything and won't have to look for first_of/first_not_of? - may not be a good choice because it can also appear in some words.

I can´t cheat changing the file format hehe. Actually im pretty satisfied with my parser speed now, thank you all, your tips were very usefull!

What do you mean by cheating?

It is always nice to have an easily readable file.

I think what the OP means is that the original file format is fixed, and can't (easily) be changed.

--
Mats

matsp is right.

Ok, im a tireless optimizer, i have improved t3 performance mark with the following parsing:

Code:

---

        for (string::size_type i = 0;;)
        {
                while (line[++i] == '-' && i < end); //find first '-' character

                if (i >= end) { break; }

                begin = i;
                while (line[++i] != '-' && i < end); //find first not of '-' character

                dictionary[line.substr(begin, i - begin)]++;
        }

---

I was able to squeeze out 1,266 seconds from this function, over the 1.5s of before...