如何優化這個C++？

Question

我想通過做一些舊的Google Code Jam問題來練習C++。我找到的一個比較簡單的方法是將字串中的單詞反轉。它可以在這裏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時，使用g++ -O3進行編譯時，大約需要3.5秒。

所以作爲基準我創建了蟒蛇

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

的解決方案。然而，當我與time pypy reverse.py <in> /dev/null運行pypy下它只需約1.95秒。

從理論上講，pypy是用C++編寫的，不應該C++的速度要快或者更快，如果是的話，這個代碼怎麼會被優化得更快？

Answer 1

一個簡單的非複製/非分配標記生成器是在惡劣的std::strtok

下擊敗你的Python程序在我的測試中

#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輸出別完全匹配;這個程序匹配你的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; 
}