Wie parsen Space-getrennte Floats in C ++ schnell?

Ich habe eine Datei mit Millionen von Zeilen, jede Zeile hat 3 schwimmt durch Leerzeichen voneinander getrennt. Es braucht eine Menge Zeit, die Datei zu Lesen, also versuchte ich, Sie zu Lesen, über die memory-mapped-Dateien, nur um herauszufinden, dass das problem nicht mit der Geschwindigkeit der IO, sondern mit der Geschwindigkeit der Analyse.

Meine aktuelle Analyse ist es, den stream (aufgerufene Datei), und führen Sie die folgenden

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

Jemand in Stack-Überlauf empfohlen, die Verwendung von Boost.Geistes, aber konnte ich nicht finden keine einfache Anleitung, um zu erklären, wie es zu benutzen.

Ich versuche zu finden, eine einfache und effiziente Art und Weise zu analysieren, eine Linie, die wie folgt aussieht:

"134.32 3545.87 3425"

Ich wirklich zu schätzen einige helfen. Ich wollte mit strtok, um es zu teilen, aber ich weiß nicht, wie konvertieren von strings, floats, und ich bin mir nicht ganz sicher, dass es der beste Weg.

Mir nichts aus, wenn die Lösung zu Steigern oder nicht. Ich habe nichts dagegen, wenn es nicht die effizienteste Lösung überhaupt, aber ich bin mir sicher, dass es möglich ist, das doppelte der Geschwindigkeit.

Vielen Dank im Voraus.

InformationsquelleAutor der Frage OopsUser | 2013-07-04

boost-spirit c++parsing

18

Wenn die Umwandlung der Flaschenhals ist (was durchaus möglich ist),
Sie sollten beginnen, indem du die verschiedenen Möglichkeiten in der
standard. Logisch, würde man erwarten, dass Sie sehr nah zu sein,
aber praktisch sind Sie nicht immer:
- Haben Sie bereits festgestellt, dass std::ifstream ist zu langsam.
- Konvertieren Sie Ihre memory-mapped Daten zu einem std::istringstream
  ist fast sicher nicht eine gute Lösung; Sie werden zunächst
  erstellen Sie ein string, das wird kopieren Sie alle Daten.
- Schreiben Sie Ihre eigenen streambuf zu Lesen direkt aus dem Speicher,
  ohne Sie zu kopieren (oder mit der veraltet std::istrstream)
  könnte eine Lösung sein, obwohl, wenn das problem wirklich ist
  Umwandlung... dies immer noch verwendet die gleiche Konvertierung Routinen.
- Können Sie immer versuchen fscanf oder scanf auf Ihrem memory-mapped
  stream. Abhängig von der Implementierung, Sie könnte schneller sein
  als die verschiedenen istream Implementierungen.
- Wahrscheinlich schneller als jede von diesen ist die Verwendung strtod. Keine Notwendigkeit
  für die tokenisierung: strtod überspringt führende Leerzeichen
  (einschließlich '\n'), und hat einen out-parameter, wo es stellt den
  Adresse des ersten Zeichens nicht Lesen. Die Ende-Bedingung ist
  ein bisschen schwierig, dein loop sollte wohl sehen ein bisschen aus wie:
```
 char* begin; //Punkt auf der mmap-ed-Daten... 
//Sie haben auch gerne für ein '\0' 
//Folgen die Daten. Dies ist wahrscheinlich 
//das schwierigste Problem. 
char* Ende; 
errno = 0; 
double tmp = strtod( begin, &end ); 
while ( errno == 0 && Ende != begin ) { 
//tun, was mit tmp... 
begin = end; 
tmp = strtod( begin, &end ); 
} 
```
Wenn keine dieser schnell genug sind, müssen Sie berücksichtigen die
die tatsächlichen Daten. Es hat wahrscheinlich eine Art von zusätzliche
Einschränkungen, was bedeutet, dass Sie kann potenziell zu schreiben
eine Konvertierungs-routine, die schneller ist als die Allgemeine;
z.B. strtod zu handhaben sind sowohl Feste als auch wissenschaftliche, und es
hat zu 100% genau, auch wenn es 17 signifikanten stellen.
Es ist auch die locale-spezifisch. All dies wird Hinzugefügt
Komplexität, was bedeutet, dass zusätzlichen code auszuführen. Aber Vorsicht:
schreiben Sie eine effiziente und korrekte Konvertierung routine, auch für
eine eingeschränkte Menge von Eingabe -, ist nicht trivial; Sie haben wirklich zu
wissen, was Sie tun.

EDIT:

Nur aus Neugier, ich habe einige tests. Zusätzlich zu den
die vorgenannten Lösungen, die ich schrieb eine einfache benutzerdefinierte Konverter,
der nur Griffe festen Punkt (nicht wissenschaftlich), mit am meisten
fünf Ziffern nach dem Komma, und der Wert vor dem dezimal
muss sich in ein 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;
}
```
(Wenn Sie tatsächlich nutzen diese, sollten Sie auf jeden Fall fügen Sie einige Fehler
die Handhabung. Dies war nur klopfte schnell für experimentelle
Zwecke, zum Lesen der Datei test würde ich erzeugt, und nichts
sonst.)

Das interface ist genau das der strtodzur Vereinfachung der Codierung.

Lief ich die benchmarks in beiden Umgebungen (auf verschiedenen Maschinen,
also die absoluten Werte aller Zeiten sind nicht relevant). Ich habe die
folgende Ergebnisse:

Unter Windows 7 kompiliert mit 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
```
Unter Linux 2.6.18 kompilieren mit 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
```
In allen Fällen, bin ich beim Lesen 554000 Linien mit jeweils 3 nach dem Zufallsprinzip
generiert floating point im Bereich [0...10000).

Das auffälligste ist der enorme Unterschied zwischen den
fstream und fscan unter Windows (und der relativ kleine
Unterschied zwischen fscan und strtod). Die zweite Sache ist
wie viel die einfache benutzerdefinierte Funktion zur Umsetzung erhält, auf
beide Plattformen. Die notwendige Fehlerbehandlung würde es langsam nach unten
ein wenig, aber der Unterschied ist immer noch signifikant. Ich erwartete
einige Verbesserung, da es nicht eine Menge Dinge behandeln, die
die standard-Konvertierung Routinen (wie dem wissenschaftlichen format,
sehr, sehr kleine Zahl, - Inf und NaN, i18n, etc.), aber nicht diese
viel.

InformationsquelleAutor der Antwort James Kanze
44

UPDATE

Da Spirit X3 für Tests verfügbar ist, habe ich aktualisiert, die benchmarks. Ich habe mittlerweile verwendet Nonius um statistisch fundierte benchmarks.

Alle charts, die unten stehen, interaktive online -

Benchmark CMake-Projekt + Testdaten verwendet, ist auf github: https://github.com/sehe/bench_float_parsing

Zusammenfassung:

Spirit-Parser sind am schnellsten. Wenn Sie können, verwenden Sie C++14 betrachten Sie die experimentelle version Spirit X3:

Die oben genannten Maßnahmen mit Hilfe von memory-mapped-Dateien. Mit IOstreams, es wird langsamer über den Vorstand,

aber nicht so langsam wie scanf mit C/POSIX FILE* Funktion ruft:

Was folgt, ist die Teile von der ALTEN Antwort
Implementiert habe ich die Spirit version, und lief ein benchmark im Vergleich zu den anderen vorgeschlagenen Antworten.

Hier meine Ergebnisse, alle tests, die auf dem gleichen Eingang (515Mb von input.txt). Siehe unten für die genauen specs.

^{(wall-clock-Zeit in Sekunden, Durchschnitt von 2+ runs)}

Zu meiner eigenen überraschung, Steigern Geist heraus, den schnellsten und elegantesten:
- Griffe/meldet Fehler
- unterstützt +/-Inf und NaN und variable Leerzeichen
- überhaupt keine Probleme erkennen das Ende der Eingabe (im Gegensatz zu den anderen mmap Antwort)
- sieht nett aus:
  
  bool ok = phrase_parse(f,l, //source iterators (double_ > double_ > double_) % eol, //grammar blank, //skipper data); //output attribute
Beachten Sie, dass boost::spirit::istreambuf_iterator war unsäglich viel langsamer (15s+). Ich hoffe, das hilft!

Benchmark-details

Alle Analyse erfolgt in vector von struct float3 { float x,y,z; }.

Generierung von input-Datei mit
```
od -f -A none --width=12 /dev/urandom | head -n 11000000
```
Diese Ergebnisse in eine 515Mb Datei mit Daten wie
```
     -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
```
Kompilieren Sie das Programm mit:
```
g++ -std=c++0x -g -O3 -isystem -march=native test.cpp -o test -lboost_filesystem -lboost_iostreams
```
Messen Wanduhr Zeit mit
```
time ./test < input.txt 
```
Umgebung:
- Linux-desktop-4.2.0-42-generic #49-Ubuntu SMP x86_64
- Intel(R) Core(TM) i7-3770K CPU @ 3.50 GHz
- 32GiB RAM
Vollständigen Code

Vollständigen code zu den alten benchmark ist in der Bearbeiten Geschichte von diesem postdie neueste version ist auf github

InformationsquelleAutor der Antwort sehe
13

Bevor Sie beginnen, stellen Sie sicher, dass dies der langsame Teil Ihrer Applikation und erhalten eine Testumgebung um ihn herum, damit Sie Messen können, Verbesserungen.

boost::spirit wäre übertrieben für diese, meiner Meinung nach. Versuchen 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;
}
```
InformationsquelleAutor der Antwort Jeff Foster
2

Ich würde check out this post Mit ifstream Lesen schwimmt oder Wie kann ich die tokenisierung ein string in C++ besonders die Beiträge im Zusammenhang zu C++ - String-Toolkit-Bibliothek. Ich habe C strtok, C++ - streams, Boost-tokenizer und die besten von Ihnen für die Leichtigkeit und verwenden Sie C++ - String-Toolkit-Bibliothek.

InformationsquelleAutor der Antwort DannyK
0

einen nitty-gritty Lösung wäre, zu werfen, mehr Kerne auf das problem, Laich mehrere threads.
Wenn der Flaschenhals ist nur die CPU kann man halbieren, unten die Laufzeit und erzeugt zwei threads (auf multicore-CPUs)

einige andere Tipps:
- versuchen zu vermeiden, parsing-Funktionen aus der Bibliothek wie boost-und/oder std. Sie sind aufgeblasen mit der Fehlerüberprüfung Bedingungen und viel der Bearbeitungszeit damit verbracht, diese Prüfungen. Nur für ein paar Konvertierungen sind Sie gut, aber Versagen kläglich, wenn es um Prozess-Millionen-Werte. Wenn Sie bereits wissen, dass Ihre Daten gut formatiert, dass Sie schreiben können (oder finden) Sie eine benutzerdefinierte optimierte C-Funktion, die nicht nur die Konvertierung der Daten
- verwenden Sie einen großen Zwischenspeicher (sagen wir mal 10 MB), in dem Sie laden die chunks der Datei und führen Sie die Konvertierung auf es
- divide et impera: teilen Sie Ihr problem in kleinere, einfacher: Vorverarbeiten Ihrer Datei haben, machen es single-line single-float, split jede Zeile, indem Sie die ". " - Zeichen und konvertieren Ganzzahlen anstelle von float, dann verschmelzen die zwei Ganzzahlen zu erstellen, die float-Zahl
InformationsquelleAutor der Antwort Gianluca Ghettini

Ich glaube, einer der wichtigsten Regel in der string-Verarbeitung ist "nur einmal gelesen, ein Zeichen zu einem Zeitpunkt". Es ist immer einfacher, schneller und sicherer, denke ich.

Ich einfach das benchmark-Programm, um zu zeigen, wie einfach es ist. Mein test sagt, dieser code läuft 40% schneller als strtod version.

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

Unten ist die Ausgabe der Konsole von i7 Mac Book Pro (kompiliert in XCode 4.6).

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

InformationsquelleAutor der Antwort 9dan

0

mit C ist die Schnellste Lösung. ~~aufsplitten in Token mit strtok und dann~~ zu konvertieren float mit strtof. Oder wenn Sie wissen das genaue format verwenden fscanf.

InformationsquelleAutor der Antwort log0

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

UPDATE

Zusammenfassung:

Benchmark-details

Umgebung:

Vollständigen Code