如何加速我的 C++ 程序？

Question

基本上我正在重新学习 C++ 并决定创建一个乐透号码生成器。该代码会创建票证，如果该票证尚不存在，则会将其添加到向量中以存储所有可能的组合。

该程序可以运行，但它太慢了，大约每秒添加一个条目，而且它会变得更慢，因为它发现从超过 1300 万种可能的组合中添加独特的组合变得更加困难。

无论如何，这是我的代码，任何优化提示将不胜感激：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> lottoCombos;

const int NUMBERS_PER_TICKET = 6;
const int NUMBERS = 49;
const int POSSIBLE_COMBOS = 13983816;

string createTicket();
void startUp();
void getAllCombinations();

int main()
{
    lottoCombos.reserve(POSSIBLE_COMBOS);
    cout<< "Random Ticket: "<< createTicket()<< endl;

    getAllCombinations();

    for (int i = 0; i < POSSIBLE_COMBOS; i++)
    {
        cout << endl << lottoCombos[i];
    }

    system("PAUSE");
    return 0;
}

string createTicket()
{
    srand(static_cast<unsigned int>(time(0)));
    vector<int> ticket;
    vector<int> numbers;
    vector<int>::iterator numberIterator;

    //ADD AVAILABLE NUMBERS TO VECTOR
    for (int i = 0; i < NUMBERS; i++)
    {
        numbers.push_back(i + 1);
    }

    for (int j = 0; j < NUMBERS_PER_TICKET; j++)
    {
        int ticketNumber = rand() % numbers.size();
        numberIterator = numbers.begin()+ ticketNumber;
        int nm = *numberIterator;
        numbers.erase(numberIterator);
        ticket.push_back(nm);
    }
    sort(ticket.begin(), ticket.end());

    string result;
    ostringstream convert;
    convert << ticket[0] << ", " << ticket[1] << ", " << ticket[2] << ", " << ticket[3] << ", " << ticket[4] << ", " << ticket[5];
    result = convert.str();

    return result;
}

void getAllCombinations()
{
    int i = 0;
    cout << "Max Vector Size: " << lottoCombos.max_size() << endl;
    cout << "Creating Entries" << endl;

    while ( i != POSSIBLE_COMBOS )
    {
        bool matchFound = true;
        string newNumbers = createTicket();

        for (int j = 0; j < lottoCombos.size(); j++)
        {
            if ( newNumbers == lottoCombos[j] )
            {
                matchFound = false;
                break;
            }
        }

        if (matchFound != false)
        {
            lottoCombos.push_back(createTicket());
            i++;
            cout << "Entries: "<< i << endl;
        }
    }
    sort(lottoCombos.begin(), lottoCombos.end());
    cout << "\nCombination generation complete!!!\n\n";
}

Answer 1

每张彩票需要一秒钟才能生成的原因是您误用了 srand()。通过在每次调用 createTicket() 时调用 srand(time(0))，您可以确保每次调用 createTicket() returns 相同的数字，直到下一次 time() 返回的值发生变化，即每秒一次。因此，您的拒绝重复算法几乎总是会找到重复项，直到下一秒过去。您应该将 srand(time(0)) 调用移至 main() 的顶部。

也就是说，这里可能还有更大的问题要面对：我的第一个问题是，是否真的有必要生成并存储每张可能的彩票？（如果是，为什么？）IIRC 真正的彩票在开票时不会这样做；他们只是生成一些随机数并将它们打印出来（如果有多张印有相同数字的中奖彩票，则这些彩票的所有者分享奖金）。

假设您出于某种原因确实需要生成每张可能的彩票，有比随机生成更好的方法。如果您曾经在驾驶汽车时观察过里程表的增量，您就会知道如何以线性方式进行增量；试想一个有 6 个轮子的里程表，每个轮子有 49 个不同的可能位置（而不是传统的 10 个）。

最后，向量的查找时间为 O(N)，如果您在向量中查找生成的每个值，那么您的算法的时间为 O(N^2)，也就是说，当您生成更多票时，它会变得非常慢非常快。因此，如果您必须将所有已知票证存储在数据结构中，您绝对应该使用查找时间更快的数据结构，例如 std::map 或 std::unordered_set，甚至 std::bitset正如@RedAlert 所建议的那样。

如何加速我的 C++ 程序？

How Can I Speed My C++ Program Up?

c++

optimization

vector