如何优化这个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; 
}