C++ 处理 pig

Question

我是 C++ 的新手(不是编程新手)并且一直在处理 Google Code Jam 问题。我解决了问题(Alien Language)在 Python(我最有经验的语言)和 C++ 中都遵循相同的算法。以我的经验，由于许多显而易见的原因，c++ 比 python 快得多；然而，我的 python 版本执行速度比我的 c++ 版本快 100 倍。处理是限制因素。我显然做错了什么我只是不知道它是什么。在采取更精细的措施来查找资源占用之前，我想我会在这里问，因为对于具有 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;
}