How can I speed up this solution to the "Rock-Paper-Scissors Tournament"

Question

As I have recently been selected to participate in my country's final preselection to the IOI -- this took me aback -- I have decided to get a bit more serious about competetitive programming.

The Rock-Paper-Scissors Tournament is an old question form the Waterloo Programming Contest 2005-09-17, available on kattis.

What it asks you to do is:

You first get two numbers n and k for the number of participants and the number of games played in the tournament. And then you get k lines detailing every one of those games. Using this data you have to output the winrate for each contestant in three decimal places. A player that has not played a single game throughout the tournament should get a '-' as output.

A zero for the number of players terminates the program.

2 4
1 rock 2 paper
1 scissors 2 paper
1 rock 2 rock
2 rock 1 scissors
2 1
1 rock 2 paper
0

Should give the output

0.333
0.667

0.000
1.000

As far as I know my solution, which follows below, solves this problem perfectly, but, sadly, it is too slow.

My question is, does anyone see where I made a suboptimal choice in the datatype I used or how I calculated a result that causes my program to fail to beat the timelimit? I hope that understanding what I could have done better here allows me to become a better programmer in the future.

#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>


std::unordered_map< std::string, std::unordered_map<std::string, int> >
result(
{
   {
       "rock",
        {
            {"rock", 0},
            {"paper", -1},
            {"scissors", 1}
        }
   },
   {
        "paper",
        {
            {"rock", 1},
            {"paper", 0},
            {"scissors", -1}
        }
   },
   {

        "scissors",
        {
            {"rock", -1},
            {"paper", 1},
            {"scissors", 0}
        }
   }
});



int main() {
    int n,
        k,
        p1,
        p2;

    std::string m1,
                m2;


    while (1) {
        std::cin >> n;

        if (n == 0) {
            break;
        }

        std::cin >> k;

        std::vector<int> wins(n, 0);
        std::vector<int> losses(n, 0);

        while (k--) {
            std::cin >> p1;
            std::cin >> m1;
            std::cin >> p2;
            std::cin >> m2;

            int v = result[m1][m2];

            if (v == 1) {
                wins[p1-1]++;
                losses[p2-1]++;
            } else if (v == -1) {
                losses[p1-1]++;
                wins[p2-1]++;
            }
        }


        std::cout << std::fixed;
        std::cout << std::setprecision(3);
        for (int i = 0; i < n; i++) {
            float numOfWins = (float)wins[i];
            float numOfGames = (float)(wins[i]+losses[i]);
            if (numOfGames != 0) {
                std::cout << numOfWins/numOfGames << std::endl;
            } else {
                std::cout << '-' << std::endl;
            }
        }
        std::cout << std::endl;

    }
    return 0;
}

Answer 1

The choice of data structure is fundamentally sound (but more on that later).

The first thing that jumped out to me in your code is actually not directly related to performance: you could drastically improve readability by declaring variables where you use them rather than at the beginning, and by assigning better names. Don’t be afraid that declaring variables inside a loop will lead to performance degradation! First off, in most cases it doesn’t. And secondly, where it does the difference in performance is usually negligible, and will not contribute sufficiently to be noticed. If, and only if, that’s not the case does it make sense to change this.

Some more points regarding readability:

1. Since you’re already using uniform initialisation, use {…} instead of (…) in your initialisation of result. Writing ({…}) is pretty unusual and consequently tripped me up.
2. Since C++11 there’s no need to put a space between template argument list terminators (> > vs. >>).
3. Don’t use integer literals in place of boolean values: don’t write while (1), write while (true).
4. Your (C-style) casts to float are unnecessary. Remove them.
5. Make more variables const — in particular result! You don’t want to accidentally modify that. You will also need to change your lookup to using find then, unfortunately.

Now on to performance improvements. There are effectively two things to improve.

First off, two things about unordered_map:

1. Although the choice of this structure is algorithmically correct, C++’s standard library specification of it is poor due to a fault in the standard wording, which forbids efficient implementations. The structure is therefore a cache killer.
2. In your case a general string hash is overkill: you only need to check the first letter of each word to determine which move was played.

You could exploit the second point by providing a custom Hash template argument to std::unordered_map which only returns the first character. But given the first point, I would suggest ditching std::unordered_map altogether and just using a 256×256 array as a lookup table (or, if you want to optimise space, subtract some common value from the first character or find a perfect hash function for the letters “r”, “p” & “s”).¹

And now something more mundane, since the execution time of your program is at any rate completely dominated by IO: std::cin and std::cout are by default synchronised with C’s buffered standard IO, which makes them excruciatingly slow. To fix this, put std::ios_base::sync_with_stdio(false) a the beginning of your main function. Similarly, untie standard output from standard input via std::cin.tie(nullptr). Secondly, replace std::endl with "\n". std::endl flushes the stream each time, which is slow. It’s also unnecessary to set the stream format manipulators in every loop (although I don’t expect this to change the performance).

— It’s worth noting that none of that had a measurable impact on the performance of the code on my machine. In fact, formatted input via std::cin totally dominates the runtime. This is surprising and disappointing (because there’s no reason for it: it hints at a broken standard library implementation). Using scanf is significantly faster, which should not happen. Of course using scanf also requires changing the type of m1 and m2 (you can use a static buffer of size sizeof "scissors"). It’s worth emphasising that it’s really IO that’s slow, and not the std::strings: simply replacing the std::strings with static buffers has almost no perceptible impact on runtime (likely due to SSO). It’s really std::cin vs scanf.

---

¹ We’re in luck, and the character codes of “r”, “p” and “s” in common encodings differ in the lower two bits, so that we only need a 4×4 lookup and minimal recoding:

static int const result[4][4] = {
//    p      r   s
    { 0, 0,  1, -1},     // paper
    { 0, 0,  0,  0},
    {-1, 0,  0,  1},     // rock
    { 1, 0, -1,  0}      // scissors
};

…

int const winner = result[move1[0] & 3][move2[0] & 3];

But of course given what I said about the IO bottleneck that’s completely unnecessary obfuscation.

Answer 2

Using Konrad's recomendations.

Did some more work. Now it runs in 0.03 second on the site. Rock Paper Scissors Info Currently at position 7 using C++ streams.

#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <locale>

static int const result[4][4] = {
    //    p      r   s
    { 0, 0,  1, -1},     // paper
    { 0, 0,  0,  0},
    {-1, 0,  0,  1},     // rock
    { 1, 0, -1,  0}      // scissors
};


class FastInt
{
    int&    val;
    public:
        FastInt(int& v): val(v) {}

        friend std::istream& operator>>(std::istream& str, FastInt const& data)
        {
            auto buf = str.rdbuf();

            int c;
            while (std::isspace(c = buf->sbumpc()))
            {}

            data.val = c - '0';
            while (std::isdigit(c = buf->sbumpc())) {
                data.val = (data.val * 10) + (c - '0');
            }

            return str;
        }
};

class FastString
{
    char*   val;
    public:
        FastString(char* v): val(v) {}

        friend std::istream& operator>>(std::istream& str, FastString const& data)
        {
            auto buf = str.rdbuf();

            int c;
            while (std::isspace(c = buf->sbumpc()))
            {}

            data.val[0] = c;
            int loop = 1;
            for (;!std::isspace(c = buf->sbumpc()); ++loop) {
                data.val[loop] = c;
            }
            data.val[loop] = '\0';

            return str;
        }
};

int main()
{
    //std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << std::fixed
              << std::setprecision(3);

    struct T {
        int wins = 0;
        int loss = 0;
    };

    char lineBreak[] = "\0";
    while (true)
    {
        int n = 0;
        std::cin >> FastInt(n);

        if (n == 0) {
            break;
        }

        int k;
        if (std::cin >> FastInt(k))
        {
            std::vector<T> games(n);

            std::cout << lineBreak;
            lineBreak[0] = '\n';

            for (int gameCount = (k * n * (n -1))/2; gameCount; --gameCount)
            {
                int         p1;
                int         p2;
                char        n1[20];
                char        n2[20];
                if (std::cin >> FastInt(p1) >> FastString(n1) >> FastInt(p2) >> FastString(n2))
                {
                    p1--;
                    p2--;

                    int v = result[n1[0] & 3][n2[0] & 3];

                    if (v != 0)
                    {
                        games[(v == 1) ? p1 : p2].wins++;
                        games[(v == 1) ? p2 : p1].loss++;
                    }
                }
            }

            for (auto const& game: games)
            {
                int numOfWins  = game.wins;
                int numOfGames = game.wins + game.loss;
                if (numOfGames != 0) {
                    std::cout << (1.0 * numOfWins / numOfGames) << "\n";
                } else {
                    std::cout << "-\n";
                }
            }
        }
    }
    //std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
    //std::cerr << "Time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "\n";
}