Große strukturierte Textdateien laden - immer langsamer

[friedemann2009]

Schönen Abend zusammen,

ich habe ein Problem mit dem Laden von großen Textdateien. Hintergrund: Ich nutze in einem Prog ein eigenes Datenformat aus verschachtelten Arrays, Dictionaries (Hash) und Records. Die Arrays werden durch verschiedene Prozesse mit zahlreichen Daten gefüllt. Um manche aufwendige BErechnungen der Daten nicht mehrfach machen zu müssen, habe ich mir eine eigene Routine geschrieben, mit der die Daten der Reihe nach in eine Textdatei geschrieben und die Datei am Ende mit ZLib komprimiert wird. Das funktioniert auch mit sehr großen Datenmengen sehr gut und schnell (wenige Sekunden). Aso, die Einzeldaten werden mit <Tags> in die Datei geschrieben.

Wenn ich die Datei jetzt wieder laden möchte, dauert das exponentiell (!) länger: also nicht nur fast eine Stunde (!), sondern auch von Einzeldatum zu Einzeldatum länger! Praktisch "lade" ich so:
- Datei dekomprimieren
- Datei in Stringlist laden
- via Schleifen und Pos() die Tags einzeln suchen, größere Einheiten kopieren, Einzeldaten darin auswerten und je nach Datentyp in die jeweiligen Container (Array usw.) verschieben.

Ich vermute stark, dass es an POS und Copy-Anweisungen liegt, aber habe keine Ahnung, wie ich das optimieren / ersetzen könnte. - Habe aber auch sehr wenig Erfahrung im Umgang mit Datenspeicherung/-laden.

Hat jemand einen Rat?

Danke und schöne Grüße,
Frieder (XE3)

[jfheins]

Hi,
also damit das wirklich exponenziell geht, da müsstest du schon was ganz falsch gemacht haben - aber kubische Laufzeit ist auch schon nicht toll.
zu deinem Problem: Du solltest dir entweder selbst einen Parser schreiben (einmal durchgehen muss reichen!) oder du wechselst das Dateiformat und nimmst einen vorhandenen Parser.
Zum Beispiel gibt es viele flotte XML Parser, und du kannst das Format relativ flexibal anpassen.
Und so als "goodie" kannst du auch eine XSD schreiben und prüfen ob eine Datei die von dir erwartete Struktur besitzt.

Falls du einen einfachen Parser schrieben willst: Da gibt es ganz viele Konzepte und es kann sehr komplex werden. Ich habe auch mal einen geschrieben, leider in java. Habe ihn dir trotzdem mal angehängt. Grob lässt sich das in einen Tokenizer einteilen, der kleine Stücke aus dem Text extrahiert ("Kleinstes Element, das eine Bedeutung hat") und dann einen teil, der die Tokens verarbeitet.
In dem Beispiel werden Objekte aus einer Datei gelesen. Jedes Objekt hat dabei seine eigene "aus der Datei laden" Funktion.
Der Parser lädt die Datei Zeilenweise und lässt dann einen RegEx auf die Zeile los. Das ist jetzt eine relativ "einfache" Methode, weil der RegEx da einige Arbeit abnimmt die man sonnst selber machen müsste.
Heraus kommt ein "Baum" an Objekten in der Variable root.

Code:

package MainPack;

import HelperClasses.TElement;
import ItemClasses.*;
import java.util.*;
import java.util.regex.*;
import javax.swing.JOptionPane;

public class TParser
{
    ArrayList<TItem> FItemArray;
    TElement root;
    
    /** Creates a new instance of TParser
     * TParser is used to parse a text file into the abstract hirachial data structure,
     * implemented by TElement. For simplicity, one root element is created which is not
     * actually in the file. all elements in the file are then added to this root element
     * as a child. After this, we can easily unserialise the while tree by talking each of
     * the root childs and calling its "toMainObject()" Method. This will return a TItem object
     * which in turn can easily be added o the ArrayList that is returned afterwards.
     */
    public TParser(ArrayList<TItem> AItemArray)
    {
   FItemArray = AItemArray;
   root = new TElement("root");
    }
    
    public void Parse(Scanner File)
    {
   File.useDelimiter(Pattern.compile("[\n]"));
   
   Pattern pnewobj =    Pattern.compile("^(new T)(.+)\\{");
   Pattern pnewchild =  Pattern.compile("^(.+)=new T(.+)\\{");
   Pattern pstrprop =   Pattern.compile("^(.+)=\"(.*)\";");
   Pattern pproperty =  Pattern.compile("^(.+)=(.+);");
   
   Matcher mnewobj;
   Matcher mnewchild;
   Matcher mstrprop;
   Matcher mproperty;
   
   String token = "";
   TElement current = null;
   
   while (File.hasNext()) // Nächste Zeile laden
   {
       token = File.next().trim();
       if (!token.equals(""))
       {      
      mnewobj =   pnewobj.matcher(token);
      mnewchild = pnewchild.matcher(token);
      mstrprop =  pstrprop.matcher(token);
      mproperty = pproperty.matcher(token);
      
      // We now get the tokens one after another, without empty tokens ...
      
      if (mnewobj.matches()) // new Item-Object to read
      {
          current = root.addRootChild(mnewobj.group(2));
          //        ^^^^ current also possible, root more error resistant
      }
      else if (mnewchild.matches()) // Child-Object
      {
          current = current.addChild(mnewchild.group(1), mnewchild.group(2));
      }
      else if (mstrprop.matches()) // String-Property to read
      {
          String str = mstrprop.group(2);
          
          str = str.replace("(\\\\)*\\n", "\n"); // replace non-escaped \n's with line break
          str = str.replace("\\\\", "\\"); // replace escaped backslashes with backslash
          
          current.addProperty(mstrprop.group(1), str);
      }
      else if (mproperty.matches()) // Other Property to read
      {
          current.addProperty(mproperty.group(1), mproperty.group(2));
      }
      else // Control-Chars
      {
          if (token.matches("\\};?")) // Klammer zu => Ebene hoch
         current = current.getParent();
          else
         System.err.println("Unrecognised token: \"" + token + "\"");
      }
       }
   }
   
   int child = 0;
   int errors = 0;
   String messages = "";
   
   for (Object elem : root.getRootChilds())
   {
       try
       {
      FItemArray.add(((TElement)elem).readMainObject());
       }
       catch (IllegalArgumentException e)
       {
      errors++;
      messages = messages + "\n" + "root[" + child + "](" + ((TElement)elem).getObjectName() + ")." + e.getMessage();
       }
       child++;
   }
   if (errors > 0)
       JOptionPane.showMessageDialog(null, errors + " Object(s) could not be imported, as properties were invalid:" + messages, "Errors during Import", JOptionPane.ERROR_MESSAGE);
    }
}

Geparst wird ein Text, der ungefähr so aussehen sollte:

Code:

new TYearly{
   Title="My Birthday";
   Priority=30;
   DaysInAdvance=1;
   Description="My Birthday ...";
   StartDate=new TDate{
      Year=2007;
      Month=3;
      Day=16;
      Time=null;
   };

   EndDate=new TDate{
      Year=2026;
      Month=3;
      Day=16;
      Time=null;
   };

   Day=12;
   Month=3;
};

[friedemann2009]

Abend jfheinz,

danke für Deine Antwort. Ich Grunde habe ich mir ja - so denke ich mir - einen Parser geschrieben. Was mich wundert ist: Jeder Parser muss doch mit Suchen und Kopieren arbeiten; was macht dann mein Auslesen so viel langsamer?

Ich hatte das Problem schon öfters; sobald eine stringlist etwas größer wird und man sie sukzessive durcharbeiten muss (via POS/Copy), wird es bald sehr langsam.. Gibt es eine andere Alternative?

Schöne Grüße,
Frieder

[jaenicke]

Zitat von friedemann2009:

Jeder Parser muss doch mit Suchen und Kopieren arbeiten; was macht dann mein Auslesen so viel langsamer?

Ein Parser kann sehr gut mit Pointern arbeiten. Einen recht schnellen habe ich in meinem Registryeditor geschrieben:
http://www.delphipraxis.net/137675-r...rsion-7-a.html
Der schafft das Lesen und Parsen eines Registry-Exportes mit ca. zwei Dritteln der sequentiellen Festplattengeschwindigkeit.

Ein anderer Parser, den ich beruflich für eine eigene Skriptsprache geschrieben habe, arbeitet auch komplett pointerbasiert und ist dadurch sehr schnell. Denn der Quelltext an sich bleibt wo er ist, zur Analyse wird nur ein PChar-Pointer verschoben und das auch nur in eine Richtung, sprich Single-Pass.

[friedemann2009]

Ah, ok, jetzt verstehe ich das mal. Tja, in meinem Fall hätte ich keine Ahnung, wie ich da mit Pointern arbeiten soll -, dafür fehlt mir die Erfahrung.. Ich kannte Pointer bislang nur insofern, als damit ein Zeiger auf ein komplettes Datum (also z.B. eine Integer, ein String o.ä.) verschoben werden kann. Wie aber soll man *innerhalb* eines Datums (wie eine Textdatei) einen Zeiger verschieben? Habt Ihr da zufällig einen Link fürs erste Reinschauen zur Hand?

Danke und schöne Grüße,
frieder

[friedemann2009]

Sorry, dass ich nochmal nachfrage: Ich lese gerade nochmal über Datenspeicherung via Streams. Könnte das Laden via Streams schneller gehen anstelle via Textdateien?

Danke und schönen Abend,
frieder

[jaenicke]

Die schnellste Variante sind MMFs wie ich sie in meinem Programm auch nutze.
Schau es dir einfach mal an, das ist nicht so kompliziert.

[jfheins]

Hallo,

Zitat von friedemann2009:

danke für Deine Antwort. Ich Grunde habe ich mir ja - so denke ich mir - einen Parser geschrieben. Was mich wundert ist: Jeder Parser muss doch mit Suchen und Kopieren arbeiten; was macht dann mein Auslesen so viel langsamer?
Ich hatte das Problem schon öfters; sobald eine stringlist etwas größer wird und man sie sukzessive durcharbeiten muss (via POS/Copy), wird es bald sehr langsam.. Gibt es eine andere Alternative?

Um eine einigermaßen gute Laufzeit zu bekommen, darfst du die eigentliche Datei nur einmal durchgehen. Also während des Durchgangs nicht Pos(Datei, ...) aufrufen, weil da steckt wieder eine Schleife srin. Und dann hast du vermutlich ein quadratisches Laufzeitverhalten. Du kannst z.B. immer ein Zeichen lesen (am besten hier schon irrelevante Zeichen überspringen) und in einen Puffer schreiben. Dann gucken ob in dem Puffer ein gültiges Token ist. Falls ja, Puffer leeren und Token verarbeiten (hierbei werden ggf. wieder Zeichen gelesen) und weitermachen.
Der "Trick" ist, dass der Puffer immer nur klein ist. In meinem Fall habe ich das über die Zeilen realisiert: Da die Datei Zeilenweise verarbeitet wird, habe ich immer nur einen Text von vll. 30 Zeichen, der einem Token zugeordnet werden muss.

[nuclearping]

Zitat von friedemann2009:

Ah, ok, jetzt verstehe ich das mal. Tja, in meinem Fall hätte ich keine Ahnung, wie ich da mit Pointern arbeiten soll -, dafür fehlt mir die Erfahrung.. Ich kannte Pointer bislang nur insofern, als damit ein Zeiger auf ein komplettes Datum (also z.B. eine Integer, ein String o.ä.) verschoben werden kann. Wie aber soll man *innerhalb* eines Datums (wie eine Textdatei) einen Zeiger verschieben? Habt Ihr da zufällig einen Link fürs erste Reinschauen zur Hand?

Danke und schöne Grüße,
frieder

Ist nicht so schwer, wie man sich das vielleicht denken mag.

Beispiel:

Delphi-Quellcode:

var
  MyString: String;
  MyPtr: Pointer;
begin
  MyString := 'Hallo Welt';
  GetMem(MyPtr, Length(MyString));
  try
    Move(MyString[1], MyPtr^, Length(MyString)); // "Hallo Welt" steht nun im Pointer
    
    Finalize(MyString);
    SetLength(MyString, 5);
    Move(MyPtr^, MyString[1], 5); // "Hallo" wird aus dem Pointer kopiert
  finally
    FreeMem(MyPtr);
  end;
end;

Oder:

Delphi-Quellcode:

var
  MyString: String;
  MyPtr: PChar;
  i, j: Integer;
  Found: Boolean;
begin
  MyString := '12345|Test';
  GetMem(MyPtr, Length(MyString));
  i := Integer(MyPtr); // Addresse vom Pointer merken
  try
    Move(MyString[1], MyPtr^, Length(MyString));
    Found := FALSE;
    j := 1;
    repeat
      if MyPtr^ = '|' then
        Found := TRUE; // Trennzeichen gefunden, irgendwas machen
      Inc(MyPtr^);
      Inc(j);
    until Found or (j > Length(MyString));
  finally
    MyPtr := PByte(i); // Addresse vom Pointer wiederherstellen
    FreeMem(MyPtr);
  end;  
end;

[Furtbichler]

Na ja, Leute. Wenn mit 'Pointer' wirklich ein PChar gemeint ist, dann ist das 'Optimieren auf hohem Niveau'. Damit kann man sein Programm um einen Faktor X (so 10% schätze ich, von mir auch auch 20%) schneller machen. Auch der wirklich sinnvolle Hinweis, mit MMF einzulesen, bringt bei sehr großen Dateien eine drastische (aber konstante) Verbesserung (wieder um einen Faktor).

Hier geht es aber zunächst um das Verfahren. alsp das 'wie'. Die Vorredner haben hier Recht: Einen Parser kann man mit einer Komplexität von O(n) hinbekommen, d.h. er verhält sich von der Laufzeit so, das er bei einer Verdoppelung der Inputlänge auch nur doppelt so lange für die Verarbeitung braucht.

Dein Algorithmus scheint bei mindestens O(n^2) zu liegen (d.h. er vervierfacht die Zeit bei Verdopplung der Input-größe), aber wie sollen wir wissen, wie wir dir helfen können, wenn wir noch keine Zeile Code gesehen haben?

Zitat von friedemann2009:

Praktisch "lade" ich so:
- Datei dekomprimieren
- Datei in Stringlist laden
- via Schleifen und Pos() die Tags einzeln suchen, größere Einheiten kopieren, Einzeldaten darin auswerten und je nach Datentyp in die jeweiligen Container (Array usw.) verschieben.

Der letzte Punkt dürfte der Entscheidende sein.