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

leer string c++

Question

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.

Answer 1

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

Resumen:

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

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

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

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

Compila el programa 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á https://github.com/sehe/bench_float_parsing

Answer 2

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

Answer 3

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 programa 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 <iostream>
#include <sstream>
#include <iomanip>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>

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<n; ++i)
    {
        unsigned u = rand();
        int w = 0;
        if (u > 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<len; ++off)
    {
        char c = str[off];
        if (c == ''+'')
        {
            if (!begin)
                begin = true;
            else
                fail = true;
        }
        else if (c == ''-'')
        {
            if (!begin)
                begin = true;
            else
                fail = true;
            minus = true;
        }
        else if (c == ''.'')
        {
            if (!begin)
                begin = true;
            else if (pfrac)
                fail = true;
            pfrac = 1;
        }
        else if (c >= ''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<len; ++i)
    {
        double f = scan_float(str, i, len);
        sum += f;
    }
    printf("scanned %f/n", sum);
}

int main()
{
    const int n = 1000000;
    printf("count = %d/n", n);

    string in = test_generate(n);    
    {
        struct timeval t1;
        gettimeofday(&t1, 0);
        printf("scan start/n");

        read_float_ss(in);

        struct timeval t2;
        gettimeofday(&t2, 0);
        double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0;
        elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0;
        printf("elapsed %.2fms/n", elapsed);
    }

    {
        struct timeval t1;
        gettimeofday(&t1, 0);
        printf("scan start/n");

        read_float_direct(in);

        struct timeval t2;
        gettimeofday(&t2, 0);
        double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0;
        elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0;
        printf("elapsed %.2fms/n", elapsed);
    }
    return 0;
}

A continuación se muestra la salida de consola de i7 Mac Book Pro (compilada 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

Answer 4

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; // Set to point to the mmap''ed data... // You''ll also have to arrange for a ''/0'' // to follow the data. This is probably // the most difficult issue. char* end; errno = 0; double tmp = strtod( begin, &end ); while ( errno == 0 && end != begin ) { // do whatever with tmp... begin = end; tmp = strtod( begin, &end ); }

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 codificación.

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, compilado 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, compilado 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.

Answer 5

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.

Answer 6

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

Answer 7

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 .