Warum ist das Teilen eines Strings in C ++ langsamer als in Python?

93

Ich versuche, Code von Python nach C ++ zu konvertieren, um ein wenig Geschwindigkeit zu gewinnen und meine verrosteten C ++ - Fähigkeiten zu verbessern. Gestern war ich schockiert, als eine naive Implementierung des Lesens von Zeilen aus stdin in Python viel schneller war als in C ++ (siehe hier ). Heute habe ich endlich herausgefunden, wie man einen String in C ++ mit zusammengeführten Trennzeichen teilt (ähnliche Semantik wie pythons split ()), und jetzt erlebe ich deja vu! Mein C ++ - Code benötigt viel länger, um die Arbeit zu erledigen (allerdings nicht um eine Größenordnung mehr, wie es in der gestrigen Lektion der Fall war).

Python-Code:

#!/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 ++ - Code:

#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

Beachten Sie, dass ich zwei verschiedene Split-Implementierungen ausprobiert habe. One (split1) verwendet String-Methoden, um nach Token zu suchen, und kann mehrere Token zusammenführen sowie zahlreiche Token verarbeiten (es kommt von hier ). Der zweite (split2) verwendet getline, um die Zeichenfolge als Stream zu lesen, führt keine Trennzeichen zusammen und unterstützt nur ein einzelnes Begrenzungszeichen (das von mehreren StackOverflow-Benutzern in Antworten auf Fragen zur Zeichenfolgenaufteilung veröffentlicht wurde).

Ich habe dies mehrmals in verschiedenen Reihenfolgen ausgeführt. Mein Testgerät ist ein Macbook Pro (2011, 8 GB, Quad Core), nicht dass es viel ausmacht. Ich teste mit einer 20-Millionen-Zeilentextdatei mit drei durch Leerzeichen getrennten Spalten, die jeweils ähnlich aussehen: "foo.bar 127.0.0.1 home.foo.bar"

Ergebnisse:

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

Was mache ich falsch? Gibt es eine bessere Möglichkeit zum Aufteilen von Zeichenfolgen in C ++, die nicht auf externen Bibliotheken basiert (dh keinen Boost), das Zusammenführen von Trennzeichenfolgen unterstützt (wie die Aufteilung von Python), threadsicher ist (also kein strtok) und deren Leistung mindestens ist? auf Augenhöhe mit Python?

Bearbeiten 1 / Teillösung?:

Ich habe versucht, den Vergleich fairer zu gestalten, indem Python die Dummy-Liste zurückgesetzt und jedes Mal angehängt hat, wie dies in C ++ der Fall ist. Dies ist immer noch nicht genau das, was der C ++ - Code tut, aber es ist ein bisschen näher. Grundsätzlich ist die Schleife jetzt:

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

Die Leistung von Python entspricht jetzt in etwa der von 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

Ich bin immer noch überrascht, dass diese C ++ - Implementierungen nicht schneller wären, selbst wenn Python für die Zeichenfolgenverarbeitung so optimiert ist (wie Matt Joiner vorgeschlagen hat). Wenn jemand Ideen hat, wie dies mit C ++ optimaler gemacht werden kann, teilen Sie bitte Ihren Code mit. (Ich denke, mein nächster Schritt wird darin bestehen, dies in reinem C zu implementieren, obwohl ich die Produktivität der Programmierer nicht abwägen werde, um mein Gesamtprojekt in C erneut zu implementieren. Dies wird also nur ein Experiment für die Geschwindigkeit der Zeichenfolgenaufteilung sein.)

Vielen Dank an alle für Ihre Hilfe.

Endgültige Bearbeitung / Lösung:

Bitte lesen Sie die akzeptierte Antwort von Alf. Da Python Strings ausschließlich als Referenz behandelt und STL-Strings häufig kopiert werden, ist die Leistung bei Vanilla-Python-Implementierungen besser. Zum Vergleich habe ich meine Daten über Alfs Code kompiliert und ausgeführt. Hier ist die Leistung auf demselben Computer wie bei allen anderen Läufen, die im Wesentlichen mit der naiven Python-Implementierung identisch ist (obwohl sie schneller ist als die Python-Implementierung, mit der die Liste zurückgesetzt / angehängt wird) in der obigen Bearbeitung gezeigt):

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

Mein einziger kleiner Kritikpunkt betrifft die Menge an Code, die erforderlich ist, damit C ++ in diesem Fall funktioniert.

Eine der Lehren aus dieser Ausgabe und der gestrigen Ausgabe zum Lesen von Standardzeilen (siehe oben) ist, dass man immer einen Benchmark durchführen sollte, anstatt naive Annahmen über die relative "Standard" -Leistung von Sprachen zu treffen. Ich schätze die Ausbildung.

Nochmals vielen Dank an alle für Ihre Vorschläge!

JJC
quelle
2
Wie haben Sie das C ++ - Programm kompiliert? Haben Sie Optimierungen aktiviert?
Interjay
2
@interjay: Es ist im letzten Kommentar in seiner Quelle: g++ -Wall -O3 -o split1 split_1.cpp@JJC: Wie sieht Ihr Benchmark - Tarif , wenn Sie tatsächlich nutzen dummyund splinejeweils vielleicht Python entfernt den Aufruf , line.split()weil es keine Nebenwirkungen hat?
Eric
2
Welche Ergebnisse erhalten Sie, wenn Sie die Aufteilung entfernen und nur noch Lesezeilen von stdin lassen?
Interjay
2
Python ist in C geschrieben. Dies bedeutet, dass es in C eine effiziente Methode gibt. Vielleicht gibt es eine bessere Möglichkeit, eine Zeichenfolge zu teilen, als STL zu verwenden?
ixe013
3
Mögliches Duplikat von Warum funktionieren std :: string-Operationen schlecht?
Matt Joiner

Antworten:

57

Vermutlich sind Python-Zeichenfolgen unveränderliche Zeichenfolgen mit Referenzzählung, sodass im Python-Code keine Zeichenfolgen kopiert werden, während C ++ std::stringein veränderlicher Werttyp ist und bei der kleinsten Gelegenheit kopiert wird.

Wenn das Ziel eine schnelle Aufteilung ist, würde man Teilzeichenfolgenoperationen mit konstanter Zeit verwenden, was bedeutet, dass nur auf Teile der ursprünglichen Zeichenfolge Bezug genommen wird , wie in Python (und Java und C #…).

Die C ++ - std::stringKlasse verfügt jedoch über eine Einlösungsfunktion: Sie ist Standard , sodass sie verwendet werden kann, um Zeichenfolgen sicher und portabel zu übergeben, wenn die Effizienz keine Hauptrolle spielt. Aber genug plaudern. Code - und auf meinem Computer ist dies natürlich schneller als Python, da Pythons String-Handling in C implementiert ist, einer Teilmenge von 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

Haftungsausschluss: Ich hoffe, es gibt keine Fehler. Ich habe die Funktionalität nicht getestet, sondern nur die Geschwindigkeit überprüft. Aber ich denke, selbst wenn es ein oder zwei Fehler gibt, wirkt sich eine Korrektur nicht wesentlich auf die Geschwindigkeit aus.

Prost und hth. - Alf
quelle
2
Ja, Python-Zeichenfolgen sind Objekte mit Referenzzählung, sodass Python weit weniger kopiert. Sie enthalten weiterhin nullterminierte C-Zeichenfolgen unter der Haube, jedoch keine Paare (Zeiger, Größe) wie Ihr Code.
Fred Foo
12
Mit anderen Worten: Halten Sie sich bei Arbeiten auf höherer Ebene, wie z. B. bei der Textmanipulation, an eine Sprache auf höherer Ebene, in der Dutzende von Entwicklern über mehrere Jahre hinweg kumulativ Anstrengungen unternommen haben, um dies effizient zu tun - oder bereiten Sie sich einfach darauf vor, so viel wie alle diese Entwickler zu arbeiten für etwas Vergleichbares in der unteren Ebene.
Jsbueno
2
@JJC: Für die StringRefkönnen Sie den Teilstring std::stringsehr einfach auf einen kopieren string( sr.begin(), sr.end() ).
Prost und hth. - Alf
3
Ich wünschte, CPython-Zeichenfolgen würden weniger kopiert. Ja, sie sind referenzgezählt und unveränderlich, aber str.split () weist jedem Element , PyString_FromStringAndSize()das diese Aufrufe verwendet , neue Zeichenfolgen zuPyObject_MALLOC() . Es gibt also keine Optimierung mit einer gemeinsam genutzten Darstellung, die ausnutzt, dass die Zeichenfolgen in Python unveränderlich sind.
JFS
3
Betreuer: Bitte führen Sie keine Fehler ein, indem Sie versuchen, wahrgenommene Fehler zu beheben (insbesondere nicht in Bezug auf cplusplus.com ). TIA.
Prost und hth. - Alf
9

Ich biete keine besseren Lösungen (zumindest in Bezug auf die Leistung), aber einige zusätzliche Daten, die interessant sein könnten.

Verwenden strtok_r(Wiedereintrittsvariante von 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);
}

Verwenden Sie zusätzlich Zeichenfolgen für Parameter und fgetszur Eingabe:

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

Und in einigen Fällen, in denen das Zerstören der Eingabezeichenfolge akzeptabel ist:

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

Die Zeitpunkte für diese sind wie folgt (einschließlich meiner Ergebnisse für die anderen Varianten aus der Frage und der akzeptierten Antwort):

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

Wie wir sehen können, ist die Lösung aus der akzeptierten Antwort immer noch am schnellsten.

Für alle, die weitere Tests durchführen möchten, habe ich auch ein Github-Repo mit allen Programmen aus der Frage, der akzeptierten Antwort, dieser Antwort und zusätzlich einem Makefile und einem Skript zum Generieren von Testdaten erstellt: https: // github. com / tobbez / string-split .

tobbez
quelle
2
Ich habe eine Pull-Anfrage ( github.com/tobbez/string-splitting/pull/2 ) gestellt, die den Test ein wenig realistischer macht, indem die Daten "verwendet" werden (Anzahl der Wörter und Zeichen gezählt). Mit dieser Änderung übertreffen alle C / C ++ - Versionen die Python-Versionen (erwarten Sie die Version, die auf dem von mir hinzugefügten Boost-Tokenizer basiert), und der wahre Wert von Methoden, die auf "String View" basieren (wie die von split6), glänzen.
Dave Johansen
Sie sollten memcpynicht verwenden strcpy, falls der Compiler diese Optimierung nicht bemerkt. strcpyVerwendet normalerweise eine langsamere Startstrategie, die ein Gleichgewicht zwischen schnell für kurze Saiten und Hochfahren auf volle SIMD für lange Saiten schafft. memcpykennt die Größe sofort und muss keine SIMD-Tricks verwenden, um nach dem Ende einer Zeichenfolge mit impliziter Länge zu suchen. (Keine große Sache bei modernen x86). Das Erstellen von std::stringObjekten mit dem (char*, len)Konstruktor ist möglicherweise auch schneller, wenn Sie dies herausholen können saveptr-token. Offensichtlich wäre es am schnellsten, nur char*Token zu speichern : P
Peter Cordes
4

Ich vermute, dass dies daran liegt, dass die std::vectorGröße während des Vorgangs eines Funktionsaufrufs von push_back () geändert wird. Wenn Sie versuchen, genügend Platz für die Sätze zu verwenden std::listoder std::vector::reserve()zu reservieren, sollten Sie eine viel bessere Leistung erzielen. Oder Sie können eine Kombination von beiden wie unten für split1 () verwenden:

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 : Das andere offensichtliche , was ich sehe , ist , dass Python - Variable dummywird zugewiesen jedes Mal , aber nicht verändert werden . Es ist also kein fairer Vergleich mit C ++. Sie sollten versuchen, Ihren Python-Code so dummy = []zu ändern , dass er initialisiert wird, und dies dann tun dummy += line.split(). Können Sie die Laufzeit danach melden?

EDIT2 : Um es noch fairer zu machen, können Sie die while-Schleife im C ++ - Code folgendermaßen ändern:

    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
quelle
Danke für die Idee. Ich habe es implementiert und diese Implementierung ist leider langsamer als das ursprüngliche split1. Ich habe auch spline.reserve (16) vor der Schleife ausprobiert, aber dies hatte keinen Einfluss auf die Geschwindigkeit meines split1. Es gibt nur drei Token pro Zeile, und der Vektor wird nach jeder Zeile gelöscht, sodass ich nicht erwartet habe, dass dies viel hilft.
JJC
Ich habe auch deine Bearbeitung versucht. Bitte beachten Sie die aktualisierte Frage. Die Leistung ist jetzt auf dem Niveau von split1.
JJC
Ich habe dein EDIT2 ausprobiert. Die Leistung war etwas schlechter: $ / usr / bin / time cat test_lines_double | ./split7 33,39 real 0,01 Benutzer 0,49 sys C ++: 20000000 Linien in 33 Sekunden sägen. Crunch-Geschwindigkeit: 606060
JJC
3

Ich denke, der folgende Code ist besser, wenn einige C ++ 17- und C ++ 14-Funktionen verwendet werden:

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

Die Wahl des Behälters:

  1. std::vector.

    Angenommen, die anfängliche Größe des zugewiesenen internen Arrays ist 1 und die endgültige Größe ist N, Sie werden log2 (N) -Zeiten zuweisen und freigeben, und Sie werden (2 ^ (log2 (N) + 1) - 1) = kopieren (2N - 1) mal. Wie in Ist die schlechte Leistung von std :: vector darauf zurückzuführen, dass realloc nicht logarithmisch aufgerufen wird? Dies kann eine schlechte Leistung haben, wenn die Größe des Vektors nicht vorhersehbar ist und sehr groß sein kann. Wenn Sie jedoch die Größe abschätzen können, ist dies weniger problematisch.

  2. std::list.

    Für jeden push_back ist die verbrauchte Zeit eine Konstante, aber es wird wahrscheinlich mehr Zeit als std :: vector für einzelne push_back dauern. Die Verwendung eines Thread-Speicherpools und eines benutzerdefinierten Allokators kann dieses Problem beheben.

  3. std::forward_list.

    Entspricht std :: list, belegt jedoch weniger Speicher pro Element. Eine Wrapper-Klasse muss funktionieren, da die API push_back fehlt.

  4. std::array.

    Wenn Sie die Wachstumsgrenze kennen, können Sie std :: array verwenden. Natürlich können Sie es nicht direkt verwenden, da es nicht über die API push_back verfügt. Aber Sie können einen Wrapper definieren, und ich denke, dies ist der schnellste Weg, und Sie können Speicherplatz sparen, wenn Ihre Schätzung ziemlich genau ist.

  5. std::deque.

    Mit dieser Option können Sie Speicher gegen Leistung eintauschen. Es gibt keine (2 ^ (N + 1) - 1) -malige Kopie des Elements, nur eine N-fache Zuordnung und keine Freigabe. Außerdem haben Sie eine konstante Direktzugriffszeit und die Möglichkeit, an beiden Enden neue Elemente hinzuzufügen.

Laut std :: deque-cppreference

Andererseits haben Deques typischerweise große minimale Speicherkosten; Eine Deque, die nur ein Element enthält, muss ihr vollständiges internes Array zuweisen (z. B. das 8-fache der Objektgröße in 64-Bit-libstdc ++; das 16-fache der Objektgröße oder 4096 Bytes, je nachdem, welcher Wert größer ist, in 64-Bit-libc ++).

oder Sie können eine Kombination davon verwenden:

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

    Dies ähnelt std :: deque. Der Unterschied besteht nur darin, dass dieser Container das Hinzufügen von Elementen an der Vorderseite nicht unterstützt. Die Leistung ist jedoch immer noch schneller, da das zugrunde liegende std :: -Array nicht (2 ^ (N + 1) - 1) Mal kopiert wird, sondern nur das Zeigerarray für (2 ^) (N - M + 1) - 1) Mal und Zuweisung eines neuen Arrays nur, wenn der Strom voll ist und keine Freigabe erforderlich ist. Übrigens können Sie eine konstante Direktzugriffszeit erhalten.

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

    Entlasten Sie den Druck der Gedächtnisfragmentierung erheblich. Es wird nur dann ein neues Array zugewiesen, wenn das aktuelle voll ist, und es muss nichts kopiert werden. Sie müssen immer noch den Preis für einen zusätzlichen Zeiger bezahlen, der mit Combo 1 verglichen wird.

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

    Wie 2, kostet aber den gleichen Speicher wie Combo 1.

JiaHao Xu
quelle
Wenn Sie std :: vector mit einer angemessenen Anfangsgröße wie 128 oder 256 verwenden, die Gesamtkopie (unter der Annahme eines Wachstumsfaktors von 2), vermeiden Sie das Kopieren für Größen bis zu dieser Grenze. Sie können dann die Zuordnung verkleinern, um sie an die Anzahl der tatsächlich verwendeten Elemente anzupassen, sodass es für kleine Eingaben nicht schrecklich ist. Dies hilft jedoch nicht viel bei der Gesamtzahl der Kopien für den sehr großen NFall. Es ist schade, dass std :: vector nicht verwenden kann, reallocum möglicherweise mehr Seiten am Ende der aktuellen Zuordnung zuzuordnen , daher ist es ungefähr 2x langsamer.
Peter Cordes
Ist es stringview::remove_prefixso billig, nur Ihre aktuelle Position in einer normalen Saite zu verfolgen? std::basic_string::findhat ein optionales 2. Argument pos = 0, mit dem Sie die Suche von einem Offset aus starten können.
Peter Cordes
@ Peter Cordes Das ist richtig. Ich überprüfte libcxx impl
JiaHao Xu
Ich habe auch libstdc ++ impl überprüft , was das gleiche ist.
JiaHao Xu
Ihre Analyse der Leistung des Vektors ist deaktiviert. Stellen Sie sich einen Vektor vor, der beim ersten Einfügen eine Anfangskapazität von 1 hat und sich jedes Mal verdoppelt, wenn neue Kapazität benötigt wird. Wenn Sie 17 Elemente eingeben müssen, bietet die erste Zuordnung Platz für 1, dann 2, dann 4, dann 8, dann 16, dann schließlich 32. Dies bedeutet, dass insgesamt 6 Zuordnungen vorhanden waren ( log2(size - 1) + 2unter Verwendung eines Ganzzahlprotokolls). Bei der ersten Zuordnung wurden 0 Zeichenfolgen verschoben, bei der zweiten 1, dann 2, dann 4, dann 8 und schließlich 16 Zeichenfolgen, was insgesamt 31 Zügen entspricht ( 2^(log2(size - 1) + 1) - 1)). Dies ist O (n), nicht O (2 ^ n). Dies wird deutlich besser abschneiden std::list.
David Stone
2

Sie gehen fälschlicherweise davon aus, dass Ihre gewählte C ++ - Implementierung notwendigerweise schneller ist als die von Python. Das String-Handling in Python ist stark optimiert. Weitere Informationen finden Sie in dieser Frage: Warum funktionieren std :: string-Operationen schlecht?

Matt Joiner
quelle
4
Ich mache keine Angaben zur allgemeinen Sprachleistung, sondern nur zu meinem speziellen Code. Also hier keine Annahmen. Danke für den guten Hinweis auf die andere Frage. Ich bin mir nicht sicher, ob Sie sagen, dass diese bestimmte Implementierung in C ++ nicht optimal ist (Ihr erster Satz) oder dass C ++ bei der Zeichenfolgenverarbeitung (Ihr zweiter Satz) nur langsamer als Python ist. Wenn Sie einen schnellen Weg kennen, um das zu tun, was ich in C ++ versuche, teilen Sie ihn bitte zum Nutzen aller mit. Vielen Dank. Nur um das zu verdeutlichen, ich liebe Python, aber ich bin kein blinder Fan, weshalb ich versuche, den schnellsten Weg zu lernen, dies zu tun.
JJC
1
@JJC: Angesichts der schnelleren Implementierung von Python würde ich sagen, dass Ihre Implementierung nicht optimal ist. Denken Sie daran, dass Sprachimplementierungen für Sie Abstriche machen können, aber letztendlich gewinnen algorithmische Komplexität und Handoptimierungen. In diesem Fall hat Python standardmäßig die Oberhand für diesen Anwendungsfall.
Matt Joiner
2

Wenn Sie die split1-Implementierung verwenden und die Signatur so ändern, dass sie der von split2 besser entspricht, ändern Sie Folgendes:

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

dazu:

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

Sie erhalten einen dramatischeren Unterschied zwischen split1 und split2 und einen faireren Vergleich:

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
quelle
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. 'Pronomen' m.
quelle
Danke nm! Leider scheint dies ungefähr mit der gleichen Geschwindigkeit wie die ursprüngliche Implementierung (Split 1) auf meinem Dataset und Computer zu laufen: $ / usr / bin / time cat test_lines_double | ./split8 21,89 real 0,01 Benutzer 0,47 sys C ++: 20000000 Zeilen in 22 Sekunden sägen. Crunch-Geschwindigkeit: 909090
JJC
Auf meinem Computer: split1 - 54s, split.py - 35s, split5 - 16s. Ich habe keine Ahnung.
n. 'Pronomen' m.
Hmm, stimmen Ihre Daten mit dem oben angegebenen Format überein? Ich gehe davon aus, dass Sie jedes Mal mehrmals ausgeführt wurden, um vorübergehende Effekte wie die anfängliche Festplatten-Cache-Population zu eliminieren.
JJC
0

Ich vermute, dass dies mit der Pufferung auf sys.stdin in Python zusammenhängt, aber keine Pufferung in der C ++ - Implementierung.

In diesem Beitrag finden Sie Details zum Ändern der Puffergröße. Versuchen Sie dann den Vergleich erneut: Festlegen einer kleineren Puffergröße für sys.stdin?

Alex Collins
quelle
1
Hmmm ... ich folge nicht. Nur das Lesen von Zeilen (ohne Teilung) ist in C ++ schneller als in Python (nach dem Einfügen von cin.sync_with_stdio (false); Zeile). Das war das Problem, das ich gestern hatte und auf das oben Bezug genommen wurde.
JJC