3
\$\begingroup\$

Having undergone a little "rediscovery" of C++, I decided to port my Ruby narcotic solitaire simulator program to it. My goal here is efficiency. This program is already about 5 times faster than the Ruby version on my computer; I want to make it even better.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <list>
#include <random>
#include <set>
#include <map>

#include "stopwatch.h"

constexpr auto NUM_PILES = 4;
constexpr auto CARD_PLACE_SECONDS = 1;
constexpr auto GATHER_DECK_SECONDS = 5;
constexpr auto CARDS_IN_DECK = 52;
constexpr auto PERCENT = 100;
constexpr auto SECONDS_IN_MINUTE = 60;
constexpr auto MINUTES_IN_HOUR = 60;

using std::endl;


struct IterationData
{
    int num_decks;
    int completion_time;
    bool did_loop;
};


int get_insertion_position(
        std::map<int, int>& value_to_pile_map, int current_index,
        int card_value)
{
    auto insertion_position = current_index;
    auto existing_pile_it = value_to_pile_map.find(card_value);
    if (existing_pile_it != value_to_pile_map.end()) {
        insertion_position = value_to_pile_map[card_value];
    } else {
        value_to_pile_map[card_value] = current_index;
    }

    return insertion_position;
}


/* Erases the last NUM_PILES elements from an std::list. */
void erase_matching_cards(std::list<int>& pile)
{
    auto card_remover_it = pile.rbegin();
    std::advance(card_remover_it, NUM_PILES);
    pile.erase(card_remover_it.base(), pile.end());
}


/* Returns whether all the inserted cards entered the same pile. */
bool distribute_cards(std::list<int>& deck, std::list<int> piles[])
{
    auto all_identical = true;
    auto value_to_pile_map = std::map<int, int>();
    for (auto i = '\0'; i < NUM_PILES; i++) {
        auto insertion_position = get_insertion_position(
                value_to_pile_map, i, deck.back());
        if (insertion_position != 0) {
            all_identical = false;
        }

        auto correct_pile = &piles[insertion_position];
        correct_pile->splice(correct_pile->end(), deck, --deck.end());
    }

    return all_identical;
}


IterationData narcotic_iterations(std::list<int>& deck)
{
    auto completion_time = 0;
    auto num_decks = 0;
    auto did_loop = false;
    std::set<std::list<int>> past_decks;

    while (!deck.empty()) {
        std::list<int> piles[NUM_PILES];
        auto insertion_result = past_decks.insert(deck);
        did_loop = !insertion_result.second;
        if (did_loop) {
            break;
        }
        while (!deck.empty()) {
            auto all_identical = distribute_cards(deck, piles);
            completion_time += CARD_PLACE_SECONDS * NUM_PILES;
            if (all_identical) {
                erase_matching_cards(piles[0]);
            }
        }

        if (did_loop) {
            break;
        }
        for (auto& pile: piles) {
            deck.splice(deck.end(), pile);
        }
        num_decks++;
        completion_time += GATHER_DECK_SECONDS;
    }

    return {num_decks, completion_time, did_loop};
}


std::mt19937* make_random_generator()
{
    using namespace std::chrono;
    auto random_generator = new std::mt19937();
    auto current_time = high_resolution_clock::now();
    auto nanos = duration_cast<nanoseconds>(
            current_time.time_since_epoch()).count();
    random_generator->seed(nanos);
    return random_generator;
}


void shuffle_deck(std::vector<int>& deck)
{
    auto random_generator = make_random_generator();
    std::shuffle(deck.begin(), deck.end(), *random_generator);
    delete random_generator;
}

std::list<int>* generate_shuffled_deck()
{
    auto shuffler_container = std::vector<int>(CARDS_IN_DECK);
    auto suit = 0;
    auto value = 0;
    auto deck_generator_lambda = [&]
    {
        suit %= 4;
        if (suit == 0) {
            value++;
        }
        suit++;
        return value;
    };

    auto shuffler_start = shuffler_container.begin();
    auto shuffler_end = shuffler_container.end();
    std::generate(shuffler_start, shuffler_end, deck_generator_lambda);
    shuffle_deck(shuffler_container);

    return new std::list<int>(
            shuffler_container.begin(), shuffler_container.end());
}

int main(int argc, char* argv[])
{
    if (argc != 2) {
        std::cout << "Please provide only a number of trials." << endl;
        return 1;
    }

    auto num_trials = atoi(argv[1]);
    auto total_num_decks = 0;
    auto total_completion_time = 0;
    auto total_num_loops = 0;

    for (int i = 0; i < num_trials; i++) {
        auto deck = generate_shuffled_deck();
        auto result = narcotic_iterations(*deck);
        total_num_loops += result.did_loop;
        total_num_decks += result.num_decks;
        total_completion_time += result.completion_time;
        delete deck;
    }

    auto average_num_decks = total_num_decks / num_trials;
    auto average_completion_time = total_completion_time / num_trials;
    auto average_completion_time_hours =
            average_completion_time / (SECONDS_IN_MINUTE*MINUTES_IN_HOUR);
    auto average_completion_time_minutes = 
            (average_completion_time/SECONDS_IN_MINUTE) % MINUTES_IN_HOUR;
    auto percent_loops = PERCENT * ((double)total_num_loops/num_trials);    

    std::cout << "Average " << average_num_decks << " decks to complete (" <<
            average_completion_time_hours << " hours " <<
            average_completion_time_minutes << " minutes)" << endl;
    std::cout << percent_loops << "% of decks loop" << endl;
}
  • Using char instead of int gives the code a 1% speedup, and makes some sense because the code's numbers range only from 1-52. but it makes it less readable, so I decided not to do it.
  • Yes, I know, this solution isn't object oriented. I think that would have made things more complicated in this case.
\$\endgroup\$
  • \$\begingroup\$ Your second if (did_loop) { check in narcotic_iterations is not doing anything \$\endgroup\$ – MikeMB Apr 21 '15 at 23:19
  • \$\begingroup\$ @MikeMB Oops! I didn't mean to post that. It's a relic from an earlier stage where that condition was checked twice. \$\endgroup\$ – EMBLEM Apr 22 '15 at 0:00
2
\$\begingroup\$

Before critiquing your code, I'd like to compliment you. In general I found your code readable and appreciated that you've broken things into short functions, and your variables were well-named.

Do you really need std::list?

Unless you have a compelling reason to use std::list, you should probably stick to std::vector. std::vector will be better for data locality, and offers random-access iterators. That means that your erase_matching_cards can be made to erase items without needing to traverse any of the data structure. I would expect switching away from std::list to improve performance.

Don't use new

In a few places you use dynamic allocation with new and return a pointer to an object. This creates a burden on the programmer to make sure delete is called appropriately, and is not exception safe. Prefer instead to return by value. The object copies can be elided by the compiler.

Don't use arrays

C-style arrays generally aren't the best data structure for, well, anything. They don't know their own size, and decay to pointers when used as function arguments. At the very least, use std::array instead.

const correctness

Declare variables const wherever you can. This lets the compiler guarantee that variables that aren't supposed to change, can't change. Less moving parts makes your code easier to reason about.

Too much auto

This may be open to some debate, but I think you use auto too much. Sometimes you initialize a container like this:

auto shuffler_container = std::vector<int>(CARDS_IN_DECK);

which isn't necessarily bad, but I find it more readable to use the older declaration style

std::vector<int> shuffler_container(CARDS_IN_DECK);

in cases like this, or where I'm initializing primitive types. Although auto num_decks = 0; and int num_decks = 0; are identical, I find the second to be easier to read. No need to wonder about what the inferred type is. That said, keep using auto in cases where the types are tedious (like iterators), and pair it with const for even more fun!

Edward's example has changed my mind. Your use of auto is fine.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You're right that "too much auto" might be open to debate. For those of us who started programming before C++ existed, the older style is more habitual, but lately I find that that I am slowly being persuaded to use auto more often. For example, see Herb Sutter's talk at CppCon 2014 for reasoned auto advocacy. \$\endgroup\$ – Edward Apr 21 '15 at 18:44
  • \$\begingroup\$ Thanks for answering. I chose std::list for a reason: I need to concatenate collections together, which (I'd assume?) would be a heavy operation under std::vector. As for auto, yeah, sometimes even I think I use it too much. \$\endgroup\$ – EMBLEM Apr 21 '15 at 18:49
  • \$\begingroup\$ @Edward That's an interesting talk. Don't get me wrong; I really like auto, and the auto name = ... style is more similar to a lot of newer languages. I guess I haven't gotten used to seeing it in C++ yet. So yes, that piece of advice is certainly not set in stone. \$\endgroup\$ – Aurelius Apr 21 '15 at 19:16
  • \$\begingroup\$ I just finished some testing. Removing pointers and switching to std::array provided a 20% speedup; list was indeed slightly faster than vector. (According to Valgrind, list allocated 312,660,736 bytes but vector required 3,145,258,600.) For good measure, I tried a deque, which took about 50% longer than either. I'm not seeing the need for const here; can you tell me some examples? \$\endgroup\$ – EMBLEM Apr 21 '15 at 19:24
  • \$\begingroup\$ @EMBLEM It depends on your definition of "need". const won't make your code run faster, but it does allow the compiler to check your code for more errors. So it's not a speed optimization, but a correctness optimization. And generally a best-practice in C++. \$\endgroup\$ – Aurelius Apr 21 '15 at 19:31

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.