Langsame Datei lesen und in den Speicher kopieren - C++

Question

Ich lese eine Datei und speichern Sie die Daten in eine vector. Ich kann arrays nicht verwenden, da die Datengröße nicht festgelegt ist. Die Dateigröße beträgt ca. 300kb und könnte bis zu 600kb betragen. Derzeit dauert das Lesen/Speichern etwa 5 - 8 Sekunden.

Ich würde gerne wissen, was verlangsamt meine Lese-/Kopier-Methode und wie es verbessert werden könnte?

Probendaten:

0000: 4000 94 45 30 39 36 39 74 00 00 00 00 50 00 00 00 27 einige andere Informationen hier

int SomeClass::Open() 
{ 

    vector <unsigned int> memory; // where the data will be stored 
    file.open("c:\\file.txt",ios::in); 
    regex addressPattern("0000:(\\d|[a-z]){4}"); // used to extract the address from a string 
    regex dataPattern("((\\d|[a-z]){2}){16}"); // used to extract the data from a string 
    smatch match; 
    string str; // where each line will be stored 
    string data; // where the data found in each line will be stored 
    int firstAddress = -1; // -1 = address not been found 
    unsigned int sector = 0; 
    unsigned int address = 0; 
    while(getline(file,str)){ 

     if(regex_search(str,match,addressPattern) && firstAddress == -1){ 
      sector = std::stoul(match.str().substr(0,3),nullptr,16); 
      address = std::stoul(match.str().substr(5),nullptr,16); 
      firstAddress = address; 
     } 
     if(regex_search(str,match,dataPattern)){ 
      std::istringstream stream(str); 
      string data; // used to store individual byte from dataString 
      while(stream >> data){ 
       unsigned int c = std::stoul(data,nullptr,16); // convertion from hex to dec 
       memory.insert(memory.end(),c); 
      } 
     } 
    } 

    return 0; 

} 

Answer 1

Regex sind sehr mächtig, aber komplex und langsam.

Da Ihr Format vollständig statisch ist (feste Anzahl von Stellen und feste Trennzeichen dazwischen), können Sie die Konvertierung selbst durchführen, indem Sie char by char lesen. Das wird nicht sehr komplex sein.

Zum Beispiel alle Hex-Zahlen zu lesen und überprüfen Sie Leerzeichen und Semikolon:

while(getline(file,str)) 
{ 
    if(str.size()>=57) 
    { 
     int sector = hexToInt(str.data(), 4); 
     int address = hexToInt(str.data()+5, 4); 

     bool ok = ok && (sector==0) && (address>=0); 

     ok = ok && str[4] == ':'; 

     int bytes[16]; 
     for(int i=0;i<16;++i) 
     { 
      bytes[i] = hexToInt(str.data()+10+3*i, 2); 
      ok = ok && (str[9+3*i]==' ') && (bytes[i]>=0); 
     } 
    } 

    //Etc... 
} 

Funktion zum Überprüfen und Umwandeln einer Hexadezimalzeichens:

int hexCharToDigit(char c) 
{ 
    if(c>='0' && c<='9') 
    { 
     //Decimal digit 
     return (int)(c-'0'); 
    } 
    else if (str[i]>='a' && str[i]<='f') 
    { 
     //Hexadecimal lower case letter 
     return (int)(c-'a')+10; 
    } 
    else if (str[i]>='A' && str[i]<='F') 
    { 
     //Hexadecimal upper case letter 
     return (int)(c-'A')+10; 
    } 
    else 
    { 
     //Char is not a hex digit 
     return -1; 
    } 
} 

Funktion zur Überprüfung und eine n- Umwandlung digit hex to int:

int hexToInt(const char * chr, int size) 
{ 
    assert(size<8); 

    int result= 0; 
    for(int i=0;i<size;++i) 
    { 
     int hexDigit = hexCharToDigit(chr[i]); 
     if(hexDigit>=0) 
     { 
      //Valid hexadecimal digit 
      result = result << 4; 
      result += hexDigit; 
     } 
     else 
     { 
      //Char is not a hex digit as expected 
      return -1; 
     } 
    } 

    return result; 
} 

Answer 2

Dies scheint wie erwartet. Verwenden Sie Boost::Progress oder ctime, um die kostspieligen Anweisungen zu isolieren.

Vektoren werden mit zusammenhängenden Speicher in der Art von Arrays implementiert, so dass Sie dort nicht viel (wenn überhaupt) Verlangsamung sehen sollten. Die IO-Zeit der Datei ist bei einer 600kb-Datei wahrscheinlich minimal - ich würde mir vorstellen, dass sie beim Öffnen im Speicher zwischengespeichert wird. Sie können die gesamte Datei mit dem Modus-Flag ios::binary für file.open im Speicher zwischenspeichern, aber Sie müssen jede Zeile deserialisieren - die Kosten der getline-Abstraktion.

Alles in allem, der Compiler ist ziemlich gut bei der Optimierung von IO und Vektoren. Der Engpass ist wahrscheinlich die Konstruktion der Regexes (und vielleicht sogar die Regex-Übereinstimmung), die notwendig sind. Ein deterministischer endlicher Automat wird für jede Regex erzeugt: What's the Time Complexity of Average Regex algorithms?.

Answer 3

Von effektiver STL (Scott Mayers)

Für Vektor und Bindfäden growthis, indem Sie die moralische Äquivalent eines realloc behandelt, wenn mehr Platz benötigt wird. Diese realloc artige Betrieb besteht aus vier Teilen:

1. einen neuen Speicherblock zuweisen, die ein Vielfaches des Containers aktuellen Kapazität. In den meisten Implementierungen wachsen die Vektor- und String-Kapazitäten jedes Mal um einen Faktor von . d. h. ihre Kapazität wird jedes Mal verdoppelt, wenn der Container expandiert werden muss.

2. Kopieren Sie alle Elemente aus dem alten Speicher des Containers in seinen neuen Speicher.

3. Zerstöre die Objekte im alten Speicher.

4. Den alten Speicher freigeben.

So eny Zeit verwenden Sie insert Funktion (warum eröffnen Sie bitte pusk_back verwenden?), Alle 4 oben aufgeführten Schritte stattfinden. Und je mehr Elemente im Vektor enthalten sind, desto mehr Zeit ist erforderlich, um eine Einfügung durchzuführen.

Sie reserve verwenden könnten reduzieren die Zeiten Ihre Vektor neue Zuweisungen zum Beispiel benötigt:

vector<int> my_vector; 
for (int i = 0; i < 1e10; i++) 
{ 
    if (my_vector.capacity() == my_vector.size()) 
     my_vector.reserve(my_vector.capacity() + 1000) // Reserve space for 1000 more ints 
                 // now my_vector.capacity() == my_vector.size() + 1000 

    my_vector.push_back(i);        // No allocation needed here in order to expand the 
                 // vector's capacity.               
} 

Auf der anderen Seite, Steephen Kommentar, das ist wahr, regex schadet in der Regel Leistung.

Aber, wenn Sie einen Blick auf Ihre eigenen Muster nehmen, können Sie sehen, dass:

"0000:(\\d|[a-z]){4}" immer bedeutet: vier Nullen, ein Doppelpunkt und vier alphanumerische Werte.

und

"((\\d|[a-z]){2}){16}" bedeutet: einen Raum und zwei alphanumerischen Wert 16 mal.

Also mein Freund, Sie könnten iftream::read verwenden, und lesen Sie in einer Schleife alles was Sie brauchen, Zeile für Zeile.