Длинные слова в словарь, которые могут быть построены из списка букв


Проблема в том, чтобы найти самые длинные слова в словаре юридических слов, которые можно построить из заданного списка писем.

Например:

$ ./scrabble dictionary.txt i g h l p r a
argil glair grail graph hilar laigh phial pilar ralph

Более детально здесь.

Я уже решил эту проблему в Python (см. Это).

Чтобы освежить мой c++ я решил воспроизвести точно такой же алгоритм на C++. Я выучил C++ как "с с классами", так и не научился правильно использовать STL, поэтому я обычно заканчиваю писать больше кода, чем это необходимо для выполнения простых вещей.

Это то, что я придумал для этой проблемы:

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

using namespace std;

bool can_make(string word, vector<char> letters);
int get_max_len(vector<string> words);


int main(int argc, char* argv[])
{
    // Grab the dictionary.
    fstream dict_file(argv[1]);
    string in;
    vector<string> dict_words;
    while(getline(dict_file, in)) dict_words.push_back(in);
    dict_file.close();

    // Get the list of input letters.
    vector<char> letters;
    for (int i = 2; i < argc; i++)
        letters.push_back(argv[i][0]);

    // Get all words.
    vector<string> all_words;
    vector<string>::iterator it;
    for (it = dict_words.begin(); it < dict_words.end(); it++)
        if (can_make(*it, letters))
            all_words.push_back(*it);

    // Get longest words.
    int max_len = get_max_len(all_words);
    vector<string> longest_words;
    for (it = all_words.begin(); it < all_words.end(); it++)
        if ((*it).length() == max_len)
            longest_words.push_back(*it);

    // Print the result.
    for (it = longest_words.begin(); it < longest_words.end(); it++)
        cout << *it << " ";
    cout << endl;

    return 0;
}


bool can_make(string word, vector<char> letters)
{
    /*
        Return true if the word <word> can be generated by all letters in <letters>
        and only the letters in <letters>.
    */

    if (word.length() > letters.size()) return false;

    vector<char> l(letters);
    vector<char> word_letters(word.c_str(), word.c_str()+word.length());
    vector<char>::iterator it, loc;

    // Iterate through <word_letters>. If a letter in <word_letters> also
    // appears in <letters>, remove it. Otherwise, return false.
    for (it = word_letters.begin(); it < word_letters.end(); it++) {
        loc = find(letters.begin(), letters.end(), *it);
        if (loc == letters.end()) return false;
        letters.erase(loc);
    }

    return true;
}


int get_max_len(vector<string> words)
{
    /*
        Return the length of the longest word(s) in <words>.
    */

    int max_len = 0;
    vector<string>::iterator it;
    for (it = words.begin(); it < words.end(); it++)
        if ((*it).length() > max_len)
            max_len = (*it).length();

    return max_len;
}
  1. Это идиоматические с++?
  2. Как я могу сделать этот код более кратким?
  3. Как я могу сделать это более правильный?
  4. Что c++11 функции я могу использовать здесь, чтобы сделать код еще короче?
  5. Какие функции я использовал здесь, что я должен избегать?


4343
3
задан 9 декабря 2011 в 07:12 Источник Поделиться
Комментарии
3 ответа

Этот пост дополняет ответы уже даны. Во-первых, несколько замечаний по поводу вашего кода:

Проверяя Довод

int main(int argc, char* argv[])
{
fstream dict_file(argv[1]);
// ...

Вы должны проверить предоставленные аргументы перед их использованием. Выполнение вашей программы без аргументов будет открыть из-за граница индекса.

Векторы везде

vector<string> dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
// ...
vector<char> letters;
for (int i = 2; i < argc; i++)
letters.push_back(argv[i][0]);
// ...
vector<string> all_words;
vector<string>::iterator it;
for (it = dict_words.begin(); it < dict_words.end(); it++)
// ...
int max_len = get_max_len(all_words);
vector<string> longest_words;
// ...

Это достаточно большое количество векторов, которые вы сделали там. Я не уверен, что они все необходимые.

bool can_make(string word, vector<char> letters);
int get_max_len(vector<string> words);

Чтобы сделать его использование еще более дармовой вам передать эти векторы по стоимости тоже!

Все принимая аргумент

// Get the list of input letters.
vector<char> letters;
for (int i = 2; i < argc; i++)
letters.push_back(argv[i][0]);

Вот я думаю, что это имеет больше смысла, чтобы использовать весь аргумент в виде писем. При необходимости вы можете проверить свой ввод с чем-то вроде isalpha.

Влияние на производительность

bool can_make(string word, vector<char> letters)
{
// ...
vector<char> l(letters);
// ...
for (it = word_letters.begin(); it < word_letters.end(); it++) {
// ...
letters.erase(loc);
}
// ...
}

Используя буквы.стереть(Лок); Либерально в петлю, как это может привести к серьезным проблемам с производительностью, особенно если вектор содержит много букв. Это связано с линейной производительности характеристики вектора::стереть , где изъяты предметы должны быть смещены более. Также обратите внимание, что ваш вектор л(буквы); не используется здесь.

И, наконец,... практический пример

Как уже намекал, вы можете урезанное на синтаксический уровень шума и улучшить читабельность(в значительной степени) с помощью алгоритмов, поставляемых в стандартной библиотеке. Если вы чистите на C++, Этот совет может быть нечетким для вас. В качестве примера, вот как я бы сделал это в истинном духе обобщенного программирования:

Вам понадобятся следующие заголовки для примера:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <iterator>
#include <algorithm>
using namespace std; // for convenience only -- don't do this on real projects


int main(int argc, char *argv[])
{
if(argc < 3)
{
// Print some error out
return -1;
}

vector<string> dictionary;
load_dictionary(argv[1], back_inserter(dictionary));

string letters = grab_letters(argv + 2, argv + argc);

deque<string> results;
for_each(dictionary.begin(), dictionary.end(), try_match(letters, results));

// No words could be matched
if(results.empty()) return 0;

// Remove short words.
while(results.back().length() > results.front().length())
results.pop_front();

copy(results.begin(),
results.end(),
ostream_iterator<string>(cout, " "));
}

Даже без комментариев, приведенный выше код очень понятный. Использование шаблона для выполнения некоторых действий по набору входов. Действие направляется на имя алгоритма (например. load_dictionary, for_each, копирование и т. д.). Входные указан как диапазон пара итераторов. Некоторые действия, такие как копирование, взять еще один итератор, чтобы указать, куда копировать.

Это похоже на Шурд по grab_dictionary функции, но изменен, чтобы принять другие контейнеры, кроме векторов.

template <typename T>
void load_dictionary(const char *filename, T appender)
{
ifstream infile(filename);
if(!infile) return;

copy(istream_iterator<string>(infile),
istream_iterator<string>(),
appender);
}

Обратите внимание на использование итератора адаптерами типа istream_iterator и ostream_iterator. С тех конструктов позволяет алгоритмы для работы с практически любой библиотеки iostream, как будто это другой контейнер.

template <typename T>
string grab_letters(T begin, const T &end)
{
string letters;
while(begin != end) letters += *begin++;

return letters;
}

Даже grab_letters следовать этому образцу для обработки дополнительные аргументы, передаваемые в. Это работает, потому что концептуально итераторы, указатели. Это означает, что вы можете использовать тип char *переменной argv[] , чтобы указать, где первый аргумент начинается и где заканчивается.

// Get all words.
deque<string> results;
for_each(dictionary.begin(), dictionary.end(), try_match(letters, results));

Это где реальная обработка происходит. В try_match функция создает функтор (удобно по имени совпадений) и передает его для for_each. Когда for_each посещает каждое слово, в свою очередь, это будет вызывать функтор через перегруженный оператор () с текущего слова в качестве аргумента.

template <typename T>
class matcher
{
public:
matcher(const string &letters, T &results);
void operator ()(const string &word);
};

template <typename T>
matcher<T> try_match(const string &letters, T &results)
{
return matcher<T>(letters, results);
}

И отсюда можно просто написать обработку произошло в классе функтора совпадений.

6
ответ дан 10 декабря 2011 в 07:12 Источник Поделиться

Предисловие

Я не уверен, что алгоритм вы выбрали лучший. Сортировка писем, или используя таблицу частот букв, очевидные альтернативы. Однако, это ревью кода, а не алгоритма комментарий.

Так что здесь мы идем:

Итераторы

Не использовать < на итераторы, использовать != на итераторы. < работает только на двунаправленных итераторов, != работает на всех итераторов. СТД::список<> пример, где < не будет работать.

Использовать ++его вместо нее++. Теоретически, последний обязан возвратить временную копию оригинала, который является дополнительным затратам при итератор-это класс. Практически, это не имеет особой разницы (если таковые имеются), большинство компиляторов будет встраивать и оптимизировать. Тем не менее, это один из лучших сигналов о том, кто является истинным эксперт C++ или переделанный с-программист :стр.

Так

for (it = dict_words.begin(); it < dict_words.end(); it++)

Станет:

for (it = dict_words.begin(); it != dict_words.end(); ++it)

Предопределенные алгоритмы

Многие из ваших однострочных петли могут быть заменены алгоритмы из .

В этом маленьком случае, я бы не стал заморачиваться, так как это не поможет сделать ваш код более ясным или короче.

С другой стороны, экспериментировать с ними в этом случае будет сделать вас более комфортно с ними. С появлением лямбд в C++11, эти алгоритмы станут гораздо более распространенными в новый код!

В C++11

Из-за того, что c++11 не давно еще (и компиляторы не полностью реализовать его пока), идиоматические C++11, которые будут меняться в течение ближайших нескольких лет. Так что берите этот раздел с зерном соли.

Это, как говорится, использовать авто по типу его. Это часть c++11 уже стало идиоматическим.

Е. Г.:

vector<string>::iterator it;
for (it = dict_words.begin(); it != dict_words.end(); ++it)

станет:

for (auto it = dict_words.begin(); it != dict_words.end(); ++it)

Правка: упс, забыл про на основе диапазона в C++11. Увидеть другие ответы, для этого. Я не настолько хорошо разбираюсь в C++11, но я думаю, это будет выглядеть так:

for (auto it : dict_words)

Больше функций

Большинство кода в одну функцию, называется основным. Попробуйте разбить его.

Как только вы начинаете вводить пустые строки и заголовки комментариев, чтобы прояснить, что происходит, это обычно является хорошим кандидатом, чтобы превратиться в отдельную функцию.

Е. Г. этот блок кода (ограниченный пустыми строками, с комментарием):

// Grab the dictionary.
fstream dict_file(argv[1]);
string in;
vector<string> dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
dict_file.close();

Можно заменить эту функцию:

void grab_dictionary(const char* filename, vector<string>& dict_words)
{
fstream dict_file(filename);
string in;
while(getline(dict_file, in))
dict_words.push_back(in);
}

Использование основных:

vector<string> dict_words;
grab_dictionary(argv[1], dict_words);

Дополнительное преимущество:


  • Комментарий уже не нужен - как правило, это стало именем функции!

  • Нет необходимости в dict_file.закрыть() , а деструктор закрывает файл в нужное время.

7
ответ дан 9 декабря 2011 в 09:12 Источник Поделиться

Вы используете слишком много копирования из одного вектора в другой.
Использовать фильтрацию.

Вместо

vector<string>::iterator it;
for (it = words.begin(); it < words.end(); it++)

использовать

for (vector<string>::const_iterator it = words.begin(), E = words.end(); it != E; ++it)

В C++11, вы должны использовать авто везде, где это возможно,
использовать begin и End функции вместо begin и End методами,
и использовать на основе диапазона на цикл для итерации по коллекции.

Ваш can_make является неоптимальным и, наверное, неправильно. (Решение Python является неоптимальным тоже).

инт get_max_len(вектор слова)
- не передать словами по значению, пока мы действительно нужно, чтобы скопировать его.
- она должна возвращать значение в size_t тип, включить предупреждения в ваш компилятор, и включить "обрабатывать предупреждения как ошибки" вариант.


УПД: @LokiAstari писал, что это плохая практика, чтобы написать Е = слова.конец(); к != Е, потому что "контейнеры, уже оптимизированы, чтобы сделать это эффективно.".
В общем случае, это неверно.
Это правда, что в некоторых тривиальных случаях, компилятор может определить, что contatiner не изменяется в теле цикла, и выполнять такую оптимизацию.
Но если контейнер есть ссылка в теле цикла по неконстантную ссылку, компилятор не может предположить, что контейнер не изменяется, поэтому он будет вам конец() итератор на каждой итерации.
Это не совпадает ; я++) против ; я++) - в тривиальных случаях, компилятор будет оптимизировать я++ к ++я, но в нетривиальных случаях он не будет делать это.

3
ответ дан 9 декабря 2011 в 09:12 Источник Поделиться