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

这似乎运行得很快。当使用大约1.2E6个测试用例的测试文件并使用g++ -O3编译时，运行time ./reverse < in > /dev/null需要约3.5秒。

因此，我创建了一个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()))))

然而，当我在pypy下运行它时，使用time pypy reverse.py < in > /dev/null只需要约1.95秒。

理论上说，由于pypy是用C++编写的，C++不应该更快吗？如果是这样，如何优化此代码以使其更快？

- luke

---

你真的不应该将“_”作为变量名，即使仅从风格角度考虑也是如此，但以“_”或“__”开头的变量名对某些编译器来说通常有特殊含义。 - PherricOxide

@PherricOxide 下划线后跟大写字母的标识符和包含双下划线的标识符都保留给实现。这适用于所有编译器。 - Captain Obvlious

如果你想要真正好的性能，就放弃使用C++的IO和字符串操作。 - Karoly Horvath

但是这个问题不需要“io stuff”和涉及“字符串”的操作吗？我怎么能解决它呢？ - luke

普通的 C 语言，char*，malloc... - Karoly Horvath

Answer 1

我认为你的C++代码在连接字符串时进行了相当多的内存复制（大多数std::string实现将整个字符串连续地保存在内存中）。 我认为以下代码可以在不复制的情况下完成此操作，但我没有进行过多的测试。 至于为什么Python表现得相当好，我不完全确定。

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

- Jonesinator

---

当使用g++ -O3编译时，实际上在运行time ./reverse < in > /dev/null时似乎会变慢，因为它需要大约4.5秒。 - luke

Answer 2

一种简单的非复制/非分配的标记化程序是可怕的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++输出相匹配

- Cubbi

---

哇！1.2秒。真快！我不知道std::strtok，但它肯定在这方面表现良好。谢谢。另外，我认为我的C++和Python代码做了同样的事情，它们有什么区别？ - luke

@luke Python在每行结尾没有打印额外的空格。 - Cubbi

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

- Kevin

---

尝试编译您的代码时，我收到以下错误信息：`error: ‘ss’在此作用域中未声明。 - luke

#include <sstream> 对此感到抱歉 - Kevin