eigener XML-Parser; Speicheralgorithmus gesucht

[Philipp Hasenfratz]

Hallihallo

ACHTUNG: Dies ist ein langes Posting (schreibwut); bitte erst ganz unten nachlesen, wo ___"endlich zur Frage"___ steht. Vielleicht will oder kann man nicht antworten; in dem Falle bringt auch der andere Text nix.

Einführung:

Seit gestern programmiere ich an einem eigenen XML-Parser (XML::DOM hat mir zwar sehr gut gefallen; aber meine Programme werden bei grossen XML-files einfach zu lange, weil man sich ja nur ziemlich schwerfällig durch die Struktur "browsen" kann). XPath wäre wohl die bessere Wahl, aber ich will mal wieder was eigenes basteln (ich hasse das Anwenden von Fertigprodukten).
Nun, der Parser (in Version 1.0 - d. h. er kann grad mal Start/End-Tags, Attribute und Werte einlesen; von Namespaces und Element-deklarationen keine Spur; aber wenn sich dann mal jemand (vielleicht ich selber) dafür interessiert, ist das Modul erweiterbar) ist nahezu fertig, ich hab nur noch Schwierigkeiten mit der Methode save, welche aus den Daten im RAM-Speicher den XML-stream erzeugt.

Wie wird das XML-Infoset intern verwaltet:
   Jeder Start-tag bekommt eine eindeutige pathID zugewiesen. In einem Hash (%pathes{$pathID}) stehen alle Daten zu einem solchen path (z. B. Name, Wert, Attribute, ...).
   XML-stream:
      <adressen>                        PathID : 1
         <adresse>                      PathID : 2
            <name>Hasenfratz</name>     PathID : 3
         </adresse>
         <adresse>                      PathID : 4
            <name>anderer Name</name>   PathID : 5
         </adresse>
      </adressen>

Die Daten des Pathes 5 sehen z. B. so aus:

$pathes{'5'} = {
   ChildOf => '4',  # Das <name>-Element ist Untermenge des Pathes 4
   NodeValue => 'anderer Name',
   NodeType  => 2,  # NodeType 2 : end-point, enthält also einen Wert
   NodeName  => 'name',
   Attributes => {...},
   ...
}

Nun geht es darum den XML-stream aus diesen Informationen wiederherzustellen:

Eine rekursive Lösung habe ich bereits erarbeitet, die ist auch nicht schwer:

sub _iterate
{
   my $self   = shift;
   my $pathID = shift;
   my $XMLstreamPtr = shift;
   $$XMLstreamPtr .= "<startTag>";
   my @subPathes = $self->getChilds($pathID);
   foreach (@subPathes)
   {
      $self->_iterate($_, $XMLstreamPtr);
   }
   $$XMLstreamPtr .= "<endTag>";
}

Nun, bei sehr grossen XML-files wird's wohl etwas kritisch mit dem Speicher (besonders, wenn viele XML-files auf dem Webserver geparsed werden müssen). Also möchte ich eine "lineare" Methode anwenden. Habe auch schon was gebastelt, aber ich bin irgendwie unfähig, dem Programm zu sagen, dass Tag's auch geschlossen werden sollen.

Endlich zur Frage:
Kann mir jemand ein (programmiertechnisch einfach zu implementierendes) Kriterium geben, wann, welcher und wieviele Tags geschlossen werden. Ich dachte etwa an folgendes, scheint aber nicht zu funktionieren:

while ( ... solange nach dem aktuellen path noch ein Element
        auf der gleichen "Ebene" kommt )
{
   schliesse den Tag und...
   $currentPathID = Das Vaterelement(parentPathID) vom $currentPathID
}

Sorry für das lange Posting

Philipp

[Philipp Hasenfratz]

Hallihallo

Vielleicht noch anders formuliert:

sub saveTheShit
{
   my $self = shift;
   my $XMLstream='';

my @pathIDs = sort {$a <=> $b} keys %{$self->{Nodes}};
   # @pathIDs enthält nun _alle_ pathes (sortiert).

while ( my $pathID = shift @pathIDs )
   {
      # Aktueller Path/Element ausgeben
      [...]
      $XMLstream .= " <$elementName $elementAttributes>\n ";

if ($self->isEndPoint($pathID))
      {
         # keine weiteren Unterelemente mehr, path fertig.
         $XMLstream .= "$elementValue";
         my $nextPathID = $pathIDs[0];
        $XMLstream .= $self->_closeTagAlgorithm($pathID, $nextPathID)
      }
   }
}

so, nun ist die Frage: wie muss diese _closeTagAlgorithm Methode beschaffen sein, dass die den String zurückgibt, der die geöffneten Tags beendet?

Viele Grüsse

Philipp

[Philipp Hasenfratz]

Hallihallo zusammen

OK. Nach langem umherprogrammieren (-pröbeln) und langen Analysen, was zu tun ist, habe ich die Lösung gefunden.

Wiedereinmal hab ich den Wald vor lauter Bäumen nicht gesehen...

Danke und sorry

Philipp

[Christian Kruse]

Hoi,

OK. Nach langem umherprogrammieren (-pröbeln) und langen Analysen,
was zu tun ist, habe ich die Lösung gefunden.

*narF* haettest du das nicht etwas frueher sagen koennen? ;-)

Gruesse,
 CK

[Philipp Hasenfratz]

Hallihallo

*narF* haettest du das nicht etwas frueher sagen koennen? ;-)

Ei, ich hatte es befürchtet. Entschuldige. Nur leider kann ich mein Hirn nicht entsprechend steuern, dass ich sagen kann, wann ich welches Problem gelöst habe. <leider>

sorrrrry

Philipp

[Christian Kruse]

Hoi,

*narF* haettest du das nicht etwas frueher sagen koennen? ;-)

Ei, ich hatte es befürchtet. Entschuldige.

Ach, mensch, nimms nicht so ernst. Das war ein Witz. Ich haette mich
ja auch gar nicht dran setzen brauchen.

Nur leider kann ich mein Hirn nicht entsprechend steuern, dass ich
sagen kann, wann ich welches Problem gelöst habe. <leider>

Schon gut ;-)

Gruesse,
 CK

[Christian Kruse]

Hoi,

ACHTUNG: Dies ist ein langes Posting (schreibwut)

So lang ists doch gar nicht?

Seit gestern programmiere ich an einem eigenen XML-Parser

Der Sinn sei dahingestellt ;-) es gibt auch SAX-Parser fuer Perl

Wie wird das XML-Infoset intern verwaltet:
   Jeder Start-tag bekommt eine eindeutige pathID zugewiesen. In
einem Hash (%pathes{$pathID}) stehen alle Daten zu einem solchen
path (z. B. Name, Wert, Attribute, ...).
   XML-stream:
      <adressen>                        PathID : 1
         <adresse>                      PathID : 2
            <name>Hasenfratz</name>     PathID : 3
         </adresse>
         <adresse>                      PathID : 4
            <name>anderer Name</name>   PathID : 5
         </adresse>
      </adressen>

[...]

Eine rekursive Lösung habe ich bereits erarbeitet, die ist auch
nicht schwer:

[... rekursive Loesung ...]

Nun, bei sehr grossen XML-files wird's wohl etwas kritisch mit
dem Speicher (besonders, wenn viele XML-files auf dem Webserver
geparsed werden müssen).

Seh ich nicht so.

Also möchte ich eine "lineare" Methode anwenden. Habe auch schon
was gebastelt, aber ich bin irgendwie unfähig, dem Programm zu
sagen, dass Tag's auch geschlossen werden sollen.

Das das langsamer ist, weisst du? Nunja, ich hab dir da mal was
geschrieben, allerdings nicht in das Paket verpackt (hatte ich keinen
Nerv zu):

sub saveXML($) {
  my $pathes        = shift;
  my $AlreadyClosed = {};

foreach my $path (sort { $a <=> $b } keys %$pathes) {
    if($pathes->{$path}->{NodeType} == 0) { # really easy
      print '<'.$pathes->{$path}->{NodeName}.attributes($path,$pathes)."/>\n";
    }
    elsif($pathes->{$path}->{NodeType} == 1) { # really easy
      print '<'.$pathes->{$path}->{NodeName}.attributes($path,$pathes).'>'.$pathes->{$path}->{NodeValue}.'</'.$pathes->{$path}->{NodeName}.">\n";
    }
    elsif($pathes->{$path}->{NodeType} == 2) {
      print '<'.$pathes->{$path}->{NodeName}.attributes($path,$pathes).">\n";
    }

if(shallClose($path,$pathes)) {
      print closeString($path,$pathes,$AlreadyClosed);
    }
  }
}

hier werden die end-tags zusammengesetzt

sub closeString($$$) {
  my $path   = shift;
  my $pathes = shift;
  my $ac     = shift;
  my $retval = '';

# sicher ist hier eine shift-push-Loesung besser
  my @keys   = sort { $a <=> $b } keys %$pathes;

for(my $i=$path;$i!=0;$i--) {
    # alle anderen element-typen sind schon geschlossen
    next if $pathes->{$i}->{NodeType} != 2;

# es gibt noch element, die tiefer oder gleich stehen in der Hierarchie
    next if grep { $pathes->{$_}->{ChildOf} >= $i } @keys[$path..$#keys];

# schon geschlossen worden
    next if $ac->{$i};

$retval .= '</'.$pathes->{$i}->{NodeName}.">\n";
    $ac->{$i} = 1;
  }

return $retval;
}

soll der Tag geschlossen werden?

geschlossen werden soll dann, wenn das darauf

folgende element Kind eines Uebergestellten Kindes ist (kleinere

Path-ID) oder kein Kind mehr folgt

sub shallClose($$) {
  my $path   = shift;
  my $pathes = shift;

if(exists $pathes->{$path+1}) {
    return $pathes->{$path+1}->{ChildOf} < $pathes->{$path}->{ChildOf};
  }

return 1;
}

attribut-strings setzen

sub attributes($$) {
  my $path   = shift;
  my $pathes = shift;
  my $retval = '';

$retval .= ' '.$_.'="'.$pathes->{$path}->{Attributes}->{$_}.'"' foreach (keys %{$pathes->{$path}->{Attributes}});

return $retval;
}

Aufgerufen wird das Ganze mit

saveXML($pathes);

Als Testdaten hatte ich:

my $pathes = {
  1 => {
    ChildOf    => 0,
    NodeValue  => '',
    NodeType   => 2,
    NodeName   => 'element1',
    Attributes => {}
  },
  2 => {
    ChildOf    => 1,
    NodeValue  => '',
    NodeType   => 2,
    NodeName   => 'element2',
    Attributes => {x => 'y'}
  },
  3 => {
    ChildOf    => 2,
    NodeValue  => '',
    NodeType   => 2,
    NodeName   => 'element3',
    Attributes => {}
  },
  4 => {
    ChildOf    => 2,
    NodeValue  => '',
    NodeType   => 2,
    NodeName   => 'element4',
    Attributes => {}
  },
  5 => {
    ChildOf    => 4,
    NodeValue  => 'xyz',
    NodeType   => 1,      # NodeType 2 : end-point, enthält also einen Wert
    NodeName   => 'element5',
    Attributes => {}
  },
  6 => {
    ChildOf    => 4,
    NodeValue  => '',
    NodeType   => 0,
    NodeName   => 'element6',
    Attributes => {x => 'y',z => 'a'}
  },
  7 => {
    ChildOf    => 3,
    NodeValue  => 'xxx',
    NodeType   => 1,
    NodeName   => 'element7',
    Attributes => {x => 'z', y => 'a'}
  },
  8 => {
    ChildOf    => 2,
    NodeValue  => 'xxx',
    NodeType   => 1,
    NodeName   => 'element8',
    Attributes => { x => 'y' }
  }
};

Das Problem bei dieser Loesung ist allerdings, dass durch das
dauernde Splice im grep() (sub closeString) das bei groesseren
Dokumenten durchaus sehr langsam werden kann. Da kann man sich eine
shift-push-Methode noch ueberlegen, hatte ich aber keine Lust zu.
Ein bisschen sollst du ja auch noch tun ;-)

Gruesse,
 CK

[Philipp Hasenfratz]

Hallihallo

ACHTUNG: Dies ist ein langes Posting (schreibwut)

So lang ists doch gar nicht?

Verglichen mit deinem von vorhin wirklich nicht ;)
Da hattest du dir ja wirklich Zeit genommen, wofür ich mich herzlich bedanken will!

Seit gestern programmiere ich an einem eigenen XML-Parser

Der Sinn sei dahingestellt ;-) es gibt auch SAX-Parser fuer Perl

Ja, mit dem hab ich auch schon herumgealbert, aber der ist mir etwas zu "linear". Ich meine, dass die Grundansätze von XML::DOM schon ganz OK sind, nur dass die Navigation durch die Nodes etwas schwerfällig ist. Deshalb auch meine "billige" Path Navigation. Wirklich ganz simpel, aber so wollte ich da auch.

Nun, bei sehr grossen XML-files wird's wohl etwas kritisch mit
dem Speicher (besonders, wenn viele XML-files auf dem Webserver
geparsed werden müssen).

Seh ich nicht so.

Meinst du? - Ich könnte mir vorstellen, dass hier einige Probleme entstehen können. Wobei ich mich mit der Speicherorganisation von perl nicht so gut auskenne, so denke ich doch, dass dieses Verfahren zumindest mehr Speicher benötigt, als eine lineare.

Das das langsamer ist, weisst du? Nunja, ich hab dir da mal was
geschrieben, allerdings nicht in das Paket verpackt (hatte ich keinen
Nerv zu):

Vielen herzlichen Dank! - Und klar: du brauchst mir ja auch nicht alles auf dem silbernen Tablett zu servieren.

[... deine Lösung ...] (mehr folgt im E-Mail)

Das Problem bei dieser Loesung ist allerdings, dass durch das
dauernde Splice im grep() (sub closeString) das bei groesseren
Dokumenten durchaus sehr langsam werden kann. Da kann man sich eine
shift-push-Methode noch ueberlegen, hatte ich aber keine Lust zu.
Ein bisschen sollst du ja auch noch tun ;-)

;)
Klaro ;)

Viele Grüsse

Philipp

[Christian Kruse]

Hoi,

Verglichen mit deinem von vorhin wirklich nicht ;)
Da hattest du dir ja wirklich Zeit genommen, wofür ich mich
herzlich bedanken will!

Na, so lang auch wieder nicht. Laenger als eine halbe Stunde wars
sicher nicht.

Meinst du? - Ich könnte mir vorstellen, dass hier einige Probleme
entstehen können. Wobei ich mich mit der Speicherorganisation von
perl nicht so gut auskenne, so denke ich doch, dass dieses
Verfahren zumindest mehr Speicher benötigt, als eine lineare.

Ich habe mit dem XML::DOM auf dem Server das gesamte Archiv 2001
geparsed und dann wieder zurueck geschrieben, und der arbeitet auch
rekursiv. Das ist kein Problem ;-) Sicher braucht das mehr Speicher,
aber der sollte heute nicht mehr so sehr ins Gewicht fallen, wenn du
nicht gerade Dokumente von einigen zig mb parsed.

[... deine Lösung ...] (mehr folgt im E-Mail)

Ok, aber bitte an mailto:[e-mail]

Gruesse,
 CK

[Philipp Hasenfratz]

Hallihallo

Ich habe mit dem XML::DOM auf dem Server das gesamte Archiv 2001
geparsed und dann wieder zurueck geschrieben, und der arbeitet auch
rekursiv. Das ist kein Problem ;-) Sicher braucht das mehr Speicher,
aber der sollte heute nicht mehr so sehr ins Gewicht fallen, wenn du
nicht gerade Dokumente von einigen zig mb parsed.

OK. Ich bin einverstanden ;-)
Vielleicht nehm ich einfach die Rekursive. Sieht auch viel besser aus (Code ist etwa halb so gross).
Gut, könnte sein, dass mein PC streikt (64MB sind nicht sehr viel ;) ); aber solange der Webserver etwas mehr hat ...

Viele Grüsse

Philipp

[Christian Kruse]

Hoi,

Gut, könnte sein, dass mein PC streikt (64MB sind nicht sehr viel ;)
); aber solange der Webserver etwas mehr hat ...

Wenn ein Script mehr als 64MB RAM brauchst, ist das eindeutig zu viel.

Gruesse,
 CK

[Philipp Hasenfratz]

Hallihallo

Wenn ein Script mehr als 64MB RAM brauchst, ist das eindeutig zu viel.

Als Faustregel lass ich dies gelten, aber...
 - Mein Windows, die mySQL Datenbank, notepad.exe, perl und einige Drivers brauchen auch RAM
 - Der Speicherbedarf der Scripte hängt auch von der Grösse eingelesener Daten ab (das habe ich eigentlich gemeint)

Viele Grüsse

Philipp

[Michael Schröpl]

Hi Philipp,

Wenn ein Script mehr als 64MB RAM brauchst, ist das eindeutig zu viel.

• Mein Windows, die mySQL Datenbank, notepad.exe, perl und einige
     Drivers brauchen auch RAM

Und das nicht zu knapp.

• Der Speicherbedarf der Scripte hängt auch von der Grösse eingelesener
     Daten ab (das habe ich eigentlich gemeint)

Selbst ohne diese Daten kommen mit 64 MB RAM schon für die eingesetzte
Grund-Software eher knapp vor:

• Ein instabileres Windows als NT würde ich nicht anraten, und
• NT oder besser mit mageren 64 MB und dann auch noch eine Anwendung
    mit Datenbank dazu, das wird kein ungetrübtes Vergnügen.

Viele Grüße
      Michael
(der auf seinem Arbeitsplatz-PC mit WinNT 4 öfters über die nur 128 MB
 flucht - und da ist keine Datenbank mit drauf)

[Philipp Hasenfratz]

Hallihallo Michael

Wenn ein Script mehr als 64MB RAM brauchst, ist das eindeutig zu viel.

• Mein Windows, die mySQL Datenbank, notepad.exe, perl und einige
     Drivers brauchen auch RAM

Und das nicht zu knapp.

Tja. Ist eben Windoof, der schlimmste PC-Virus in Person, äh, Software.

• Der Speicherbedarf der Scripte hängt auch von der Grösse eingelesener
     Daten ab (das habe ich eigentlich gemeint)

Selbst ohne diese Daten kommen mit 64 MB RAM schon für die eingesetzte
Grund-Software eher knapp vor:

Mir auch, aber mein Computer is eben schon ein bisschen alt...
Gut: Wenn ich Pascal programmiere, mache ich das immer noch auf meinem alten 386-er. Da hat programmieren noch was bedeutet! - Heute, na, ja, who cares about some bytes more or less??? - No one does!
Na, ja, mein perl funktioniert leider nicht auf dem 386 (386sx => keine 32bit, kein Win32 )

• Ein instabileres Windows als NT würde ich nicht anraten, und
• NT oder besser mit mageren 64 MB und dann auch noch eine Anwendung
    mit Datenbank dazu, das wird kein ungetrübtes Vergnügen.

Tja. Und als Server muss mein PC zuletzt fungieren...
NT, nicht mit mir (als privat/desktop PC; als Server, naja, besser als Win95 sicherlich)! - Win95 :-)
Bei Microschrott gilt die Devise: Je älter desto stabiler ;-)

Viele Grüsse

Philipp

PS: Bitte keine Antworten auf die Microschrott-anspielungen, ich weiss dass hier die Wege scheiden und jeder ein klein wenig recht hat.

[Michael Schröpl]

Hi Philipp,

Na, ja, mein perl funktioniert leider nicht auf dem 386
(386sx => keine 32bit, kein Win32 )

Ich habe schon mal irgendwo ein Perl für DOS gesehen.

Es drohte für ein Projekt gebraucht zu werden, das auf einem PC hätte
laufen müssen, dem mehr als DOS nicht zuzumuten war, der aber eine
Hardware- und Software-Konfiguration besaß, die als unersetzlich gelten
durfte ... (Insbesondere lief die darauf installierte Anwendung, deren
Daten hätten weiter verarbeitet werden müssen, nur unter DOS und galt
eigentlich seit Jahren als "weggeworfen" - kein aktueller Quelltext und
keine Entwicklungsumgebung mehr greifbar - lief aber immer noch produk-
tiv ... der Kunde zahlte unfreundlicherweise einfach weiter. ;-)

Viele Grüße
      Michael

[Philipp Hasenfratz]

Hallihallo Michael

Na, ja, mein perl funktioniert leider nicht auf dem 386
(386sx => keine 32bit, kein Win32 )

Ich habe schon mal irgendwo ein Perl für DOS gesehen.

Oh, cool. Muss mich mal ans Suchen machen, das wäre ja erste Sahne. Perl auf einem 386-er, ned schlecht.
Nur leider wird's dann wohl etwas kompliziert mit TCP/IP, Sockets, Multithread/fork, ...

Vielleicht noch hierzu: (für alle die denken, dass es unter DOS kein Internet gibt)
Borland hat ein neues Produkt in Bearbeitung. Die neue Delphi Version soll mit einem Compilerschalter nun auch DOS tauglich werden (in _vollen Zügen_, meine ich) und dies sogar mit TCP/IP Unterstützung!!! - Diese Funktionalität ist für Konsolencomputer gedacht, die über SOAP (o. ä.) dann auf den Mainframe zugreifen...
Mal schaun', ob daraus was wird.

Es drohte für ein Projekt gebraucht zu werden, das auf einem PC hätte
laufen müssen, dem mehr als DOS nicht zuzumuten war, der aber eine
Hardware- und Software-Konfiguration besaß, die als unersetzlich gelten
durfte ... (Insbesondere lief die darauf installierte Anwendung, deren
Daten hätten weiter verarbeitet werden müssen, nur unter DOS und galt

Ein Fall für Michael, der die Daten wiederherstellt ;-)
Ja, rette was zu retten ist ;-)

eigentlich seit Jahren als "weggeworfen" - kein aktueller Quelltext und
keine Entwicklungsumgebung mehr greifbar - lief aber immer noch produk-
tiv ... der Kunde zahlte unfreundlicherweise einfach weiter. ;-)

Ui, das ist _übelst_.

Viele Grüsse

Philipp

[Christian Kruse]

Hoi,

Oh, cool. Muss mich mal ans Suchen machen, das wäre ja erste
Sahne. Perl auf einem 386-er, ned schlecht.
Nur leider wird's dann wohl etwas kompliziert mit TCP/IP,
Sockets, Multithread/fork, ...

TCP/IP? Wieso? Das gibts auch fuer DOS. Schau mal bei MS vorbei.

Vielleicht noch hierzu: (für alle die denken, dass es unter DOS
kein Internet gibt)

Das erste Internet gab es *nur* unter Dos. Ich habe noch unter DOS
gesurft ;-) naja, gut, surfen kann mans eigentlich nicht nennen.

Gruesse,
 C'gaehn'K

P. S.: bist du eigentlich noch wach oder schon wieder? ;-)

[Christian Kruse]

Hoi,

• Mein Windows, die mySQL Datenbank, notepad.exe, perl und einige
  Drivers brauchen auch RAM

Sind diese Programme Scripte? ;-)

• Der Speicherbedarf der Scripte hängt auch von der Grösse
  eingelesener Daten ab (das habe ich eigentlich gemeint)

Ja, richtig. Aber 64MB Daten im Speicher zu halten ist IMHO relativ
idiotisch.

Gruesse,
 CK