Dlaczego dzielenie łańcucha jest wolniejsze w C ++ niż w Pythonie?

94

Próbuję przekonwertować kod z Pythona na C ++, starając się przyspieszyć i wyostrzyć moje zardzewiałe umiejętności C ++. Wczoraj byłem zszokowany, gdy naiwna implementacja odczytu wierszy ze stdin była znacznie szybsza w Pythonie niż C ++ (zobacz to ). Dzisiaj w końcu odkryłem, jak podzielić ciąg w C ++ za pomocą scalania ograniczników (podobna semantyka do metody split () w Pythonie) i teraz doświadczam deja vu! Mój kod C ++ zajmuje dużo więcej czasu, aby wykonać swoją pracę (choć nie o rząd wielkości więcej, jak to miało miejsce w przypadku wczorajszej lekcji).

Kod Pythona:

#!/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('')

Kod 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

Zauważ, że próbowałem dwóch różnych implementacji podzielonych. One (split1) używa metod ciągów do wyszukiwania tokenów i jest w stanie łączyć wiele tokenów, a także obsługiwać wiele tokenów (pochodzi stąd ). Drugi (split2) używa getline do odczytywania ciągu jako strumienia, nie łączy ograniczników i obsługuje tylko jeden znak separatora (ten został wysłany przez kilku użytkowników StackOverflow w odpowiedziach na pytania dotyczące podziału ciągów).

Prowadziłem to wiele razy w różnych zamówieniach. Moja maszyna testowa to Macbook Pro (2011, 8GB, Quad Core), nie ma to większego znaczenia. Testuję z plikiem tekstowym o długości 20 milionów wierszy z trzema kolumnami oddzielonymi spacjami, z których każda wygląda podobnie do tego: „foo.bar 127.0.0.1 home.foo.bar”

Wyniki:

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

Co ja robię źle? Czy istnieje lepszy sposób na dzielenie ciągów w C ++, który nie opiera się na bibliotekach zewnętrznych (tj. Bez wzmocnienia), obsługuje łączenie sekwencji ograniczników (jak podział w Pythonie), jest bezpieczny dla wątków (więc nie ma strtoka) i którego wydajność jest co najmniej na równi z Pythonem?

Edytuj 1 / Częściowe rozwiązanie ?:

Próbowałem uczynić to bardziej sprawiedliwym porównaniem, zmuszając Pythona do resetowania listy fikcyjnej i dodawania do niej za każdym razem, tak jak robi to C ++. To wciąż nie jest dokładnie to, co robi kod C ++, ale jest trochę bliżej. Zasadniczo pętla jest teraz:

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

Wydajność Pythona jest teraz mniej więcej taka sama jak w implementacji 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

Wciąż jestem zaskoczony, że nawet jeśli Python jest tak zoptymalizowany pod kątem przetwarzania ciągów (jak zasugerował Matt Joiner), te implementacje C ++ nie byłyby szybsze. Jeśli ktoś ma pomysł, jak zrobić to w bardziej optymalny sposób przy użyciu C ++, udostępnij swój kod. (Myślę, że moim następnym krokiem będzie próba zaimplementowania tego w czystym C, chociaż nie zamierzam rezygnować z produktywności programisty, aby ponownie zaimplementować mój ogólny projekt w C, więc będzie to tylko eksperyment dotyczący szybkości dzielenia ciągów.)

Dziękuję wszystkim za pomoc.

Ostateczna edycja / rozwiązanie:

Zobacz zaakceptowaną odpowiedź Alfa. Ponieważ Python traktuje łańcuchy wyłącznie przez odniesienie, a ciągi STL są często kopiowane, wydajność jest lepsza w przypadku implementacji Vanilla Python. Dla porównania skompilowałem i przepuściłem moje dane przez kod Alf, a tutaj jest wydajność na tej samej maszynie, co wszystkie inne uruchomione, zasadniczo identyczne z naiwną implementacją Pythona (choć szybszą niż implementacja Pythona, która resetuje / dołącza listę, ponieważ pokazane w powyższej edycji):

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

Moje jedyne pozostałe zastrzeżenie dotyczy ilości kodu niezbędnego do wykonania w tym przypadku C ++.

Jedną z lekcji wyciągniętych z tego wydania i wczorajszego problemu z czytaniem wierszy standardowego (link powyżej) jest to, że należy zawsze dokonywać testów porównawczych zamiast naiwnych założeń dotyczących względnej „domyślnej” wydajności języków. Doceniam wykształcenie.

Jeszcze raz dziękuję wszystkim za sugestie!

JJC
źródło
2
Jak skompilowałeś program w C ++? Czy masz włączone optymalizacje?
interjay
2
@interjay: Jest to w ostatnim komentarzu w jego źródle: g++ -Wall -O3 -o split1 split_1.cpp@JJC: Jak radzi sobie twój benchmark, kiedy faktycznie używasz dummyi, splineodpowiednio, może Python usuwa wywołanie, line.split()ponieważ nie ma skutków ubocznych?
Eric
2
Jakie wyniki uzyskasz, jeśli usuniesz podział i pozostawisz tylko czytane wiersze ze standardowego wejścia?
interjay
2
Python jest napisany w C. Oznacza to, że istnieje skuteczny sposób na zrobienie tego w C. Może jest lepszy sposób na podzielenie łańcucha niż użycie STL?
ixe013
3
możliwy duplikat Dlaczego operacje std :: string działają słabo?
Matt Joiner,

Odpowiedzi:

58

Domyślnie napisy w Pythonie są niezmiennymi ciągami liczonymi jako referencje, więc żadne ciągi nie są kopiowane w kodzie Pythona, podczas gdy C ++ std::stringjest zmiennym typem wartości i jest kopiowany przy najmniejszej okazji.

Jeśli celem jest szybkie dzielenie, to można by użyć operacji na podciągach o stałym czasie, co oznacza odnoszenie się tylko do części oryginalnego ciągu, jak w Pythonie (i Javie i C #…).

Klasa C ++ std::stringma jednak jedną funkcję odkupienia: jest standardowa , dzięki czemu może być używana do bezpiecznego i przenośnego przekazywania ciągów znaków w miejscach, w których wydajność nie jest głównym czynnikiem. Ale dość rozmowy. Kod - a na moim komputerze jest to oczywiście szybsze niż Python, ponieważ obsługa łańcuchów w Pythonie jest zaimplementowana w C, który jest podzbiorem 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

Zastrzeżenie: mam nadzieję, że nie ma żadnych błędów. Nie testowałem funkcjonalności, sprawdziłem tylko prędkość. Ale myślę, że nawet jeśli jest błąd lub dwa, poprawienie tego nie wpłynie znacząco na prędkość.

Pozdrawiam i hth. - Alf
źródło
2
Tak, ciągi znaków w Pythonie są obiektami liczonymi jako odwołania, więc Python kopiuje znacznie mniej. Nadal zawierają pod maską ciągi C zakończone znakiem null, ale nie parami (wskaźnik, rozmiar), jak twój kod.
Fred Foo
13
Innymi słowy - w przypadku pracy na wyższym poziomie, takiej jak manipulacja tekstem, trzymaj się języka wyższego poziomu, w którym dziesiątki programistów wkładają w to wysiłek na przestrzeni dziesiątek lat - lub po prostu przygotuj się do pracy tak samo, jak wszyscy ci za posiadanie czegoś porównywalnego na niższym poziomie.
jsbueno,
2
@JJC: w przypadku StringRef, możesz std::stringbardzo łatwo skopiować podciąg do pliku just string( sr.begin(), sr.end() ).
Pozdrawiam i hth. - Alf
3
Chciałbym, żeby ciągi CPythona były mniej kopiowane. Tak, są liczone jako odwołania i niezmienne, ale str.split () przydziela nowe ciągi dla każdego elementu używając PyString_FromStringAndSize()tych wywołań PyObject_MALLOC(). Nie ma więc optymalizacji ze wspólną reprezentacją, która wykorzystuje fakt, że ciągi znaków są niezmienne w Pythonie.
jfs
3
Opiekunowie: proszę nie wprowadzać błędów, próbując naprawić błędy dostrzeżone (szczególnie nie w odniesieniu do cplusplus.com ). TIA.
Pozdrawiam i hth. - Alf
9

Nie dostarczam lepszych rozwiązań (przynajmniej pod względem wydajności), ale dodatkowe dane, które mogłyby być interesujące.

Korzystanie strtok_r(wariant ponownie wprowadzający 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);
}

Dodatkowo użycie ciągów znaków dla parametrów i fgetsdanych wejściowych:

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

W niektórych przypadkach niszczenie ciągu wejściowego jest dopuszczalne:

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

Czasy ich wykonania są następujące (w tym moje wyniki dla innych wariantów z pytania i zaakceptowanej odpowiedzi):

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

Jak widać, rozwiązanie z zaakceptowanej odpowiedzi jest nadal najszybsze.

Dla każdego, kto chciałby zrobić dalsze testy, umieściłem również repozytorium Github ze wszystkimi programami z pytania, zaakceptowaną odpowiedzią, tą odpowiedzią, a dodatkowo Makefile i skrypt do generowania danych testowych: https: // github. com / tobbez / string-splitting .

tobbez
źródło
2
Zrobiłem żądanie ściągnięcia ( github.com/tobbez/string-splitting/pull/2 ), które sprawia, że ​​test jest nieco bardziej realistyczny dzięki „wykorzystaniu” danych (liczenie liczby słów i znaków). Dzięki tej zmianie wszystkie wersje C / C ++ przewyższają wersje Pythona (nie licząc wersji opartej na tokenizatorze Boost, który dodałem), a prawdziwa wartość metod opartych na „widoku ciągów znaków” (takich jak split6) świeci.
Dave Johansen
Powinieneś użyć memcpy, nie strcpy, na wypadek, gdyby kompilator nie zauważył tej optymalizacji. strcpyzazwyczaj używa wolniejszej strategii uruchamiania, która zapewnia równowagę między szybkim dla krótkich ciągów a zwiększeniem do pełnego SIMD dla długich ciągów. memcpyzna rozmiar od razu i nie musi używać żadnych sztuczek SIMD, aby sprawdzić koniec łańcucha o niejawnej długości. (Nie jest to wielka sprawa na nowoczesnym x86). Tworzenie std::stringobiektów za pomocą (char*, len)konstruktora może być również szybsze, jeśli możesz to uzyskać saveptr-token. Oczywiście najszybciej byłoby po prostu przechowywać char*żetony: P
Peter Cordes
4

Podejrzewam, że jest to spowodowane sposobem zmiany std::vectorrozmiaru podczas procesu wywołania funkcji push_back (). Jeśli spróbujesz użyć std::listlub std::vector::reserve()zarezerwować wystarczającą ilość miejsca na zdania, powinieneś uzyskać znacznie lepszą wydajność. Lub możesz użyć kombinacji obu, jak poniżej dla 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());
}

EDYCJA : Inną oczywistą rzeczą, którą widzę, jest to, że zmienna Pythona dummyjest przypisywana za każdym razem, ale nie jest modyfikowana. Więc to nie jest uczciwe porównanie z C ++. Powinieneś spróbować zmodyfikować swój kod Pythona, aby go dummy = []zainicjować, a następnie zrobić dummy += line.split(). Czy możesz następnie zgłosić czas działania?

EDIT2 : Aby było jeszcze bardziej sprawiedliwie, możesz zmodyfikować pętlę while w kodzie C ++ tak, aby była:

    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++;
    };
Vite Falcon
źródło
Dzięki za pomysł. Zaimplementowałem to i niestety ta implementacja jest wolniejsza niż oryginalny split1. Próbowałem również spline.reserve (16) przed pętlą, ale nie miało to wpływu na prędkość mojego split1. W każdym wierszu są tylko trzy żetony, a wektor jest usuwany po każdym wierszu, więc nie spodziewałem się, że to pomoże.
JJC
Wypróbowałem również twoją edycję. Zobacz zaktualizowane pytanie. Wydajność jest teraz na równi z split1.
JJC
Próbowałem twojego EDIT2. Wydajność była nieco gorsza: $ / usr / bin / time cat test_lines_double | ./split7 33,39 real 0,01 użytkownik 0,49 sys C ++: wyświetlono 20000000 linii w 33 sekundy. Szybkość chrupania: 606060
JJC
3

Myślę, że poniższy kod jest lepszy, używając niektórych funkcji C ++ 17 i 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));
}

Wybór pojemnika:

  1. std::vector.

    Zakładając, że początkowy rozmiar przydzielonej tablicy wewnętrznej to 1, a ostateczny rozmiar to N, przydzielisz i zwolnisz alokację dla log2 (N) razy, a następnie skopiujesz (2 ^ (log2 (N) + 1) - 1) = (2BA - 1) razy. Jak wskazano w Czy słaba wydajność std :: vector spowodowana brakiem wywołania funkcji realloc jest logarytmiczną liczbą razy? , może to mieć słabą wydajność, gdy rozmiar wektora jest nieprzewidywalny i może być bardzo duży. Ale jeśli możesz oszacować jego rozmiar, będzie to mniejszy problem.

  2. std::list.

    Dla każdego push_back zużyty czas jest stałą, ale prawdopodobnie zajmie więcej czasu niż std :: vector w przypadku pojedynczego push_back. Użycie puli pamięci na wątek i niestandardowego alokatora może złagodzić ten problem.

  3. std::forward_list.

    To samo co std :: list, ale zajmuje mniej pamięci na element. Wymagaj, aby klasa opakowania działała z powodu braku interfejsu API push_back.

  4. std::array.

    Jeśli znasz granicę wzrostu, możesz użyć std :: array. Oczywiście nie można go używać bezpośrednio, ponieważ nie ma on API push_back. Ale możesz zdefiniować opakowanie i myślę, że jest to najszybszy sposób tutaj i może zaoszczędzić trochę pamięci, jeśli twoje oszacowanie jest dość dokładne.

  5. std::deque.

    Ta opcja umożliwia wymianę pamięci na wydajność. Nie będzie (2 ^ (N + 1) - 1) razy kopii elementu, tylko N razy alokacja i brak cofnięcia alokacji. Ponadto będziesz mieć stały losowy czas dostępu i możliwość dodawania nowych elementów na obu końcach.

Zgodnie ze std :: deque-cppreference

Z drugiej strony, deques zazwyczaj mają duży minimalny koszt pamięci; deque przechowujący tylko jeden element musi przydzielić swoją pełną wewnętrzną tablicę (np. 8-krotność rozmiaru obiektu w 64-bitowym libstdc ++; 16-krotność rozmiaru obiektu lub 4096 bajtów, w zależności od tego, która z tych wartości jest większa, w 64-bitowej libc ++)

lub możesz użyć kombinacji tych:

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

    Jest to podobne do std :: deque, różnica polega na tym, że ten kontener nie obsługuje dodawania elementu z przodu. Ale nadal działa szybciej, ponieważ nie skopiuje bazowego std :: array for (2 ^ (N + 1) - 1) razy, po prostu skopiuje tablicę wskaźników dla (2 ^ (N - M + 1) - 1) razy i przydzielanie nowej tablicy tylko wtedy, gdy bieżąca jest pełna i nie trzeba niczego cofać. Nawiasem mówiąc, możesz uzyskać stały czas dostępu losowego.

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

    Znacznie złagodzić presję framentacji pamięci. Przydzieli nową tablicę tylko wtedy, gdy bieżąca jest pełna i nie musi niczego kopiować. Nadal będziesz musiał zapłacić cenę za dodatkowy wskaźnik w porównaniu do combo 1.

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

    To samo co 2, ale kosztuje tyle samo pamięci co combo 1.

JiaHao Xu
źródło
Jeśli używasz std :: vector z pewnym rozsądnym rozmiarem początkowym, takim jak 128 lub 256, łączna liczba kopii (zakładając współczynnik wzrostu 2), unikasz kopiowania w ogóle dla rozmiarów do tego limitu. Następnie możesz zmniejszyć przydział, aby dopasować go do liczby faktycznie używanych elementów, więc nie jest to straszne w przypadku małych nakładów. Nie pomaga to jednak zbytnio przy całkowitej liczbie kopii w bardzo dużej Nobudowie. Szkoda, że std :: vector nie może reallocpotencjalnie pozwolić na mapowanie większej liczby stron pod koniec bieżącego przydziału , więc jest około 2x wolniejszy.
Peter Cordes
Czy jest stringview::remove_prefixtak tanie, jak śledzenie aktualnej pozycji w zwykłym ciągu? std::basic_string::findma opcjonalny drugi argument pos = 0umożliwiający rozpoczęcie wyszukiwania od przesunięcia.
Peter Cordes
@ Peter Cordes Zgadza się. Sprawdziłem libcxx impl
JiaHao Xu
Sprawdziłem również libstdc ++ impl , który jest taki sam.
JiaHao Xu
Twoja analiza wydajności wektora jest wyłączona. Rozważ wektor, który ma początkową pojemność 1 podczas pierwszego wstawiania i podwaja się za każdym razem, gdy potrzebuje nowej pojemności. Jeśli musisz umieścić 17 pozycji, pierwsza alokacja daje miejsce na 1, potem 2, potem 4, potem 8, potem 16, a na końcu 32. Oznacza to, że było łącznie 6 alokacji ( log2(size - 1) + 2używając logu liczb całkowitych). Pierwsza alokacja przesunęła 0 ciągów, druga przesunęła 1, potem 2, potem 4, potem 8, a na koniec 16, w sumie 31 ruchów ( 2^(log2(size - 1) + 1) - 1)). To jest O (n), a nie O (2 ^ n). To znacznie przewyższa std::list.
David Stone
2

Robisz błędne założenie, że wybrana przez Ciebie implementacja C ++ jest koniecznie szybsza niż Python. Obsługa ciągów znaków w Pythonie jest wysoce zoptymalizowana. Zobacz to pytanie, aby uzyskać więcej informacji: Dlaczego operacje std :: string działają słabo?

Matt Joiner
źródło
4
Nie mówię o ogólnej wydajności języka, tylko o moim konkretnym kodzie. Nie ma więc żadnych założeń. Dziękuję za dobrą wskazówkę na drugie pytanie. Nie jestem pewien, czy mówisz, że ta konkretna implementacja w C ++ jest nieoptymalna (twoje pierwsze zdanie), czy też że C ++ jest po prostu wolniejszy niż Python w przetwarzaniu ciągów (twoje drugie zdanie). Ponadto, jeśli znasz szybki sposób zrobienia tego, co próbuję zrobić w C ++, udostępnij go dla dobra wszystkich. Dzięki. Gwoli wyjaśnienia, uwielbiam Pythona, ale nie jestem ślepym fanboyem, dlatego staram się nauczyć tego najszybszego sposobu.
JJC
1
@JJC: Biorąc pod uwagę, że implementacja Pythona jest szybsza, powiedziałbym, że Twoja jest nieoptymalna. Pamiętaj, że implementacje językowe mogą ci pomóc, ale ostatecznie wygrywają złożoność algorytmiczna i optymalizacja rąk. W tym przypadku Python ma domyślnie przewagę w tym przypadku użycia.
Matt Joiner
2

Jeśli weźmiesz implementację split1 i zmienisz podpis, aby bardziej pasował do tego z split2, zmieniając to:

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

do tego:

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

Otrzymujesz bardziej dramatyczną różnicę między split1 i split2 oraz bardziej sprawiedliwe porównanie:

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
Paul Beckingham
źródło
1
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;
        }
    }
}
n. zaimki m.
źródło
Dzięki NM! Niestety wydaje się, że działa to mniej więcej z taką samą szybkością jak oryginalna implementacja (podział 1) na moim zbiorze danych i komputerze: $ / usr / bin / time cat test_lines_double | ./split8 21,89 real 0,01 użytkownik 0,47 sys C ++: wyświetlono 20000000 linii w 22 sekundy. Szybkość chrupania: 909090
JJC
Na moim komputerze: split1 - 54s, split.py - 35s, split5 - 16s. Nie mam pojęcia.
n. zaimki m.
Hmm, czy Twoje dane są zgodne z formatem, który zauważyłem powyżej? Zakładam, że uruchomiłeś każdy z nich kilka razy, aby wyeliminować przejściowe efekty, takie jak początkowe zapełnienie pamięci podręcznej dysku?
JJC
0

Podejrzewam, że jest to związane z buforowaniem na sys.stdin w Pythonie, ale bez buforowania w implementacji C ++.

Zobacz ten post, aby dowiedzieć się, jak zmienić rozmiar bufora, a następnie spróbuj ponownie porównać: Ustawianie mniejszego rozmiaru bufora dla sys.stdin?

Alex Collins
źródło
1
Hmmm ... Nie nadążam. Samo czytanie wierszy (bez podziału) jest szybsze w C ++ niż w Pythonie (po uwzględnieniu linii cin.sync_with_stdio (false);). To był problem, który miałem wczoraj, o którym mowa powyżej.
JJC