c++ - una - operadores de incremento en python

¿Por qué dividir una cadena es más lenta en C++ que en Python?

Question

Intento convertir algún código de Python a C ++ en un esfuerzo por ganar un poco de velocidad y agudizar mis oxidadas habilidades de C ++. Ayer quedé sorprendido cuando una implementación ingenua de líneas de lectura de stdin fue mucho más rápida en Python que en C ++ (ver this ). Hoy, finalmente descubrí cómo dividir una cadena en C ++ con los delimitadores de fusión (semántica similar a la división de python ()), ¡y ahora estoy experimentando un deja vu! Mi código C ++ toma mucho más tiempo para hacer el trabajo (aunque no un orden de magnitud más, como fue el caso de la lección de ayer).

Código de 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ódigo 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

Tenga en cuenta que probé dos implementaciones de división diferentes. Uno (split1) utiliza métodos de cadena para buscar tokens y puede fusionar varios tokens así como manejar numerosos tokens (proviene de here ). El segundo (split2) usa getline para leer la cadena como una secuencia, no fusiona delimitadores, y solo admite un solo carácter delímetro (ese fue publicado por varios usuarios de StackOverflow en respuestas a preguntas de división de cadenas).

Ejecuté esto varias veces en varios pedidos. Mi máquina de prueba es una Macbook Pro (2011, 8GB, Quad Core), no es que importe mucho. Estoy probando con un archivo de texto de línea de 20M con tres columnas separadas por espacios que se parecen a esto: "foo.bar 127.0.0.1 home.foo.bar"

Resultados:

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

¿Qué estoy haciendo mal? ¿Existe una mejor manera de dividir cadenas en C ++ que no dependa de librerías externas (es decir, no aumentar), admite fusionar secuencias de delimitadores (como la división de Python), es seguro para hilos (por lo que no strtok) y cuyo rendimiento es al menos a la par con Python?

¿Edición 1 / Solución parcial ?:

Intenté hacer una comparación más justa al hacer que python restableciera la lista ficticia y anexarla cada vez, como hace C ++. Esto todavía no es exactamente lo que está haciendo el código C ++, pero está un poco más cerca. Básicamente, el ciclo es ahora:

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

El rendimiento de python ahora es aproximadamente el mismo que el de la implementación 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

Todavía estoy sorprendido de que, incluso si Python está tan optimizado para el procesamiento de cadenas (como sugirió Matt Joiner), estas implementaciones de C ++ no serían más rápidas. Si alguien tiene ideas sobre cómo hacer esto de una manera más óptima con C ++, comparta su código. (Creo que mi próximo paso será implementar esto en C pura, aunque no voy a sacrificar la productividad del programador para volver a implementar mi proyecto general en C, así que esto será solo un experimento para la velocidad de división de cuerdas).

Gracias a todos por vuestra ayuda.

Edición final / Solución:

Por favor, mira la respuesta aceptada de Alf. Dado que python se ocupa de cadenas estrictamente por referencia y las cadenas STL a menudo se copian, el rendimiento es mejor con las implementaciones vanthon python. Para comparar, compilé y ejecuté mis datos a través del código de Alf, y aquí está el rendimiento en la misma máquina que todas las otras ejecuciones, esencialmente idéntica a la implementación naive de python (aunque más rápida que la implementación de python que restablece / agrega la lista, mostrado en la edición anterior):

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

Mi única queja restante es la cantidad de código necesario para que C ++ funcione en este caso.

Una de las lecciones que se desprenden de este tema y del problema de lectura de la línea stdin de ayer (vinculado anteriormente) es que siempre se debe comparar en lugar de hacer suposiciones ingenuas sobre el rendimiento relativo "predeterminado" de los lenguajes. Aprecio la educación.

¡Gracias de nuevo a todos por sus sugerencias!

Answer 1

A modo de conjetura, las cadenas de Python son cadenas inmutables de referencia contadas, de modo que no se copian cadenas en el código de Python, mientras que C ++ std::string es un tipo de valor mutable, y se copia a la menor oportunidad.

Si el objetivo es una división rápida, entonces uno usaría operaciones de subcadenas de tiempo constante, lo que significa solo referirse a partes de la cadena original, como en Python (y Java, y C # ...).

Sin embargo, la clase C ++ std::string tiene una función de canje: es estándar , por lo que se puede usar para pasar cadenas de manera segura y portátil donde la eficiencia no es una consideración principal. Pero suficiente charla. Código - y en mi máquina esto es, por supuesto, más rápido que Python, ya que el manejo de cadenas de Python se implementa en C, que es un subconjunto de 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

Descargo de responsabilidad: espero que no haya ningún error. No he probado la funcionalidad, pero solo verifiqué la velocidad. Pero creo que, incluso si hay una falla o dos, corregir eso no afectará significativamente la velocidad.

Answer 2

Creo que el siguiente código es mejor, usando algunas características de C ++ 17 y 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));
}

La elección del contenedor:

1. std::vector .

   Suponiendo que el tamaño inicial de la matriz interna asignada es 1, y el tamaño final es N, asignará y desasignará para log2 (N) veces, y copiará el (2 ^ (log2 (N) + 1) - 1) = (2N - 1) veces Como se señala en ¿Es el bajo rendimiento de std :: vector debido a que no se llama a realloc un número logarítmico de veces? , esto puede tener un rendimiento pobre cuando el tamaño del vector es impredecible y puede ser muy grande. Pero, si puede estimar su tamaño, esto será menos problemático.

2. std::list .

   Por cada push_back, el tiempo que consume es una constante, pero probablemente llevará más tiempo que std :: vector en push_back individual. El uso de un grupo de memoria por subprocesos y un asignador personalizado puede aliviar este problema.

3. std::forward_list .

   Igual que std :: list, pero ocupa menos memoria por elemento. Requerir que una clase contenedora funcione debido a la falta de API push_back.

4. std::array .

   Si puede conocer el límite de crecimiento, entonces puede usar std :: array. Por causa, no puede usarlo directamente, ya que no tiene API push_back. Pero puede definir un contenedor, y creo que es la manera más rápida aquí y puede guardar algo de memoria si su estimación es bastante precisa.

5. std::deque .

   Esta opción le permite intercambiar memoria por rendimiento. No habrá (2 ^ (N + 1) - 1) veces la copia del elemento, solo N veces la asignación y ninguna desasignación. Además, tendrá un tiempo de acceso aleatorio constante y la capacidad de agregar nuevos elementos en ambos extremos.

De acuerdo con std::deque-cppreference

Por otro lado, los deques típicamente tienen un gran costo de memoria mínimo; una retención que tiene solo un elemento tiene que asignar su matriz interna completa (por ejemplo, 8 veces el tamaño del objeto en libstdc ++ de 64 bits; 16 veces el tamaño del objeto o 4096 bytes, el que sea mayor, en libc ++ de 64 bits)

o puedes usar el combo de estos:

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

   Esto es similar a std :: deque, la diferencia es que este contenedor no admite agregar elementos en la parte frontal. Pero aún es más rápido en rendimiento, debido al hecho de que no copiará el std :: array subyacente durante (2 ^ (N + 1) - 1) veces, solo copiará el conjunto de punteros por (2 ^ (N - M + 1) - 1) veces, y la asignación de una nueva matriz solo cuando la corriente está llena y no necesita desasignar nada. Por cierto, puede obtener un tiempo de acceso aleatorio constante.

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

   Facilita enormemente la presión de la fragmentación de la memoria. Solo asignará una nueva matriz cuando la corriente esté llena y no necesita copiar nada. Aún tendrá que pagar el precio de un puntero adicional configurado para el combo 1.

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

   Igual que 2, pero cuesta la misma memoria que el combo 1.

Answer 3

Estás asumiendo erróneamente que tu implementación de C ++ elegida es necesariamente más rápida que la de Python. El manejo de cadenas en Python está altamente optimizado. Consulte esta pregunta para obtener más información: ¿Por qué las operaciones std :: string funcionan mal?

Answer 4

No proporciono mejores soluciones (al menos en cuanto a rendimiento), pero algunos datos adicionales podrían ser interesantes.

Usando strtok_r (variante reentrante de 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);
}

Además, utiliza cadenas de caracteres para los parámetros y fgets para la entrada:

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

Y, en algunos casos, donde la destrucción de la cadena de entrada es aceptable:

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

Los tiempos para estos son los siguientes (incluidos mis resultados para las otras variantes de la pregunta y la respuesta aceptada):

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

Como podemos ver, la solución de la respuesta aceptada es aún más rápida.

Para cualquiera que quiera hacer más pruebas, también coloqué un repositorio de Github con todos los programas de la pregunta, la respuesta aceptada, esta respuesta y, además, un Makefile y un script para generar datos de prueba: https://github.com/tobbez/string-splitting .

Answer 5

Si toma la implementación de split1 y cambia la firma para que coincida más con la de split2, al cambiar esto:

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

a esto:

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

Obtienes una diferencia más dramática entre split1 y split2, y una comparación más justa:

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

Answer 6

Sospecho que esto está relacionado con el almacenamiento en búfer en sys.stdin en Python, pero no con el búfer en la implementación de C ++.

Consulte esta publicación para obtener detalles sobre cómo cambiar el tamaño del búfer, luego intente de nuevo la comparación: ¿ Configurar un tamaño de búfer más pequeño para sys.stdin?

Answer 7

Sospecho que esto se debe a la forma en que se redimensiona std::vector durante el proceso de una llamada de función push_back (). Si intenta usar std::list o std::vector::reserve() para reservar suficiente espacio para las oraciones, debería obtener un mejor rendimiento. O puede usar una combinación de ambos como a continuación para 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());
}

EDITAR : La otra cosa obvia que veo es que la variable variable de Python se asigna cada vez pero no se modifica. Entonces no es una comparación justa contra C ++. Deberías intentar modificar tu código de Python para que sea dummy = [] para inicializarlo y luego hacer dummy += line.split() . ¿Puedes reportar el tiempo de ejecución después de esto?

EDIT2 : Para que sea aún más justo, puedes modificar el ciclo while en el código C ++ para que sea:

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

Answer 8

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