4
\$\begingroup\$

I wrote a program that takes a string as standard input and checks if the words in the string are in the scrabble dictionary, then checks each letter of the words and gives back the the score of the words based off of what they would be worth in scrabble. The program is supposed to be written using various STL containers, which I did but it is still not running fast enough.

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

int main() {
  std::vector<std::string> scrabble;
  {
    std::ifstream scrabble_words("/srv/datasets/scrabble-hybrid");
    for (std::string word; std::getline(scrabble_words, word);) {
      scrabble.push_back(word);
    }
  }
  std::unordered_map<std::string, int> points;
  std::string letter;
  int total_count = 0;
  std::ifstream in_file("/srv/datasets/scrabble-letter-values");
  for (int worth; in_file >> letter >> worth;) {
    points[letter] = worth;
  }
  int word_count = 0;
  std::string word;
  for (word; std::cin >> word;) {
    std::for_each(word.begin(), word.end(), [](char& c) { c = ::toupper(c); });
    if (std::find(scrabble.begin(), scrabble.end(), word) != scrabble.end()) {
      word_count++;
      for (int i = 0; i < word.length(); i++) {
        std::string x(1, word[i]);
        total_count = total_count + points[x];
      }
    }
  }
  if (word_count == 1) {
    std::cout << word_count << " word worth " << total_count << " points"
              << std::endl;
  } else {
    std::cout << word_count << " words worth " << total_count << " points"
              << std::endl;
  }
}

Any ideas on how to make this run faster/more efficiently?

\$\endgroup\$
1
  • \$\begingroup\$ Is the word list sorted? Your std::find is doing a linear search thru your vector. One alternative is a Trie. \$\endgroup\$ Oct 3, 2021 at 20:42

2 Answers 2

5
\$\begingroup\$

Use the right STL containers

Searching for an entry in a std::vector of words with std::find() is going to be very slow, as it just checks against each item in the list. A much better option is to use a std:unordered_set, and then use the member function count() to check if a given word is in the set of scrabble words.

As for points, there you actually don't want to use an std::unordered_map, even though it has \$\mathcal{O}(1)\$ lookups, it still needs to calculate a hash every time you want to look up an item, and that's unnecessary here. You know that there are exactly 26 letters, so you can just make it a std::array<26, int>, and use points[x - 'A'] to look up the number of points for a given letter.

Don't treat word_count == 1 differently

Avoid making special cases for printing counts that might be 1. It adds duplication to your code, and can get out of hand quickly if you have to print many counts this way. In fact, while you handled the singular for word_count, you didn't handle the (admittedly unlikely) case where total_count == 1. And in English there's just singular and plural, but some other languages have a dual, trial or other forms of plurals as well.

It's relatively easy to change the way you print the results to avoid having to deal with singular and plural forms:

std::cout << "Number of words: " << word_count << "\n";
std::cout << "Total points: " << total_count << "\n";

Missing error checking

You are not checking if the two input files were read correctly. After reading in all the words and letter values, use eof() to check that the whole file was read. If not, there was a read error.

Further performance improvements

If the number of words given on the standard input is much larger than the number of valid scrabble words, you might make your program faster by computing the score of each valid word up front, and storing the valid words and their score in a std::unordered_map.

If only a small number of words will be read from standard input, and the file scrabble-hybrid is already sorted, it might be faster to not read in that whole file into memory, but just do a binary search in the file each time you need to look up a word.

\$\endgroup\$
2
\$\begingroup\$

These are the tips I can give you:

  • use std::set for unique ordered things, it has fast O(log N) search capabilities.
  • just use std::map not unordered_map, it can search by key in O(log N) as well (maybe unordered map has this to but I almost never use it)
  • Add scores for both lower and upper case letters to the map (this avoids having to change each character before looking it up)
  • Don't load letter scores from file (unless they really need to be flexible)
  • Make small functions for readability

EDIT : based on comments : replaced map with unordered map and set with set<string_view> and changed load to read all words into a buffer at once, and then pick string_views out of it (todo : replace with binary file with '\0'`s and add data for string_view (offsets,length) in to it)

In code it would look like this :

#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <set>

// keep everything scrabble together. Ideally split into header and cpp file.
class scrabble_t final
{
public:
    scrabble_t()
    {
        load_scrabble_words();
        load_letter_scores();
    }

    // Check if word exists, and if so calculate score otherwise a score of 0 is returned.
    auto get_score(const std::string_view& word)
    {
        unsigned int score{ 0 };

        // searching in a set is much faster then in a vector.
        // C++20, if ( m_scrabble_words.contains(word)) for better readability;
        if (auto it = m_scrabble_words.find(word) != m_scrabble_words.end())
        {
            score = calculate_score(word);
        }
        return score;
    }

    void show_all_scores()
    {
        for (const auto& word : m_scrabble_words)
        {
            auto score = calculate_score(word); // no need to check if word exists.
            std::cout << "word : " << word << " has score of : " << score << "\n";
        }
    }

private:
    // calculate the score for an existing word, no checks.
    unsigned int calculate_score(const std::string_view& word)
    {
        unsigned int score{ 0 };

        for (const char c : word)
        {
            // no need to check upper/lower case since map contains both
            score += m_letter_scores.at(c);
        }

        return score;
    }

    void load_scrabble_words()
    {
        //std::ifstream file("/srv/datasets/scrabble-hybrid");
        std::istringstream file("Apple\nBanana\nCitrus\nDog\nElephant\nFish\n");
    
        // read whole file into once
        m_words_buffer.insert(m_words_buffer.begin(), std::istreambuf_iterator<char>(file), std::istreambuf_iterator<char>());

        // extract string_views from buffers, this will avoid copying
        // of read strings into the buffer.
        auto word_begin = m_words_buffer.begin();
        for (auto it = m_words_buffer.begin(); it != m_words_buffer.end(); ++ it)
        {
            if ( *it == '\n')
            {
                m_scrabble_words.emplace(std::string_view(word_begin, it));
                word_begin = it+1;
            }
        }
    }

    // don't load scores from file, but compile
    // they're not likely to change.
    void load_letter_scores()
    {
        // quick way of specifiying letter scores.
        // could also be done from file by using ifstream instead.
        static std::istringstream scores{ "1 aeilnorstu 2 dg 3 bcmp 4 fhvwy 5 k 8 jx 10 zq" };

        unsigned int score;
        std::string letters;

        // load scores from stringstream (would be the same from file)
        while (scores >> score >> letters)
        {
            // insert both lower AND upper case into map
            // this will avoid special cases later on.
            for (const char c : letters)
            {
                m_letter_scores.insert({ c, score });
                // ALSO insert the upper case letters
                // toupper is now only called once for each letter (26 times)
                m_letter_scores.insert({ std::toupper(c), score });
            }
        }
    }

    // set is a better container for ordered unique data
    // it will insert the words in a tree making searching much faster
    // O(log n) instead of O(n) for vector
    std::set<std::string_view> m_scrabble_words;

    // unordered_map has O(1) search capability on key.
    std::unordered_map<char, unsigned int> m_letter_scores;

    std::vector<char> m_words_buffer;
};


int main()
{
    scrabble_t scrabble;
    scrabble.show_all_scores();
}
\$\endgroup\$
4
  • \$\begingroup\$ std::unordered_map has O(1) lookups. You might want to check up on all the STL containers and their properties. A std::map can certainly be used in many places, but it's not always the most performant choice. \$\endgroup\$
    – G. Sliepen
    Oct 4, 2021 at 12:02
  • \$\begingroup\$ @G.Sliepen Thanks for that info, I'll have a look. There where 3 containers I never really looked at yet : multimap, multiset and unordered_map. \$\endgroup\$ Oct 4, 2021 at 14:38
  • \$\begingroup\$ You should use std::string_view for parameters. \$\endgroup\$
    – JDługosz
    Oct 4, 2021 at 16:21
  • \$\begingroup\$ Example updated \$\endgroup\$ Oct 5, 2021 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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