Mengapa memisahkan string lebih lambat di C ++ daripada Python?

Saya mencoba mengonversi beberapa kode dari Python ke C ++ dalam upaya untuk mendapatkan sedikit kecepatan dan mempertajam keterampilan C ++ saya yang berkarat. Kemarin saya terkejut ketika implementasi naif membaca baris dari stdin jauh lebih cepat dengan Python daripada C ++ (lihat ini ). Hari ini, saya akhirnya menemukan cara membagi string di C ++ dengan pembatas penggabungan (semantik mirip dengan split python ()), dan sekarang saya mengalami deja vu! Kode C ++ saya membutuhkan waktu lebih lama untuk melakukan pekerjaan itu (meskipun bukan urutan besarnya, seperti yang terjadi pada pelajaran kemarin).

Kode 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('')

Kode 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

Perhatikan bahwa saya mencoba dua implementasi pemisahan yang berbeda. One (split1) menggunakan metode string untuk mencari token dan mampu menggabungkan banyak token serta menangani banyak token (berasal dari sini ). Yang kedua (split2) menggunakan getline untuk membaca string sebagai aliran, tidak menggabungkan pembatas, dan hanya mendukung satu karakter pembatas (yang diposting oleh beberapa pengguna StackOverflow sebagai jawaban untuk pertanyaan pemisahan string).

Saya menjalankan ini beberapa kali dalam berbagai pesanan. Mesin uji saya adalah Macbook Pro (2011, 8GB, Quad Core), bukan itu masalahnya. Saya menguji dengan file teks baris 20 juta dengan tiga kolom terpisah spasi yang masing-masing terlihat mirip dengan ini: "foo.bar 127.0.0.1 home.foo.bar"

Hasil:

$ /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

Apa yang saya lakukan salah? Apakah ada cara yang lebih baik untuk melakukan pemisahan string dalam C ++ yang tidak bergantung pada pustaka eksternal (yaitu, tidak ada dorongan), mendukung penggabungan urutan pembatas (seperti pemisahan python), aman untuk utas (jadi tidak ada strtok), dan yang kinerjanya setidaknya setara dengan python?

Edit 1 / Solusi Parsial ?:

Saya mencoba membuatnya menjadi perbandingan yang lebih adil dengan meminta python mengatur ulang daftar boneka dan menambahkannya setiap kali, seperti yang dilakukan C ++. Ini masih belum persis seperti yang dilakukan kode C ++, tetapi ini sedikit lebih dekat. Pada dasarnya, loop sekarang:

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

Kinerja python sekarang hampir sama dengan implementasi 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

Saya masih terkejut bahwa, meskipun Python begitu dioptimalkan untuk pemrosesan string (seperti yang disarankan Matt Joiner), implementasi C ++ ini tidak akan lebih cepat. Jika ada yang punya ide tentang cara melakukan ini dengan cara yang lebih optimal menggunakan C ++, silakan bagikan kode Anda. (Saya pikir langkah saya selanjutnya akan mencoba menerapkan ini dalam C murni, meskipun saya tidak akan menukar produktivitas pemrogram untuk menerapkan ulang keseluruhan proyek saya di C, jadi ini hanya akan menjadi eksperimen untuk kecepatan pemisahan string.)

Terima kasih untuk semua atas bantuan Anda.

Edit / Solusi Akhir:

Silakan lihat jawaban Alf yang diterima. Karena python menangani string secara ketat dengan referensi dan string STL sering disalin, kinerja lebih baik dengan implementasi vanilla python. Sebagai perbandingan, saya mengumpulkan dan menjalankan data saya melalui kode Alf, dan berikut adalah kinerja pada mesin yang sama dengan semua yang berjalan, pada dasarnya identik dengan implementasi python naif (meskipun lebih cepat daripada implementasi python yang menyetel ulang / menambahkan daftar, seperti ditampilkan di edit di atas):

$ /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

Keluhan kecil saya yang tersisa hanyalah mengenai jumlah kode yang diperlukan untuk mendapatkan C ++ untuk bekerja dalam kasus ini.

Salah satu pelajaran di sini dari masalah ini dan masalah membaca garis stdin kemarin (ditautkan di atas) adalah bahwa seseorang harus selalu membuat tolok ukur daripada membuat asumsi naif tentang kinerja relatif "default" bahasa. Saya menghargai pendidikan.

Terima kasih sekali lagi untuk semua saran Anda!

Sebagai tebakan, string Python adalah referensi yang dihitung sebagai string yang tidak dapat diubah, sehingga tidak ada string yang disalin dalam kode Python, sementara C ++ std::string adalah jenis nilai yang dapat berubah, dan disalin pada peluang terkecil.

Jika tujuannya adalah pemisahan cepat, maka seseorang akan menggunakan operasi substring waktu konstan, yang berarti hanya merujuk pada bagian dari string asli, seperti di Python (dan Java, dan C #…).

Kelas C ++ std::stringmemiliki satu fitur penebusan, meskipun: ini standar , sehingga dapat digunakan untuk meneruskan string dengan aman dan mudah dibawa di mana efisiensi bukanlah pertimbangan utama. Tapi cukup ngobrol. Kode - dan di mesin saya ini tentu saja lebih cepat daripada Python, karena penanganan string Python diimplementasikan di C yang merupakan bagian dari C ++ (he he):

#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

Penafian: Saya harap tidak ada bug. Saya belum menguji fungsionalitasnya, tetapi hanya memeriksa kecepatannya. Tapi saya pikir, meskipun ada satu atau dua bug, mengoreksi itu tidak akan mempengaruhi kecepatan secara signifikan.

Saya tidak memberikan solusi yang lebih baik (setidaknya dari segi performa), tetapi beberapa data tambahan yang mungkin menarik.

Menggunakan strtok_r(varian reentrant dari strtok):

void splitc1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(str.size() + 1);
    strcpy(cpy, str.c_str());

    for(token = strtok_r(cpy, delimiters.c_str(), &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters.c_str(), &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

Selain itu menggunakan string karakter untuk parameter, dan fgetsuntuk input:

void splitc2(vector<string> &tokens, const char *str,
        const char *delimiters) {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(strlen(str) + 1);
    strcpy(cpy, str);

    for(token = strtok_r(cpy, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

Dan, dalam beberapa kasus, di mana pemusnahan string input dapat diterima:

void splitc3(vector<string> &tokens, char *str,
        const char *delimiters) {
    char *saveptr;
    char *token;

    for(token = strtok_r(str, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }
}

Pengaturan waktu untuk ini adalah sebagai berikut (termasuk hasil saya untuk varian lain dari pertanyaan dan jawaban yang diterima):

split1.cpp:  C++   : Saw 20000000 lines in 31 seconds.  Crunch speed: 645161
split2.cpp:  C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444
split.py:    Python: Saw 20000000 lines in 33 seconds.  Crunch Speed: 606060
split5.py:   Python: Saw 20000000 lines in 35 seconds.  Crunch Speed: 571428
split6.cpp:  C++   : Saw 20000000 lines in 18 seconds.  Crunch speed: 1111111

splitc1.cpp: C++   : Saw 20000000 lines in 27 seconds.  Crunch speed: 740740
splitc2.cpp: C++   : Saw 20000000 lines in 22 seconds.  Crunch speed: 909090
splitc3.cpp: C++   : Saw 20000000 lines in 20 seconds.  Crunch speed: 1000000

Seperti yang bisa kita lihat, solusi dari jawaban yang diterima masih paling cepat.

Bagi siapa pun yang ingin melakukan tes lebih lanjut, saya juga memasang repo Github dengan semua program dari pertanyaan, jawaban yang diterima, jawaban ini, dan tambahan Makefile dan skrip untuk menghasilkan data pengujian: https: // github. com / tobbez / string-splitting .

Saya menduga bahwa ini karena cara std::vectordiubah ukurannya selama proses pemanggilan fungsi push_back (). Jika Anda mencoba menggunakan std::listatau std::vector::reserve()menyediakan ruang yang cukup untuk kalimat, Anda akan mendapatkan kinerja yang jauh lebih baik. Atau Anda bisa menggunakan kombinasi keduanya seperti di bawah ini untuk split1 ():

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);
    list<string> token_list;

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the list
        token_list.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);
    }
    tokens.assign(token_list.begin(), token_list.end());
}

EDIT : Hal yang jelas lainnya saya lihat adalah bahwa variabel Python dummyakan ditugaskan setiap kali tetapi tidak dimodifikasi. Jadi ini bukan perbandingan yang adil terhadap C ++. Anda harus mencoba memodifikasi kode Python Anda menjadi dummy = []untuk menginisialisasi dan kemudian melakukannyadummy += line.split() . Dapatkah Anda melaporkan runtime setelah ini?

EDIT2 : Untuk membuatnya lebih adil, Anda dapat memodifikasi loop sementara dalam kode C ++ menjadi:

    while(cin) {
        getline(cin, input_line);
        std::vector<string> spline; // create a new vector

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

        count++;
    };

Saya pikir kode berikut lebih baik, menggunakan beberapa fitur C ++ 17 dan C ++ 14:

// These codes are un-tested when I write this post, but I'll test it
// When I'm free, and I sincerely welcome others to test and modify this
// code.

// C++17
#include <istream>     // For std::istream.
#include <string_view> // new feature in C++17, sizeof(std::string_view) == 16 in libc++ on my x86-64 debian 9.4 computer.
#include <string>
#include <utility>     // C++14 feature std::move.

template <template <class...> class Container, class Allocator>
void split1(Container<std::string_view, Allocator> &tokens, 
            std::string_view str,
            std::string_view delimiter = " ") 
{
    /* 
     * The model of the input string:
     *
     * (optional) delimiter | content | delimiter | content | delimiter| 
     * ... | delimiter | content 
     *
     * Using std::string::find_first_not_of or 
     * std::string_view::find_first_not_of is a bad idea, because it 
     * actually does the following thing:
     * 
     *     Finds the first character not equal to any of the characters 
     *     in the given character sequence.
     * 
     * Which means it does not treeat your delimiters as a whole, but as
     * a group of characters.
     * 
     * This has 2 effects:
     *
     *  1. When your delimiters is not a single character, this function
     *  won't behave as you predicted.
     *
     *  2. When your delimiters is just a single character, the function
     *  may have an additional overhead due to the fact that it has to 
     *  check every character with a range of characters, although 
     * there's only one, but in order to assure the correctness, it still 
     * has an inner loop, which adds to the overhead.
     *
     * So, as a solution, I wrote the following code.
     *
     * The code below will skip the first delimiter prefix.
     * However, if there's nothing between 2 delimiter, this code'll 
     * still treat as if there's sth. there.
     *
     * Note: 
     * Here I use C++ std version of substring search algorithm, but u
     * can change it to Boyer-Moore, KMP(takes additional memory), 
     * Rabin-Karp and other algorithm to speed your code.
     * 
     */

    // Establish the loop invariant 1.
    typename std::string_view::size_type 
        next, 
        delimiter_size = delimiter.size(),  
        pos = str.find(delimiter) ? 0 : delimiter_size;

    // The loop invariant:
    //  1. At pos, it is the content that should be saved.
    //  2. The next pos of delimiter is stored in next, which could be 0
    //  or std::string_view::npos.

    do {
        // Find the next delimiter, maintain loop invariant 2.
        next = str.find(delimiter, pos);

        // Found a token, add it to the vector
        tokens.push_back(str.substr(pos, next));

        // Skip delimiters, maintain the loop invariant 1.
        //
        // @ next is the size of the just pushed token.
        // Because when next == std::string_view::npos, the loop will
        // terminate, so it doesn't matter even if the following 
        // expression have undefined behavior due to the overflow of 
        // argument.
        pos = next + delimiter_size;
    } while(next != std::string_view::npos);
}   

template <template <class...> class Container, class traits, class Allocator2, class Allocator>
void split2(Container<std::basic_string<char, traits, Allocator2>, Allocator> &tokens, 
            std::istream &stream,
            char delimiter = ' ')
{
    std::string<char, traits, Allocator2> item;

    // Unfortunately, std::getline can only accept a single-character 
    // delimiter.
    while(std::getline(stream, item, delimiter))
        // Move item into token. I haven't checked whether item can be 
        // reused after being moved.
        tokens.push_back(std::move(item));
}

Pilihan wadah:

1. std::vector.

   Dengan asumsi ukuran awal dari array internal yang dialokasikan adalah 1, dan ukuran akhirnya adalah N, Anda akan mengalokasikan dan membatalkan alokasi untuk log2 (N) kali, dan Anda akan menyalin (2 ^ (log2 (N) + 1) - 1) = (2N - 1) kali. Seperti yang ditunjukkan di Apakah kinerja yang buruk dari std :: vector karena tidak memanggil realoc beberapa kali logaritmik? , ini dapat memiliki kinerja yang buruk jika ukuran vektor tidak dapat diprediksi dan bisa sangat besar. Tapi, jika Anda bisa memperkirakan ukurannya, ini tidak akan menjadi masalah.

2. std::list.

   Untuk setiap push_back, waktu yang dikonsumsi adalah konstan, tetapi mungkin akan membutuhkan lebih banyak waktu daripada std :: vector pada masing-masing push_back. Menggunakan kumpulan memori per utas dan pengalokasi khusus dapat meredakan masalah ini.

3. std::forward_list.

   Sama seperti std :: list, tetapi menggunakan lebih sedikit memori per elemen. Memerlukan kelas pembungkus agar berfungsi karena kurangnya push_back API.

4. std::array.

   Jika Anda dapat mengetahui batas pertumbuhan, maka Anda dapat menggunakan std :: array. Penyebabnya, Anda tidak dapat menggunakannya secara langsung, karena tidak memiliki push_back API. Tetapi Anda dapat menentukan pembungkus, dan menurut saya ini adalah cara tercepat di sini dan dapat menghemat memori jika perkiraan Anda cukup akurat.

5. std::deque.

   Opsi ini memungkinkan Anda untuk menukar memori dengan kinerja. Tidak akan ada (2 ^ (N + 1) - 1) kali salinan elemen, hanya alokasi N kali, dan tidak ada deallocation. Selain itu, Anda akan memiliki waktu akses acak yang konstan, dan kemampuan untuk menambahkan elemen baru di kedua ujungnya.

Menurut std :: deque-cppreference

Di sisi lain, deques biasanya memiliki biaya memori minimal yang besar; deque yang hanya menampung satu elemen harus mengalokasikan array internal penuhnya (misalnya 8 kali ukuran objek pada 64-bit libstdc ++; 16 kali ukuran objek atau 4096 byte, mana saja yang lebih besar, pada 64-bit libc ++)

atau Anda dapat menggunakan kombinasi ini:

1. std::vector< std::array<T, 2 ^ M> >

   Ini mirip dengan std :: deque, perbedaannya hanya wadah ini tidak mendukung untuk menambahkan elemen di depan. Tetapi ini masih lebih cepat dalam kinerjanya, karena fakta bahwa itu tidak akan menyalin std :: array yang mendasari untuk (2 ^ (N + 1) - 1) kali, itu hanya akan menyalin array pointer untuk (2 ^ (N - M + 1) - 1) kali, dan mengalokasikan array baru hanya jika arus sudah penuh dan tidak perlu membatalkan alokasi apa pun. Omong-omong, Anda bisa mendapatkan waktu akses acak yang konstan.

2. std::list< std::array<T, ...> >

   Sangat meringankan tekanan framentation memori. Ini hanya akan mengalokasikan array baru ketika arus sudah penuh, dan tidak perlu menyalin apa pun. Anda masih harus membayar harga untuk penunjuk tambahan yang sebanding dengan kombo 1.

3. std::forward_list< std::array<T, ...> >

   Sama seperti 2, tetapi harganya sama dengan memori kombo 1.

Anda membuat asumsi yang salah bahwa implementasi C ++ yang Anda pilih tentu lebih cepat daripada implementasi Python. Penanganan string dengan Python sangat dioptimalkan. Lihat pertanyaan ini untuk lebih lanjut: Mengapa operasi std :: string berkinerja buruk?

Jika Anda mengambil implementasi split1 dan mengubah tanda tangan agar lebih cocok dengan split2, dengan mengubah ini:

void split1(vector<string> &tokens, const string &str, const string &delimiters = " ")

untuk ini:

void split1(vector<string> &tokens, const string &str, const char delimiters = ' ')

Anda mendapatkan perbedaan yang lebih dramatis antara split1 dan split2, dan perbandingan yang lebih adil:

split1  C++   : Saw 10000000 lines in 41 seconds.  Crunch speed: 243902
split2  C++   : Saw 10000000 lines in 144 seconds.  Crunch speed: 69444
split1' C++   : Saw 10000000 lines in 33 seconds.  Crunch speed: 303030

void split5(vector<string> &tokens, const string &str, char delim=' ') {

    enum { do_token, do_delim } state = do_delim;
    int idx = 0, tok_start = 0;
    for (string::const_iterator it = str.begin() ; ; ++it, ++idx) {
        switch (state) {
            case do_token:
                if (it == str.end()) {
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                    return;
                }
                else if (*it == delim) {
                    state = do_delim;
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                }
                break;

            case do_delim:
                if (it == str.end()) {
                    return;
                }
                if (*it != delim) {
                    state = do_token;
                    tok_start = idx;
                }
                break;
        }
    }
}

Saya menduga bahwa ini terkait dengan buffering pada sys.stdin dengan Python, tetapi tidak ada buffering dalam implementasi C ++.

Lihat posting ini untuk detail tentang cara mengubah ukuran buffer, lalu coba perbandingan lagi: Menetapkan ukuran buffer yang lebih kecil untuk sys.stdin?