Cómo analizar flotadores separados por espacios en C ++ rápidamente?

Tengo un archivo con millones de líneas, cada línea tiene 3 flotantes separados por espacios. Lleva mucho tiempo leer el archivo, así que traté de leerlo usando archivos mapeados en memoria solo para descubrir que el problema no está en la velocidad de IO sino en la velocidad del análisis.

Mi análisis actual es tomar la secuencia (archivo llamado) y hacer lo siguiente

float x,y,z; file >> x >> y >> z; 

Alguien en Stack Overflow me recomendó usar Boost.Spirit, pero no pude encontrar ningún tutorial simple para explicar cómo usarlo.

Estoy tratando de encontrar una forma simple y eficiente de analizar una línea que se ve así:

 "134.32 3545.87 3425" 

Realmente agradeceré algo de ayuda. Quería usar strtok para dividirlo, pero no sé cómo convertir cadenas en flotadores, y no estoy seguro de que sea la mejor manera.

No me importa si la solución será Boost o no. No me importa si no será la solución más eficiente, pero estoy seguro de que es posible duplicar la velocidad.

Gracias por adelantado.

Si la conversión es el cuello de la botella (que es bastante posible), debe comenzar utilizando las diferentes posibilidades en el estándar. Lógicamente, uno esperaría que estuvieran muy cerca, pero prácticamente, no siempre:

  • Ya ha determinado que std::ifstream es demasiado lento.

  • Convertir sus datos mapeados en memoria a std::istringstream es casi seguro que no es una buena solución; primero tendrá que crear una cadena, que copiará todos los datos.

  • Escribir su propio streambuf para leer directamente desde la memoria, sin copiar (o usar el std::istrstream desuso) podría ser una solución, aunque si el problema es realmente la conversión … esto todavía usa las mismas rutinas de conversión.

  • Siempre puede probar fscanf , o scanf en su flujo mapeado en la memoria. Dependiendo de la implementación, pueden ser más rápidos que las diversas implementaciones de istream .

  • Probablemente más rápido que cualquiera de estos es usar strtod . No es necesario utilizar token para esto: strtod omite el espacio en blanco inicial (incluido '\n' ), y tiene un parámetro de salida donde no se lee la dirección del primer carácter. La condición final es un poco complicada, tu loop probablemente se parezca un poco a:

     char * begin;  // Establecer para apuntar a los datos mmap'ed ...
                     // También tendrás que organizar un '\ 0'
                     // para seguir los datos.  Esto es probable
                     // el problema más difícil.
     char * end;
     errno = 0;
     doble tmp = strtod (inicio, y fin);
     while (errno == 0 && end! = begin) {
         // haz lo que sea con tmp ...
         comenzar = fin;
         tmp = strtod (inicio y fin);
     }

Si ninguno de estos es lo suficientemente rápido, tendrá que considerar los datos reales. Probablemente tenga algún tipo de restricciones adicionales, lo que significa que potencialmente puede escribir una rutina de conversión que es más rápida que las más generales; por ejemplo, strtod tiene que manejar tanto fija como científica, y tiene que ser 100% precisa, incluso si hay 17 dígitos significativos. También tiene que ser específico de la localidad. Todo esto se agrega complejidad, lo que significa código agregado para ejecutar. Pero tenga cuidado: escribir una rutina de conversión eficiente y correcta, incluso para un conjunto restringido de entradas, no es trivial; usted realmente tiene que saber lo que está haciendo.

EDITAR:

Solo por curiosidad, hice algunas pruebas. Además de las soluciones mencionadas, escribí un convertidor personalizado simple, que solo maneja puntos fijos (no científicos), con un máximo de cinco dígitos después del decimal, y el valor antes del decimal debe caber en un int :

 double convert( char const* source, char const** endPtr ) { char* end; int left = strtol( source, &end, 10 ); double results = left; if ( *end == '.' ) { char* start = end + 1; int right = strtol( start, &end, 10 ); static double const fracMult[] = { 0.0, 0.1, 0.01, 0.001, 0.0001, 0.00001 }; results += right * fracMult[ end - start ]; } if ( endPtr != nullptr ) { *endPtr = end; } return results; } 

(Si realmente usa esto, definitivamente debería agregar algún tipo de manejo de errores. Esto se eliminó rápidamente con fines experimentales, para leer el archivo de prueba que había generado, y nada más).

La interfaz es exactamente la de strtod , para simplificar la encoding.

Ejecuté los puntos de referencia en dos entornos (en diferentes máquinas, por lo que los valores absolutos de cualquier momento no son relevantes). Obtuve los siguientes resultados:

En Windows 7, comstackdo con VC 11 (/ O2):

 Testing Using fstream directly (5 iterations)... 6.3528e+006 microseconds per iteration Testing Using fscan directly (5 iterations)... 685800 microseconds per iteration Testing Using strtod (5 iterations)... 597000 microseconds per iteration Testing Using manual (5 iterations)... 269600 microseconds per iteration 

Bajo Linux 2.6.18, comstackdo con g ++ 4.4.2 (-O2, IIRC):

 Testing Using fstream directly (5 iterations)... 784000 microseconds per iteration Testing Using fscanf directly (5 iterations)... 526000 microseconds per iteration Testing Using strtod (5 iterations)... 382000 microseconds per iteration Testing Using strtof (5 iterations)... 360000 microseconds per iteration Testing Using manual (5 iterations)... 186000 microseconds per iteration 

En todos los casos, estoy leyendo 554000 líneas, cada una con 3 puntos flotantes generados aleatoriamente en el rango [0...10000) .

Lo más llamativo es la enorme diferencia entre fstream y fscan en Windows (y la diferencia relativamente pequeña entre fscan y strtod ). Lo segundo es cuánto gana la sencilla función de conversión personalizada en ambas plataformas. El manejo de errores necesario ralentizará un poco, pero la diferencia sigue siendo significativa. Esperaba alguna mejora, ya que no maneja muchas cosas que hacen las rutinas de conversión estándar (como el formato científico, números muy pequeños, Inf y NaN, i18n, etc.), pero no tanto.

ACTUALIZAR

Como Spirit X3 está disponible para las pruebas, actualicé los puntos de referencia. Mientras tanto, he usado a Nonius para obtener puntos de referencia estadísticamente sólidos.

Todos los cuadros a continuación están disponibles en línea interactiva

El proyecto de Benchmark CMake + testdata utilizado está en github: https://github.com/sehe/bench_float_parsing

enter image description here

Resumen:

Los analizadores de Spirit son los más rápidos. Si puede usar C ++ 14 considere la versión experimental Spirit X3:

enter image description here

Lo anterior es medidas usando archivos mapeados de memoria. Usando IOstreams, será más lento en general,

enter image description here

pero no tan lento como scanf usando las llamadas a la función C / POSIX FILE* :

enter image description here


Lo que sigue son partes de la respuesta VIEJA


Implementé la versión Spirit y ejecuté un punto de referencia en comparación con las otras respuestas sugeridas.

Aquí están mis resultados, todas las pruebas se ejecutan en el mismo cuerpo de entrada (515Mb de input.txt ). Vea a continuación las especificaciones exactas.


(tiempo de reloj de pared en segundos, promedio de 2+ carreras)

Para mi sorpresa, Boost Spirit resulta ser el más rápido y elegante:

  • maneja / informa errores
  • admite +/- Inf y NaN y espacios en blanco variables
  • no hay problemas detectando el final de la entrada (a diferencia de la otra respuesta mmap)
  • se ve bien:

     bool ok = phrase_parse(f,l, // source iterators (double_ > double_ > double_) % eol, // grammar blank, // skipper data); // output attribute 

Tenga en cuenta que boost::spirit::istreambuf_iterator fue mucho más lento (15s +). ¡Espero que esto ayude!

Detalles de referencia

Todo el análisis realizado en el vector de struct float3 { float x,y,z; } struct float3 { float x,y,z; } .

Generar archivo de entrada usando

 od -f -A none --width=12 /dev/urandom | head -n 11000000 

Esto da como resultado un archivo de 515Mb que contiene datos como

  -2627.0056 -1.967235e-12 -2.2784738e+33 -1.0664798e-27 -4.6421956e-23 -6.917859e+20 -1.1080849e+36 2.8909405e-33 1.7888695e-12 -7.1663235e+33 -1.0840628e+36 1.5343362e-12 -3.1773715e-17 -6.3655537e-22 -8.797282e+31 9.781095e+19 1.7378472e-37 63825084 -1.2139188e+09 -5.2464635e-05 -2.1235992e-38 3.0109424e+08 5.3939846e+30 -6.6146894e-20 

Comstack el progtwig usando:

 g++ -std=c++0x -g -O3 -isystem -march=native test.cpp -o test -lboost_filesystem -lboost_iostreams 

Mida el tiempo del reloj de pared usando

 time ./test < input.txt 

Ambiente:

  • Linux desktop 4.2.0-42-generic # 49-Ubuntu SMP x86_64
  • CPU Intel (R) Core (TM) i7-3770K a 3.50 GHz
  • 32GiB RAM

Código completo

El código completo de la referencia anterior está en el historial de edición de esta publicación , la última versión está en github

Antes de comenzar, verifique que esta es la parte lenta de su aplicación y obtenga un arnés de prueba para medir las mejoras.

boost::spirit sería excesivo para esto en mi opinión. Prueba fscanf

 FILE* f = fopen("yourfile"); if (NULL == f) { printf("Failed to open 'yourfile'"); return; } float x,y,z; int nItemsRead = fscanf(f,"%f %f %f\n", &x, &y, &z); if (3 != nItemsRead) { printf("Oh dear, items aren't in the right format.\n"); return; } 

Verificaría esta publicación relacionada Uso de ifstream para leer flotantes o Cómo puedo tokenizar una cadena en C ++, particularmente las publicaciones relacionadas con C ++ String Toolkit Library. He usado C strtok, flujos de C ++, Boost tokenizer y lo mejor de ellos para la facilidad y el uso es C ++ String Toolkit Library.

una solución esencial sería arrojar más núcleos al problema, generando múltiples hilos. Si el cuello de botella es solo la CPU, puede reducir a la mitad el tiempo de ejecución al generar dos hilos (en CPU multinúcleo)

algunos otros consejos:

  • trate de evitar las funciones de análisis de la biblioteca tales como boost y / o std. Están llenos de condiciones de comprobación de errores y gran parte del tiempo de procesamiento se utiliza para realizar estos controles. Solo por un par de conversiones están bien, pero fallan miserablemente cuando se trata de procesar millones de valores. Si ya sabe que sus datos están bien formateados, puede escribir (o encontrar) una función C optimizada personalizada que solo hace la conversión de datos

  • utilice un gran búfer de memoria (digamos 10 Mbytes) en el que cargue trozos de su archivo y realice la conversión allí

  • divide et impera: divide tu problema en otros más pequeños y más fáciles: preprocesa tu archivo, hazlo de una sola línea, divide cada línea con el “.” caracterizar y convertir enteros en lugar de float, luego fusionar los dos enteros para crear el número flotante

Creo que una regla más importante en el procesamiento de cadenas es “leer solo una vez, un personaje a la vez”. Siempre es más simple, más rápido y más confiable, creo.

Hice un progtwig de referencia simple para mostrar lo simple que es. Mi prueba dice que este código funciona un 40% más rápido que la versión strtod .

 #include  #include  #include  #include  #include  #include  #include  using namespace std; string test_generate(size_t n) { srand((unsigned)time(0)); double sum = 0.0; ostringstream os; os << std::fixed; for (size_t i=0; i UINT_MAX/2) w = - (u - UINT_MAX/2); else w = + (u - UINT_MAX/2); double f = w / 1000.0; sum += f; os << f; os << " "; } printf("generated %f\n", sum); return os.str(); } void read_float_ss(const string& in) { double sum = 0.0; const char* begin = in.c_str(); char* end = NULL; errno = 0; double f = strtod( begin, &end ); sum += f; while ( errno == 0 && end != begin ) { begin = end; f = strtod( begin, &end ); sum += f; } printf("scanned %f\n", sum); } double scan_float(const char* str, size_t& off, size_t len) { static const double bases[13] = { 0.0, 10.0, 100.0, 1000.0, 10000.0, 100000.0, 1000000.0, 10000000.0, 100000000.0, 1000000000.0, 10000000000.0, 100000000000.0, 1000000000000.0, }; bool begin = false; bool fail = false; bool minus = false; int pfrac = 0; double dec = 0.0; double frac = 0.0; for (; !fail && off= '0' && c <= '9') { if (!begin) begin = true; if (pfrac == 0) { dec *= 10; dec += c - '0'; } else if (pfrac < 13) { frac += (c - '0') / bases[pfrac]; ++pfrac; } } else { break; } } if (!fail) { double f = dec + frac; if (minus) f = -f; return f; } return 0.0; } void read_float_direct(const string& in) { double sum = 0.0; size_t len = in.length(); const char* str = in.c_str(); for (size_t i=0; i 

A continuación se muestra la salida de consola de i7 Mac Book Pro (comstackda en XCode 4.6).

 count = 1000000 generated -1073202156466.638184 scan start scanned -1073202156466.638184 elapsed 83.34ms scan start scanned -1073202156466.638184 elapsed 53.50ms 

usar C va a ser la solución más rápida. Divide en tokens usando strtok y luego strtof en float con strtof . O si conoce el formato exacto, use fscanf .