C++ Anagram Solver 速度优化

Question

我决定为我爸爸制作一个字谜求解器。我对编程很陌生，但我认为我仍然可以做到。我的成品有效，但速度非常慢，例如，找到 8 个字符的所有组合需要大约 15 分钟以上。我正在寻找优化它/让它更快的方法。

使用 MinGW c++ 编译器，Clion 2019.3.4，cpu：i7 9700k，内存：16GB/3200mhz。

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

using namespace std;

//Menu for interacting with user, not really important
void menu() {
    cout << "=========================" << endl;
    cout << "======== !WOW! ==========" << endl;
    cout << "=========================" << endl;
    cout << "1 ... INSERT" << endl;
    cout << "2 ... PRINT" << endl;
    cout << "3 ... LIMIT WORD LENTGH" << endl;
    cout << "4 ... NEW GAME" << endl;
    cout << "0 ... EXIT" << endl;
    cout << "=========================" << endl;
    cout << "Select: ";
}

//Function to find all possible combinations from letters of a given string 
void get(vector<string> &vec, string str, string res) {

    vec.push_back(res);

    for (int i = 0; i < str.length(); i++)
        get(vec, string(str).erase(i, 1), res + str[i]);
}

//Only for testing purposes
void printVec(vector<string> vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
}

//Function to check if a given word exists in given .txt file
bool checkWord(vector<string> &vec2, string filename, string search) {

    string line;
    ifstream myFile;
    myFile.open(filename);

    if (myFile.is_open()) {
        while (!myFile.eof()) {
            getline(myFile, line);
            if (line == search) {
                vec2.push_back(line);
                return true;
            }
        }
        myFile.close();
    } else
        cout << "Unable to open this file." << endl;

    return false;
}


int main() {

    int selection;
    bool running = true;
    string stringOfChars;
    vector<string> vec;
    vector<string> vec2;

    do {

        menu();
        cin >> selection;
        switch (selection) {

            case 1:
                cout << "Insert letters one after another: ";
                cin >> stringOfChars;
                get(vec, stringOfChars, ""); //fill first vector(vec) with all possible combinations.
                break;

            case 2:
                for (int i = 0; i < vec.size(); i++) {
                    if (checkWord(vec2, "C:/file.txt", vec[i])) { //For each word in vector(vec) check if exists in file.txt, if it does, send it in vector(vec2) and return true
//Reason for vec2's existence is that later I want to implement functions to manipulate with possible solutions (like remove words i have already guessed, or as shown in case 3, to limit the word length)
                        cout << vec[i] << endl; //If return value == true cout the word
                    }
                }
                break;

            case 3:
                int numOfLetters;
                cout << "Word has a known number of letters: ";
                cin >> numOfLetters;
                for (int i = 0; i < vec2.size(); i++) { /*vec2 is now filled with all the answers, we can limit the output if we know the length of the word */
                    if (vec2[i].length() == numOfLetters) {
                        cout << vec2[i] << endl;
                    }
                }
                break;

            case 4:
                vec.clear();
                vec2.clear();
                break;

            case 0:
                running = false;
                break;

            default:
                cout << "Wrong selection!" << endl;
                break;
        }
        cout << endl;
    } while (running);

    return 0;
}

file.txt 填满了我的语言中的所有单词，按字母顺序排列，大小为 50mb。

aachecnska
aachenskega
aachenskem
aachenski
.
.
.
bab
baba
babah
.
.
.

任何建议或题外话提示都会有所帮助。我的一个想法是可能将 file.txt 分隔在较小的文件中，例如将具有相同起始字母的行放在它们自己的文件中，这样 A.txt 将只包含以 A 开头的单词等......然后相应地更改代码。

Answer 1

这是您需要使用 探查器 的地方。在 Linux，我最喜欢的是 kcachgrind

http://kcachegrind.sourceforge.net/html/Home.html

它为您提供逐行计时信息，并告诉您应该最优化代码的哪一部分。

当然，有很多分析器可用，包括商业的。

C++ Anagram Solver 速度优化

C++ Anagram Solver speed optimization

c++

performance

puzzle

anagram