Die letzten n Zeilen einer Textdatei lesen

Hi!

Wie bekomme ich es performant hin, die letzten n Zeilen einer Textdatei zu lesen? Problem ist, dass die Datei schon mal ein paar MB groß sein kann, es soll aber nur eine minimale Verzögerung auftreten.

getline() bis zum Ende wäre da schon zu langsam.

Gibt es da irgendeine Möglichkeit? zB. den get-pointer ans Ende setzen und dann rückwärts immer bis (\r)\n lesen oder sonstwie... keine Ahnung...

Danke jedenfalls

SeppJ

Du kannst beispielweise mit seekg direkt ans Ende springen. Dies könnte dabei helfen:
http://www.cplusplus.com/reference/iostream/ios_base/seekdir/
http://www.cplusplus.com/reference/iostream/istream/seekg/

Von dort an, gehst du dann entsprechend rückwärts.

Danke erstmal, soweit war ich schon.
Wie gehe ich denn rückwärts? Muss das Zeichenweise geschehen? Ist das schnell? Oder geht das auch zeilenweise?

SeppJ

Ich meinte damit, dass du je nachdem, was du schon über deine Datei weißt, etwas zurückspringst und dann einliest. Wenn du beispielsweise weißt, wie lang eine Zeile ist, springst du direkt nach Ende-Zeilenlänge. Wenn du sowas nicht weißt, wirst du dich Stück für Stück vortasten müssen. Welche Blockgröße dabei optimal ist, hängt wahrscheinlich wieder davon ab, was für Zeilenlängen du erwartest und wie das Medium von dem du liest genau funktioniert.

Das ist performancetechnisch auf jeden Fall schneller als die Datei von Anfang an zu lesen. Und weil das Kommando tail aus den GNU coreutils macht das genauso, deswegen nehme ich mal an, dass dieser Weg ziemlich optimal ist. Du kannst dir ja mal den Source von tail angucken, falls es wirklich auf jede Sekunde ankommt und du die Blockgröße optimieren musst. Das Programm ist jedoch in C geschrieben und falls du Programmieranfänger bist, wirst du nicht viel davon verstehen.

Sofern du dich an die GPL hälst, kannst du natürlich auch gleich den Code von tail übernehmen.

tail.c: 2000 Zeilen ok, aber linux-typischer Frickelcode nicht. Sorry, das guck ich mir nicht durch.

Ich soll also fstream::read() eine negative streamsize übergeben?

Eine Zeile in der Datei ist im Durchschnitt 120 Zeichen lang, ist aber unterschiedlich.
Blockgröße optimieren, so weit muss ich wohl auch nicht gehen. Ich möchte insgesamt maximal 100 Zeilen vom Ende auslesen.

Ist nur wichtig, dass auch wenn die Datei so 10 MB groß ist, es deutlich unter einer Sekunde dauert.
Aber mit dem Filepointer sollte es ja unabhängig der Dateigröße immer gleich schnell gehen, nur abhängig davon, wieviel ich dann damit einlese, nicht?

Also geht das jetzt so einfach wie getline() nur rückwärts mit read() oder kommt da Magie ins Spiel?

volkard

Recht einfach zu programmieren ist wohl: Liest die letzten 1000 bytes ein, geht durch und merke Dir die Zeilenanfänge in einem vector. und schau dann, ob's genügend zeilen sind. immer, wenns noch nicht genügend zeilen sind, verdopple die größe bis maximal zur dateigröße.

Hehe, genau das hab ich gerade gemacht.
Geht es nicht noch einfacher? Kann man nicht rückwärts lesen bis \n? Wäre doch komisch...

Nanyuki

Ich brauchte auch ein tail für Windows, hab es mir also selbst gebaut (gibt es mit Sicherheit zwar schon...).

Wenn du es gebrauchen kannst, bedien dich...
ist natürlich anders als das "echte" tail nicht gründlich auf Herz und Nieren geprüft. Außerdem werden alle leeren Zeilen am Ende der Datei ignoriert. Falls das Verhalten für dich unpassend ist, musst du es noch leicht abändern.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <string>

class ReverseReader
{
  public:
    ReverseReader(const std::string& fileName,int numberOfLines,int estimatedAvgLineLength=80)
    : stream(fileName.c_str(),std::ios::ate|std::ios::binary), currentLine(0), cpos(-1), totalLines(numberOfLines),
      avgLineLength(estimatedAvgLineLength), lastLinePos(0)
    {
      if (stream.tellg()==0)return;
      try {while (currentLine<totalLines)readLine();}
      catch (int) {}
      printAllLines();
    }

  private:
    void fillVector()
    {
      int blockSize=std::min(int((totalLines-currentLine)*avgLineLength*1.3),int(stream.tellg()));
      if (blockSize<=0 || !stream.good())return;
      stream.seekg(-blockSize,std::ios::cur);
      buf.resize(lastLinePos);
      buf.insert(buf.begin(),blockSize,0);
      stream.read(&buf[0],blockSize);
      stream.seekg(-blockSize,std::ios::cur);
      cpos+=blockSize;
      lastLinePos+=blockSize;
    }

    char peek()
    {
      if (cpos<0)fillVector();
      if (cpos<0)throw int();
      return buf[cpos];
    }

    char readChar()
    {
      char ch=peek();
      cpos--;
      return ch;
    }

    void readLine()
    {
      try {while (readChar()!='\n');}
      catch(int)
      {
        output(std::string(&buf[cpos+1],lastLinePos-cpos-1));
        throw;
      }
      output(std::string(&buf[cpos+2],lastLinePos-cpos-2));
      while (peek()=='\r')readChar();
      currentLine++;
      lastLinePos=cpos+1;
    }

    void output(const std::string& str)
    {
      if (currentLine==0 && str.empty())currentLine--;
      else lines.push(str);
    }

    void printAllLines()
    {
      while (lines.size()>0)std::cout << lines.top() << std::endl,lines.pop();
    }

    std::ifstream stream;
    int currentLine;
    int totalLines;
    int avgLineLength;
    std::vector<char> buf;
    std::stack<std::string> lines;
    int cpos;
    int lastLinePos;
};

int main(int argc,char** argv)
{
  if (argc<2)return 1;
  int n=argc>=3 ? atoi(argv[2]) : 0;
  if (n==0)n=10;
  ReverseReader reader(argv[1],n);
}

Danke erstmal.
Bevor ich mich da einarbeite: Warum ist rückwärts lesen anscheinend komplizierter als normal zu lesen?
Kann man nicht einfach den Zeiger dekrementieren und Zeichen für Zeichen, immer bis \n, einlesen?

Nanyuki

Reader schrieb:

Danke erstmal.
Bevor ich mich da einarbeite: Warum ist rückwärts lesen anscheinend komplizierter als normal zu lesen?
Kann man nicht einfach den Zeiger dekrementieren und Zeichen für Zeichen, immer bis \n, einlesen?

Weil rückwarts lesen ungewöhnlich ist. Für vorwärts lesen gibt es getline(), rückwärts lesen ist nicht vorgesehen und musst du selber machen.
Du kannst zeichenweise rückwärts bis '\n' lesen, getline() benutzen und wieder zurückspringen, sollte gehen. Da get() die Position immer um eins vorne verschiebt, müsstest du nach jedem Zeichen zwei zurückspringen.
Viel anders macht das Programm auch nicht, außer dass gleich am Anfang ein ganzer Block eingelesen wird und damit der Overhead von seekg/get entfällt.