Как я могу оптимизировать этот C++?

Question

Я пытаюсь практиковать C++, выполняя некоторые старые проблемы с Google Code Jam. Относительно простой я нашел, чтобы обратить слова в строку. Его можно найти здесь https://code.google.com/codejam/contest/351101/dashboard#s=p1

До сих пор у меня есть:

#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; 
} 

Который, кажется, бежит довольно быстро. При запуске time ./reverse <in> /dev/null с тестовым файлом около 1.2E6 случаев он занимает около 3.5 секунд при компиляции с g++ -O3.

Так как эталон я создал решение в питона

#!/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())))) 

Однако, когда я запускаю его под pypy с time pypy reverse.py <in> /dev/null это занимает около 1.95 секунд.

В теории как pypy написано на C++, не должно быть C++ так быстро или быстро, и если да, как можно оптимизировать этот код для ускорения?

Answer 1

Один простой без копирования/без выделения токенизатор является отвратительным std::strtok

Следующая бьет вашу питона программу в моих тестах

#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: ваш C++ и Python выходы Дон» t соответствует точно; эта программа соответствует вашему выходу на C++

Answer 2

Я думаю, что ваш код на C++ делает довольно много копий памяти при конкатенации строк (большинство реализаций std :: string сохраняют всю цепочку непрерывной в памяти.) Я думаю, что следующий код делает это без копий, но я сделал не испытывать его много. Что касается того, почему питон работает достаточно хорошо, я не совсем уверен.

#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

Вместо использования двух буферов и много конкатенации, вы могли бы использовать от алгоритмов и библиотек итераторов, чтобы сделать все это гораздо проще. Я не уверен, насколько быстрее это будет (хотя я бы догадался довольно, но), но он также намного более компактен.

#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; 
}