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

Estoy tratando de convertir algo de código de Python a C ++ en un esfuerzo por ganar un poco de velocidad y agudizar mis habilidades oxidadas de C ++. Ayer me sorprendí cuando una implementación ingenua de las líneas de lectura de stdin fue mucho más rápida en Python que en C ++ (vea esto ). Hoy, finalmente descubrí cómo dividir una cadena en C ++ con delimitadores combinados (semántica similar a split () de python), ¡y ahora estoy experimentando un deja vu! Mi código C ++ tarda mucho más tiempo en hacer el trabajo (aunque no es un orden de magnitud más, como fue el caso de la lección de ayer).

Código 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  #include  #include  #include  #include  using namespace std; void split1(vector &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 &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 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 comstacktion, 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 < 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 he intentado dos implementaciones de división diferentes. One (split1) utiliza métodos de cadena para buscar tokens y puede combinar múltiples tokens, así como manejar numerosos tokens (se trata de aquí ). El segundo (split2) usa getline para leer la cadena como un flujo, no combina delimitadores, y solo admite un único carácter delimitador (el cual fue publicado por varios usuarios de StackOverflow en respuestas a preguntas de división de cadenas).

Corrí esto varias veces en varios órdenes. Mi máquina de prueba es una Macbook Pro (2011, 8 GB, Quad Core), aunque no importa mucho. Estoy probando con un archivo de texto de 20M de línea 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 hacer la división de cadenas en C ++ que no dependa de bibliotecas externas (es decir, sin impulso), admite la fusión de secuencias de delimitadores (como la división de python), es seguro para subprocesos (por lo tanto, no strtok) y cuyo rendimiento es al menos a la par con python?

Editar 1 / Solución parcial ?:

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

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

El rendimiento de python ahora es casi el mismo que la implementación de 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 me sorprende que, incluso si Python está tan optimizado para el procesamiento de cadenas (como sugirió Matt Joiner), estas implementaciones de C ++ no sean más rápidas. Si alguien tiene ideas sobre cómo hacer esto de una manera más óptima utilizando C ++, comparta su código. (Creo que mi próximo paso será tratar de implementar esto en C pura, aunque no voy a cambiar la productividad del progtwigdor para volver a implementar mi proyecto general en C, así que esto solo será un experimento para la velocidad de división de cadenas).

Gracias a todos por vuestra ayuda.

Edición final / Solución:

Por favor vea la respuesta aceptada de Alf. Como Python se ocupa de las cadenas estrictamente por referencia y las cadenas STL a menudo se copian, el rendimiento es mejor con las implementaciones de vainilla python. A modo de comparación, 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 ingenua de python (aunque más rápida que la implementación de python que restablece / adjunta la lista, como 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 pequeña queja que queda es con respecto a la cantidad de código necesario para que C ++ se desempeñe en este caso.

Una de las lecciones aquí de este problema y el problema de la lectura de la línea estándar de ayer (enlazado arriba) es que siempre se debe establecer un punto de referencia en lugar de hacer suposiciones ingenuas sobre el rendimiento “predeterminado” relativo de los idiomas. Aprecio la educación.

Gracias de nuevo a todos por vuestras sugerencias!

Como una suposición, las cadenas de Python son cadenas inmutables contabilizadas de referencia, 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 en la oportunidad más pequeña.

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

Sin embargo, la clase std::string C ++ tiene una función de redención: es estándar , por lo que puede usarse para pasar cadenas de forma segura y portátil en lugares donde la eficiencia no es una consideración importante. Pero basta de chat. 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  #include  #include  #include  #include  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 split3( string const& str, char delimiter = ' ' ) { vector 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 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 comstacktion, obviously: // split1(spline, input_line); //split2(spline, input_line); vector 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 hay errores. No he probado la funcionalidad, pero solo he comprobado la velocidad. Pero creo que, incluso si hay un error o dos, la corrección no afectará significativamente la velocidad.

No estoy proporcionando mejores soluciones (al menos en lo que respecta al rendimiento), sino algunos datos adicionales que podrían ser interesantes.

Usando strtok_r (variante reentrante de strtok ):

 void splitc1(vector &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, mediante el uso de cadenas de caracteres para los parámetros y fgets para la entrada:

 void splitc2(vector &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, la destrucción de la cadena de entrada es aceptable:

 void splitc3(vector &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 horarios 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 sigue siendo la más rápida.

Para cualquier persona que quiera hacer más pruebas, también puse un repository de Github con todos los progtwigs 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 .

Sospecho que esto se debe a la forma en que se cambia el tamaño de std::vector durante el proceso de una llamada a la función push_back (). Si intenta usar std::list o std::vector::reserve() para reservar suficiente espacio para las oraciones, debería obtener un rendimiento mucho mejor. O puedes usar una combinación de ambos como abajo para split1 ():

 void split1(vector &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 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 dummy Python se asigna cada vez pero no se modifica. Así que no es una comparación justa con C ++. Debería intentar modificar su 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 hacerlo aún más justo, puede modificar el bucle while en el código C ++ para que sea:

  while(cin) { getline(cin, input_line); std::vector spline; // create a new vector //I'm trying one of the two implementations, per comstacktion, obviously: // split1(spline, input_line); split2(spline, input_line); count++; }; 

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

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á veces log2 (N), 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 deficiente cuando el tamaño del vector es impredecible y podría ser muy grande. Pero, si puedes estimar su tamaño, esto será un problema menor.

  2. std::list .

    Para cada push_back, el tiempo que consume es una constante, pero probablemente tome más tiempo que std :: vector en push_back individual. El uso de un grupo de memoria por subproceso 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 una causa, no puede usarlo directamente, ya que no tiene la API push_back. Pero puede definir una envoltura, y creo que es la forma más rápida aquí y puede ahorrar 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) copia del elemento, solo N veces la asignación y no habrá desasignación. Además, tendrá un tiempo de acceso aleatorio constante y la capacidad de agregar nuevos elementos en ambos extremos.

Según std :: deque-cppreference

Por otro lado, los deques típicamente tienen un costo de memoria mínimo grande; un deque que solo tiene 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 >

    Esto es similar a std :: deque, la diferencia es que este contenedor no admite agregar elementos en la parte frontal. Pero sigue siendo más rápido en rendimiento, debido a que no copiará std :: array subyacente por (2 ^ (N + 1) – 1) veces, solo copiará la matriz de punteros por (2 ^ (N – M + 1) – 1) veces, y asignando una nueva matriz solo cuando la stream está llena y no es necesario desasignar nada. Por cierto, puede obtener tiempo de acceso aleatorio constante.

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

    Gran facilidad para aliviar la presión de la estructuración de la memoria. Solo asignará una nueva matriz cuando la stream esté llena y no necesita copiar nada. Aún tendrá que pagar el precio de un puntero adicional en relación con el combo 1.

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

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

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

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

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

a esto:

 void split1(vector &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 
 void split5(vector &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; } } } 

Sospecho que esto está relacionado con el almacenamiento en búfer en sys.stdin en Python, pero no con el almacenamiento en 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 la comparación nuevamente: ¿ establecer un tamaño de búfer más pequeño para sys.stdin?