C++ Processing Hog

Question

Я очень новичок в C++ (не новичок в программировании) и работаю с проблемами, связанными с Google Code Jam. Я решил проблему (Alien Language) правильно как на Python (мой самый опытный язык), так и на C++ по тому же алгоритму. По моему опыту C++ намного быстрее, чем python по многим очевидным причинам; однако моя версия python выполнена на 100 раз быстрее, чем моя версия на C++. Обработка была ограничивающим фактором. Я, очевидно, делаю что-то очень плохое, я просто не знаю, что это такое. Прежде чем принимать более сложные меры для поиска ресурса, я подумал, что попрошу здесь, поскольку это кажется очень простым решением для кого-то, у кого есть опыт работы с C++, указать ресурс или метод в моем коде, который неэффективен. Я запускаю среду unix.

Я отправлю свой код на C++ ниже. Если кто-то думает, что мой код на Python поможет им ответить на мой вопрос, я буду рад также опубликовать его.

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

int main() 
{ 
    int L, D, N; 

    std::cin >> L; 
    std::cin >> D; 
    std::cin >> N; 
    std::cin.ignore(); 

    std::string dictionary [D]; 
    for (int i=0; i<D; i++) { 
     std::getline(std::cin, dictionary[i]); 
    } 

    for (int tt=1; tt<=N; tt++) { 
     std::cerr << tt << std::endl; 

     std::string case_word; 
     std::getline(std::cin, case_word); 

     int current_letter = 0; 

     std::vector <int> invalid_indexes; 

     while (case_word.length() > 0) { 
      std::vector <char> required_letters; 
      if (case_word[0] != '(') { 
       required_letters.push_back(case_word[0]); 
       case_word.erase(case_word.begin()); 
      } 

      else { 
       std::string::iterator closing_parenthesis = std::find(case_word.begin(), case_word.end(), ')'); 
       std::string::iterator p = case_word.begin()+1; 
       while (p != closing_parenthesis) { 
        required_letters.push_back(*(p++)); 
       } 
       case_word.erase(case_word.begin(), closing_parenthesis+1); 
      } 

      for (int dictionary_word=0; dictionary_word<D; dictionary_word++) { 
       if (std::find(invalid_indexes.begin(), invalid_indexes.end(), dictionary_word) != invalid_indexes.end()) { 
        continue;       
       } 
       if (std::find(required_letters.begin(), required_letters.end(), dictionary[dictionary_word][current_letter]) == required_letters.end()) { 
        invalid_indexes.push_back(dictionary_word); 
       } 
      } 

      current_letter++; 
     } 
     std::cout << "Case #" << tt << ": " << D - invalid_indexes.size() << std::endl; 
    } 
return 0; 
} 

Answer 1

Здесь мой пропуск через ваш код. Вероятно, есть некоторые фантазии DFA, которые могут быть построены из словаря, чтобы полностью ускорить алгоритм. Это всего лишь попытка ускорить работу алгоритма с лучшими структурами данных.

for (int tt=1; tt<=N; tt++) { 
    std::cerr << tt << std::endl; 

    std::string case_word; 
    std::getline(std::cin, case_word); 

    int current_letter = 0; 
    std::string::iterator i = case_word.begin(); 

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

std::tr1::unordered_set<int> invalid_indexes(D); 

    while (i != case_word.end()) { 
     std::tr1::unordered_set<char> required_letters(256); 

Используйте неупорядоченный набор для более эффективного поиска индекса. (Пространство имен tr1 связано с тем, что я скомпилирован без включения C++ 11).

 if (*i != '(') { 
      required_letters.insert(*i); 
      ++i; 
     } 

     else { 
      std::string::iterator closing_parenthesis 
       = std::find(i, case_word.end(), ')'); 
      std::string::iterator p = i+1; 
      while (p != closing_parenthesis) { 
       required_letters.insert(*(p++)); 
      } 
      i = closing_parenthesis+1; 
     } 

     for (int dictionary_word=0; dictionary_word<D; dictionary_word++) { 
      int index = dictionary_word; 
      if (invalid_indexes.find(index) != invalid_indexes.end()) { 
       continue; 
      } 
      char letter = dictionary[index][current_letter]; 
      if (required_letters.find(letter) == required_letters.end()) { 
       invalid_indexes.insert(dictionary_word); 
      } 

Обратите внимание на упрощена (и быстрее) поиск, что результаты от использования unordered_set.

 } 

     current_letter++; 
    } 
    std::cout << "Case #" << tt 
       << ": " << D - invalid_indexes.size() 
       << std::endl; 
}