3

古い 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かかります。3.5g++ -O3

ベンチマークとして、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++ はそれほど高速または高速であるべきではありません。

4

3 に答える 3

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;
}
于 2013-07-02T22:01:24.653 に答える
-2

2 つのバッファーと多数の連結を使用する代わりに、アルゴリズムとイテレーター ライブラリを利用して、すべてをより簡単に行うことができます。どれくらい高速になるかはわかりませんが (かなり高速だと思いますが)、はるかにコンパクトです。

#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;
}
于 2013-07-02T22:02:17.903 に答える