[解決済み] なぜC++はPythonより文字列の分割が遅いのですか？

質問

私は、少しスピードを上げ、私の錆びたC++のスキルを磨くために、いくつかのコードをPythonからC++に変換しようとしています。 昨日、stdinから行を読む素朴な実装が、C++よりもPythonの方がはるかに速かったので、私はショックを受けました(参照) この ). 今日、私はついにC++で文字列をマージデリミタ（Pythonのsplit()と似たようなセマンティクス）で分割する方法を見つけ出し、今デジャヴを経験しています！私のC++のコードは、仕事をするのにはるかに時間がかかります（しかし、それはPythonのコードに似ています）。 私の C++ コードは、作業を行うためにはるかに時間がかかります (ただし、昨日のレッスンの場合のように、1 桁多くではありません)。

Pythonのコードです。

#!/usr/bin/env python
from __future__ import print_function                                            
import time
import sys

count = 0
start_time = time.time()
dummy = None

for line in sys.stdin:
    dummy = line.split()
    count += 1

delta_sec = int(time.time() - start_time)
print("Python: Saw {0} lines in {1} seconds. ".format(count, delta_sec), end='')
if delta_sec > 0:
    lps = int(count/delta_sec)
    print("  Crunch Speed: {0}".format(lps))
else:
    print('')

C++のコードです。

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the vector
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
}

void split2(vector<string> &tokens, const string &str, char delim=' ') {
    stringstream ss(str); //convert string to stream
    string item;
    while(getline(ss, item, delim)) {
        tokens.push_back(item); //add token to vector
    }
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp

2つの異なるsplitの実装を試したことに注意してください。 ひとつは文字列メソッドを使ってトークンを検索し、複数のトークンをマージしたり、多数のトークンを扱えるようにしたものです（これは ここで ). 2つ目(split2)はgetlineを使って文字列をストリームとして読み込み、区切り文字をマージせず、1つの区切り文字のみをサポートします(こちらはStackOverflowの複数のユーザが文字列分割の質問に対する答えとして投稿したものです)。

私はこれをさまざまな順序で複数回実行しました。 私のテスト マシンは Macbook Pro (2011、8GB、Quad Core) ですが、それはあまり重要ではありません。 私は、次のような 3 つのスペースで区切られた列を持つ 20M 行のテキスト ファイルでテストしています: "foo.bar 127.0.0.1 home.foo.bar"

結果が出ました。

$ /usr/bin/time cat test_lines_double | ./split.py
       15.61 real         0.01 user         0.38 sys
Python: Saw 20000000 lines in 15 seconds.   Crunch Speed: 1333333
$ /usr/bin/time cat test_lines_double | ./split1
       23.50 real         0.01 user         0.46 sys
C++   : Saw 20000000 lines in 23 seconds.  Crunch speed: 869565
$ /usr/bin/time cat test_lines_double | ./split2
       44.69 real         0.02 user         0.62 sys
C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444

私は何を間違えているのでしょうか？ C++で文字列分割を行う場合、外部ライブラリに依存せず（つまりboostなし）、区切り文字列のマージに対応し（pythonのsplitのように）、スレッドセーフで（つまりstrotokなし）、少なくともpythonと同程度の性能を持つ良い方法はないでしょうか。

編集1 / 部分的な解決策？

C++が行うように、pythonにダミーリストをリセットして毎回それに追加させることで、より公平な比較になるように試みました。これはまだC++コードが行っていることと正確に一致しませんが、少しは近づきました。基本的に、ループは今

for line in sys.stdin:
    dummy = []
    dummy += line.split()
    count += 1

pythonの性能はsplit1のC++実装とほぼ同じになりました。

/usr/bin/time cat test_lines_double | ./split5.py
       22.61 real         0.01 user         0.40 sys
Python: Saw 20000000 lines in 22 seconds.   Crunch Speed: 909090

Pythonが（Matt Joinerが提案したように）文字列処理にとても最適化されているとしても、これらのC++の実装がより速くならないことに、私はまだ驚いています。 もし誰かがC++を使ってより最適な方法でこれを行う方法についてアイデアをお持ちでしたら、あなたのコードを共有してください。 (私の次のステップは、純粋な C でこれを実装しようとすることだと思いますが、私のプロジェクト全体を C で再実装するためにプログラマの生産性をトレードオフするつもりはないので、これは単なる文字列分割速度の実験になります)。

皆さんの協力に感謝します。

最終的な編集・解決方法です。

Alfの受理済み回答を参照してください。 Pythonは厳密に参照によって文字列を扱い、STL文字列はしばしばコピーされるので、パフォーマンスはpythonのバニラ実装でより良くなります。 比較のために、私はAlfのコードを通して私のデータをコンパイルして実行しました。そして、ここに他のすべての実行と同じマシン上のパフォーマンスがあります。本質的に素朴なpythonの実装と同じです(ただし、上記の編集で示されているように、リストをリセット/追加するpythonの実装よりも高速です)。

$ /usr/bin/time cat test_lines_double | ./split6
       15.09 real         0.01 user         0.45 sys
C++   : Saw 20000000 lines in 15 seconds.  Crunch speed: 1333333

私の唯一の小さな不満は、このケースで C++ を実行させるために必要なコードの量についてです。

この問題と昨日の stdin 行読み取り問題 (上記リンク) から得られる教訓の 1 つは、言語の相対的な "default" パフォーマンスについて素朴な仮定をする代わりに、常にベンチマークを行うべきであるということです。 私は教育に感謝します。

提案をしてくれたみなさん、本当にありがとうございました!

どのように解決するのですか？

推測ですが、Pythonの文字列は参照カウントされた不変の文字列なので、Pythonのコード内で文字列がコピーされることはありませんが、C++の場合は std::string はmutableな値型であり、最小の機会でコピーされます。

もし高速な分割が目的なら、定時間部分文字列操作を使うことになり、それはつまり 参照 を参照するだけです。

C++の std::string クラスには、ひとつだけ救いのある特徴があります。 標準 であるため、効率が重要視されない場所でも安全に文字列を渡すことができ、ポータブルに使用できます。しかし、おしゃべりはもう十分です。Pythonの文字列処理はC++のサブセットであるCで実装されているからです(彼は彼です)。

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

class StringRef
{
private:
    char const*     begin_;
    int             size_;

public:
    int size() const { return size_; }
    char const* begin() const { return begin_; }
    char const* end() const { return begin_ + size_; }

    StringRef( char const* const begin, int const size )
        : begin_( begin )
        , size_( size )
    {}
};

vector<StringRef> split3( string const& str, char delimiter = ' ' )
{
    vector<StringRef>   result;

    enum State { inSpace, inToken };

    State state = inSpace;
    char const*     pTokenBegin = 0;    // Init to satisfy compiler.
    for( auto it = str.begin(); it != str.end(); ++it )
    {
        State const newState = (*it == delimiter? inSpace : inToken);
        if( newState != state )
        {
            switch( newState )
            {
            case inSpace:
                result.push_back( StringRef( pTokenBegin, &*it - pTokenBegin ) );
                break;
            case inToken:
                pTokenBegin = &*it;
            }
        }
        state = newState;
    }
    if( state == inToken )
    {
        result.push_back( StringRef( pTokenBegin, &*str.end() - pTokenBegin ) );
    }
    return result;
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        //spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        //split2(spline, input_line);

        vector<StringRef> const v = split3( input_line );
        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp -std=c++0x

免責事項：バグがないことを祈ります。機能的なテストはしていませんが、スピードのチェックだけはしています。しかし、たとえ1つや2つのバグがあったとしても、それを修正することで速度に大きな影響を与えることはないと思います。