2
\$\begingroup\$

I'm creating a dictionary app using Win32 API. I stored the word meaning in a file called dictionary.dic in the following format:

Word Meaning

A The first letter

B The second letter

... and so on

As my window is created, I load the dictionary file into the std::map object using this code:

std::map<wstring, wstring> dict;
...
std::wifstream stream(L"dictionary.dic");
std::wstring temp, fileContent = L"";
while (std::getline(stream, temp)) {
    fileContent += temp;
    fileContent.push_back(L'\n');
}
std::vector<wstring> lines = split(fileContent, L'\n');
for (std::wstring line : lines) {
    std::vector<wstring> word = split(line, L'\t');
    dict.insert(dict.end(), make_pair(word[0], word[1]));
}

And when the user search the word, I'm using this code to display the meaning:

std::wstring enteredWord;
map<wstring, wstring>::iterator mi;
mi = dict.find(toLower(enteredWord));
if (mi != dict.end()) {
    //display meaning
}
else {
    //word not found
}

I used these functions to convert text to lowercase and split text: I'm using this function to split the text:

std::vector<std::wstring> &split(const std::wstring &s, WCHAR delim, std::vector<std::wstring> &elems) {
    std::wstringstream ss(s);
    std::wstring item;
    while (std::getline(ss, item, delim)) {
        elems.push_back(item);
    }
    return elems;
}

std::vector<std::wstring> split(const std::wstring &s, WCHAR delim) {
    std::vector<std::wstring> elems;
    split(s, delim, elems);
    return elems;
}

std::wstring toLower(std::wstring val) {
    std::wstring temp = val;
    std::transform(temp.begin(), temp.end(), temp.begin(), tolower);
    return temp;
}

Is there a more efficient way to create a dictionary in Win32 / C++?

\$\endgroup\$
3
\$\begingroup\$

Is there a more efficient way to create a dictionary in win32 / c++.

Yes :-)

Let's look at the code:

Reading the file

// Read a file line by line.
while (std::getline(stream, temp)) {

    // Build one long........ string in memory.
    fileContent += temp;
    fileContent.push_back(L'\n');
}

// Then you split the long...... line you just built
// back into a vector of lines (using the '\n' you just inserted)
// to mark the line boundries.
std::vector<wstring> lines = split(fileContent, L'\n');

Issues

  • So you are basically doing the same work twice.
  • You are building a string in the most inefficient way possible.
    Because you did not reserve space you are reallocating that string again and again and again. Each reallocation requires the whole string to be copied.

Why not read the lines directly into the vector?

 std::vector<wstring> lines;
 std::wstring line;

 while(std::getline(stream, line)) {
     lines.push_back(line);
 }

We can even do better than that with a tiny bit of work.

 // Define a class that represents a line.
 // Then define the input operator so it knows how to read itself.
 // Then define a conversion operator so it can be converted into a string.

 class Line
 {
     std::wstring   data;
     friend std::istream& operator>>(std::istream& str, Line& value)
     {
         return std::getline(str, value.data);
     }
     operator std::wstring&() const
     {
         return data;
     }
};
using LineStreamIter = std::istream_iterator<Line>;
// now you can declare your vector and load it in a single line.
std::vector<std::wstring>  lines(LineStreamIter(source), LineStreamIter());

Moving on to loading the map:

for (std::wstring line : lines) {
    std::vector<wstring> word = split(line, L'\t');
    dict.insert(dict.end(), make_pair(word[0], word[1]));
}

So basically you are saving your map as two strings separated by the first tab onto a single line. I assume there are no '\n' characters in the meaning, otherwise your encoding is going to break.

But again this is ineffecient as you build a vector in place then use that to build the dictionary. Why not just build the dictionary directly from the file.

std::map<std::wstring, std::wstring> dict;

std::wstring word;
std::wstring meaning;

while(std::getline(source, word, '\t') && std::getline(source, meaning))
{
    dict.emplace_back(std::piecewise_construct, word, meaning);
} 

Note: std::getline() allows you specify a third argument that defines the line terminator (by default this is '\n'). By setting this to tab '\t' you can read up-to (but not including) the tab and extract the word first then extract the meaning separately.

I would take this a step further and define a dictionary class with a specific interface then use std::map internally. This has several advantages.

  1. You can replace std::map with std::vector later as suggested by @ilmale
  2. You can write the load/save functions in a self contained way.

Here is an outline:

class Dict
{
    class DictFileElement
    {
        std::pair<std::wstring, std::wstring>   value;
        frined std::istream& operator>>(std::istream& s, DictFileElement& value);
        frined std::ostream& operator<<(std::ostream& s, DictFileElement const& value);
    };

    std::map<std::wstring, std::wstring>  data;
    public:
        Dict(std::string fileName);
        std::wstring getMeaning(std::wstring const& word);
};
// I leave the implementation to you .
// Should be easy given all the code I wrote above.
\$\endgroup\$
1
\$\begingroup\$

First of all, don't do optimization for optimization sake. Usually optimization make code less readable, if no optimization is required readable code is better. In a standard english dictionary there are less than 60000 words. Even with linear search a computer can crush your dictionary in a fraction of a second.

In any case because I think this is more a learning exercise than a real program here some tips.

Maps are cache inefficient. They store elements in a tree, and each element is not guarantee to be contiguos in memory. Usually access to main memory is the bottleneck in a lot of applications. If you analyse the data you will find that:

  • A dictionary is always ordered.
  • And usually is read only, or at least the read are much more frequent than the write.
  • When you search a word you don't need the definition.

With these premises you can reduce the memory access by storing the word in a contiguos array and use binary search to find the word. When you have the word you can find the corresponding definition in another array at the same position.

I'm not an expert of unicode, but switching from WString to UTF-8 should reduce the comparison cost. You will need a library like this one to work with UTF-8.

\$\endgroup\$
  • \$\begingroup\$ Maybe in American English there are only 60K. In British English closer to 170K (in current usage) oxforddictionaries.com/us/words/… :-) Still crush-able by a computer in a fraction of a second. \$\endgroup\$ – Martin York Mar 23 '16 at 15:05
  • \$\begingroup\$ They added alot of words from the last time I counted them. I must admit that I just give a random number hoping to get the right order of magnitude. :-S \$\endgroup\$ – ilmale Mar 23 '16 at 15:37
  • \$\begingroup\$ There are definate advantages to using fixed width strings in memory. It makes a whole class of problem go away. I like UTF-8 for storage and transport (because of the very efficient compression). But I like to use UTF-32 (UCS-4) in memory. Though of course windows is stupid and uses UTF-16 (UCS-2) in memory which is the worst of all cases. \$\endgroup\$ – Martin York Mar 23 '16 at 15:40
  • \$\begingroup\$ In this case, just doing a really straightforward implementation will probably make the code more readable and a fair amount faster, so the "optimization usually makes code less readable" doesn't apply particularly well here. \$\endgroup\$ – Jerry Coffin Mar 23 '16 at 15:50

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.