How can I optimise this C++?

Question

I am trying to practice C++ by doing some old Google Code Jam problems. A relatively simple one I found is to reverse the words in a string. It can be found here https://code.google.com/codejam/contest/351101/dashboard#s=p1

So far I have:

#include<iostream>
using namespace std;

int main(){
    int n = 0;
    cin >> n;


    string rev = "";
    string buf = "";

    string data = "";
    getline(cin, data);

    for(int _ = 0; _ < n; _++){
        getline(cin, data);

        rev = "";
        buf = "";
        for(char& c : data) {
            buf += c;
            if(c == ' '){
                rev = buf + rev;
                buf = "";
            }
        }

        cout << "Case #" << _ + 1 << ": " << buf << " " << rev << endl;
    }

    return 0;
}

Which seems to run pretty fast. When running time ./reverse < in > /dev/null with a test file of around 1.2E6 cases it takes around 3.5 seconds when compiled with g++ -O3.

So as a benchmark I created a solution in python

#!/usr/bin/env python
from sys import stdin, stdout
stdout.writelines(map(lambda n: "Case #%d: %s\n" % (n + 1, ' '.join(stdin.readline().split()[::-1])), xrange(int(stdin.readline()))))

However when I run it under pypy with time pypy reverse.py < in > /dev/null it takes only about 1.95 seconds.

In theory as pypy is written in C++ shouldn't C++ be as fast or faster and if so how could this code be optimised to be faster ?

Answer 1

One simple non-copying/non-allocating tokenizer is the abominable std::strtok

The following beats your python program in my tests

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstring>

int main()
{
    std::cout.sync_with_stdio(false); // we don't need C in the picture

    std::string line;
    getline(std::cin, line);
    int num_cases = stoi(line);

    std::vector<char*> words;
    for(int n = 0; getline(std::cin, line) && n < num_cases; ++n)
    {   
        words.clear();
        char* p = std::strtok(&line[0], " ");
        while (p) {
            words.push_back(p);
            p = std::strtok(nullptr, " ");
        }
        std::cout << "Case #" << n + 1 << ": ";
        reverse_copy(words.begin(), words.end(),
                     std::ostream_iterator<char*>(std::cout, " "));
        std::cout << '\n'; // never std::endl!
    }
}   

PS: your C++ and python outputs don't match exactly; this program matches your C++ output

Answer 2

I think your C++ code is doing quite a few memory copies when you concatenate strings (most implementations of std::string keep the entire string contiguous in memory.) I think the following code does this without copies, but I did not test it much. As to why the python performs quite well, I'm not entirely sure.

#include<iostream>

int main()
{
    size_t numCases;
    std::cin >> numCases;
    std::cin.ignore();

    for( size_t currentCase = 1; currentCase <= numCases; ++currentCase )
    {
        std::cout << "Case #" << currentCase << ": ";

        std::string line;
        getline(std::cin, line);
        size_t wordEnd = line.length() - 1;
        size_t lastSpace = std::string::npos;
        for ( int pos = wordEnd - 1; pos >= 0; --pos )
        {
            if ( line[pos] == ' ' )
            {
                for ( int prt = pos + 1; prt <= wordEnd; ++prt )
                    std::cout << line[prt];
                std::cout << ' ';
                lastSpace = pos;
                wordEnd = pos - 1;
                --pos;
            }
        }
        for ( int prt = 0; prt < lastSpace; ++prt )
            std::cout << line[prt];

        std::cout << std::endl;
    }

    return 0;
}

Answer 3

Instead of using two buffers and lots of concatenation, you could leverage off of the algorithms and iterator libraries to do it all much simpler. I'm not sure how much faster it would be (though I would guess quite a but), but it is also much more compact.

#include<iostream>
#include<algorithm>
#include<iterator>
#include<sstream>
using namespace std;

int main(){
    int n = 0;
    cin >> n;
    string data = "";
    getline(cin, data);
    for(int _ = 0; _ < n; _++){
        getline(cin, data);
        stringstream ss(data);
        reverse(istream_iterator<string>(ss), istream_iterator<string>());
        cout << "Case #" << _ + 1 << ": " << ss.str() << endl;
    }
    return 0;
}