2
\$\begingroup\$

I would like to know if there is a more efficient way to speed up below code. This function is meant to fill in a set of poker hand with the remaining cards using Mersenne Twister for a Monte Carlo simulation.

void HandEvaluator::RandomFill(std::vector<std::shared_ptr<Card>>& _Set, std::vector<std::shared_ptr<Card>>& _Dead, unsigned int _Target){
    //Add the cards that are currently in Set as dead cards
    for (auto const& CardInSet : _Set)
    {
        if (CardInSet == nullptr)
            break;

        _Dead.push_back(CardInSet);
    }

    bool IsDead;
    unsigned int RequiredAmt = _Target - _Set.size();

    unsigned int CardIndex = 0;
    std::uniform_int_distribution<unsigned int> CardsDistribution(0, 51);

    for (unsigned int Index = 0; Index < RequiredAmt; Index++)
    {
        while (true)
        {
            IsDead = false;
            CardIndex = CardsDistribution(MTGenerator);

            for (auto const& Dead : _Dead)
            {
                if (ReferenceDeck[CardIndex]->GetRank() == Dead->GetRank() && ReferenceDeck[CardIndex]->GetSuit() == Dead->GetSuit())
                {
                    IsDead = true;
                    break;
                }
            }

            if (!IsDead)
            {
                _Set.push_back(ReferenceDeck[CardIndex]);
                break;
            }
        }
    }
}

The Visual Studio Profiler had identified that this line

    CardIndex = CardsDistribution(MTGenerator);

is the main culprit behind the high compute time. Is Mersenne Twister itself not meant for a Monte Carlo Simulation and another PRNG should be used instead ? Or there are some inefficient lines that I had missed out ?

\$\endgroup\$
  • \$\begingroup\$ Hi, and welcome to CodeReview! I reformatted your code section. Next time, please just paste the code, select it, then press Ctrl + K. \$\endgroup\$ – Incomputable Dec 1 '18 at 9:55
  • \$\begingroup\$ Could you please also post other parts of the code used in the post? A little example program which can be compiled and run would be awesome! Don't be concerned with size of the program, 100-200 lines of code is common for a CR question. \$\endgroup\$ – Incomputable Dec 1 '18 at 10:59
  • \$\begingroup\$ Thanks for the help ! I've done up a sample project that can be compiled and run. However, my sample project relies on a relatively large .dat file (~126mb) to perform the simulation. Should I include the .dat file into the project and upload them into a file storage site like Google Drive or include another project that generate .dat file? \$\endgroup\$ – Tomashiwa Dec 1 '18 at 12:57
  • \$\begingroup\$ Whichever is more convenient for you. People might want to check their modifications, like comparing the output of your version and their version. I believe the code you've shown here just generates the deck of cards. Maybe you could include all of the code used for it and create a small main function which generates one deck and prints it? For example, at the moment I don't know what Card is (I can guess that it is either an integer or pair which represents a card) and what is ReferenceDeck (vector of cards?). \$\endgroup\$ – Incomputable Dec 1 '18 at 13:13
  • \$\begingroup\$ Ah sorry for the confusion, this function is meant to generate a hand, _Target amt of cards, based on the remaining cards in a deck. The generation of ReferenceDeck is in another part of the HandEvaluator class and Card is a class that contains the Suit and Rank with functions to compare with other Cards. Here's the link to the sample project: drive.google.com/file/d/1U3d8ZuS_wzkq4RVIj2RV6gj1zyv_yrco/… \$\endgroup\$ – Tomashiwa Dec 1 '18 at 13:52
0
\$\begingroup\$

In the end, I opt to replace Mersenne Twister with another PRNG, xoroshiro128+, it managed to cut the compute time by around 15%. I also did some minor optimization on the for-loop but the improvement is minuscule. Anyway, here is the same function but with new PRNG:

Seeding in HandEvaluator's constructor:

HandEvaluator::HandEvaluator()
{
    Initialize();
    MTGenerator.seed(std::chrono::high_resolution_clock::now().time_since_epoch().count());

    s[0] = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::cout << "Seed 1: " << s[0] << "\n";

    s[1] = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::cout << "Seed 2: " << s[1] << "\n";
}

HandEvaluator's RandomFill function:

void HandEvaluator::RandomFill(std::vector<std::shared_ptr<Card>>& _Set, std::vector<std::shared_ptr<Card>>& _Dead, unsigned int _Target)
{
    //Add the cards that are currently in Set as dead cards
    for (auto const& CardInSet : _Set)
    {
        if (CardInSet == nullptr)
            break;

        _Dead.push_back(CardInSet);
    }

    bool IsDead;
    unsigned int RequiredAmt = _Target - _Set.size();

    for (unsigned int Index = 0; Index < RequiredAmt; Index++)
    {
        while (true)
        {
            _Set.push_back(ReferenceDeck[next() % 52]);

            IsDead = false;

            for (auto const& Dead : _Dead)
            {
                if (Dead->IsEqualTo(_Set[_Set.size() - 1]))
                {
                    IsDead = true;
                    break;
                }
            }

            if (IsDead)
                _Set.pop_back();
            else
                break;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ If you got rid of the Mersenne Twister you should probably rename MTGenerator \$\endgroup\$ – brug Dec 2 '18 at 15:54
  • \$\begingroup\$ Thanks for the heads-up, I had removed MTGenerator from HandEvaluator class as its no longer necessary \$\endgroup\$ – Tomashiwa Dec 2 '18 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.