ищет более быстрый способ помочь уменьшить / создать огромный список строк - PullRequest
Новая
       20

ищет более быстрый способ помочь уменьшить / создать огромный список строк

2 голосов
/ 01 мая 2019

Я попытался написать алгоритм для правильного угадывания в игре "Masterminds",
он работает, среднее число догадок равно 6, но вычисление лучшего предположения занимает много времени.

Я использовал идею Кнута, алгоритм работает следующим образом:

  1. Создайте набор S из 1296 возможных кодов (1111, 1112 ... 6665, 6666).
  2. Начните с начального предположения 1122 (Кнут приводит примеры, показывающие, что другие первые предположения, такие как 1123, 1234, не выигрывают в пяти попытках для каждого кода).
  3. Воспользуйтесь предположением, чтобы получить ответ из цветных и белых колышков.
  4. Если ответ - четыре цветных колышка, игра выиграна, алгоритм завершается.
  5. В противном случае удалите из S любой код, который не дал бы тот же ответ, если бы текущее предположение было кодом.

В моем коде шаг 2 - взять случайное число.

Я использовал для этого vector<string>.

AllPoss - векторполный строк, я думаю, это последнее предположение, которое было использовано.answer - это количество быков и коров, которые выглядят как "x, y" (где x и y - числа) 

void bullpgia::SmartGuesser::remove(string guess, string answer)
{
    for (auto i= AllPoss.begin();i != AllPoss.end();i++){
        string token = *i;
        if (calculateBullAndPgia(token, guess) != answer)
        AllPoss.erase(i--);
    }
}

это та часть, которую нужно вычислить, есть ли способулучшения?

для создания списка, который я использовал: 

void bullpgia::SmartGuesser::All() {
    /**
     * creates a pool of all the possibilities strings
     * we then delete the ones we dont need
     * @param length is the length of the word we need to guess
     */
    for(int i=0;i<pow(10,length);i++){
        stringstream ss;
        ss << setw(length) << setfill('0') << i;
        string s = ss.str();
        AllPoss.push_back(s);
    }
}

функция CalculateBullAndPgia (строка, строка): 

string calculateBullAndPgia(const string &choice, const string &guess) {
    string temp = choice;
    string temp2 = guess;
    unsigned int bull = 0;
    unsigned int pgia = 0;
    for (int i = 0; i < temp.length(); i++) {
        if (temp[i] == temp2[i]) {
            bull++;
            temp[i] = 'a';
            temp2[i] = 'z';
        }
    }
    for (int i = 0; i < temp.length(); i++) {
        for (int j = 0; j < temp2.length(); j++) {
            if (i != j && temp[i] == temp2[j]) {
                pgia++;
                temp[i] = 'a';
                temp2[j] = 'z';
            }
        }
    }
    return to_string(bull) + "," + to_string(pgia);
}

1 Ответ

3 голосов
/ 01 мая 2019

Стирание одного элемента в середине вектора - O (n). Я предполагаю, что вы делаете это O (n) раз за звонок на SmartGuesser::remove. Затем вы зацикливаетесь на этом, так что вы, вероятно, имеете алгоритм O (n ^ 3). Вместо этого вы можете использовать std::remove_if, то есть O (n), чтобы переместить все подлежащие удалению элементы в конец вектора, где их можно дешево удалить .:

AllPoss.erase(std::remove_if(AllPos.begin(), AllPos.end(), [&](const std::string& token, const std::string& guess) { return calculateBullAndPgia(token, guess) != answer; }), AllPos.end());
...