Optimierte Behandlung von Bäumen

(Auszug aus "Perl & XML" von Erik T. Ray & Jason McIntosh)

Der wesentliche Nachteil beim Umgang mit Bäumen ist ihr enormer Verbrauch von Speicher und Verarbeitungszeit. Bei kleineren Dokumenten fällt das nicht so sehr ins Gewicht, mit wachsender Dokumentgröße und Tausenden von Knoten ändert sich das. Ein typisches Buch mit einigen hundert Seiten kann ohne weiteres einige zehntausend Knoten enthalten. Jeder dieser Knoten wird durch ein Objekt repräsentiert, dessen Erstellung Speicher und Zeit beansprucht.

Vielleicht benötigen Sie aber gar nicht den gesamten Baum? Oft tut es ein kleiner Teilbaum, für den sich dann allerdings die bequeme Bearbeitung lohnt. In diesem Fall könnte der Einsatz von XML::Twig für Sie interessant sein. (Wir haben das Modul schon in XPath vorgestellt.) Dieses Modul ermöglicht die Angabe von Teilbäumen (den »Twigs«), die Sie für die weitere Bearbeitung benötigen. Das Ergebnis ist eine interessante Mischung aus baum- und eventorientierter Verarbeitung mit einem guten Verhältnis zwischen Geschwindigkeit und Speicher einerseits und Komfort andererseits.

XML::Twig kennt drei verschiedene Operationsmodi: Den regulären, klassischen Baummodus, wie wir ihn schon kennen, den Modus »chunk« (oder »Teil«), der ebenfalls einen kompletten Baum aufbaut, aber nur einen Teil davon im Speicher hält, und einen Modus mit verschiedenen Wurzelknoten, der nur einige ausgewählte »Twigs« im Speicher hält.

Im folgenden Beispiel sehen wir die Anwendung des Modus »chunk« von XML::Twig. Die Eingabe des Programms besteht aus einem in DocBook verfaßten Buch mit mehreren <chapter>-Elementen. Solche Dokumente können enorm groß werden, hundert Megabyte und mehr sind nicht unüblich. Das Programm behandelt diese Kapitel einzeln und reduziert damit den erforderlichen Speicher auf den für die Darstellung des größten Kapitels erforderlichen Speicher.

Beispiel: Ein mit »Chunks« arbeitendes Programm

use XML::Twig;   

# Initialisierung und Aufruf des Parsers, Ausgabe des bearbeiteten "Twig"
my $twig = new XML::Twig( TwigHandlers => { "chapter" => \&process_chapter });
$twig->parsefile( shift @ARGV );
$twig->print;

# Handler für Kapitel: Verarbeitung und Ausgabe
sub process_chapter {
   my( $tree, $elem ) = @_;
   &process_element( $elem );
   $tree->flush_up_to( $elem ); # Kommentieren Sie diese Zeile einmal zur Probe aus
   # und beobachten Sie, wie der Speicherverbrauch wächst.
}

# Ein 'foo' wird an den Elementnamen angehängt
sub process_element {
   my $elem = shift;
   $elem->set_gi( $elem->gi . 'foo' );
   my @children = $elem->children;
   foreach my $child ( @children ) {
      next if( $child->gi eq '#PCDATA' );
      &process_element( $child );
   }
}

Die »Bearbeitung« des Programms besteht darin, ein »foo« an alle Elementnamen anzuhängen. Das hat nur einen Zweck: Das Programm soll etwas länger laufen, damit uns Zeit zur Überprüfung des Speicherverbrauchs bleibt. Beachten Sie die folgende Zeile in der Funktion process_chapter( ):

 $tree->flush_up_to( $elem ); 

Dieses Kommando läßt uns tatsächlich Speicher sparen. Ohne dieses Kommando wäre letzten Endes doch der komplette Baum aufgebaut worden. Der Aufruf bewirkt, daß der bislang angesammelte Teilbaum ausgegeben und verworfen wird. Dieser Vorgang wird als Flush bezeichnet. Der Speicherverbrauch entspricht dadurch jeweils dem für das aktuell gelesene Kapitel.

Soviel zur Theorie. Um das auch in der Praxis zu testen, haben wir das Programm mit einer 3 MB großen Datei getestet, erst ohne diese Zeile und dann mit. Ohne Flush benötigte das Programm nicht weniger als 30 MB. Das Verhältnis zwischen Brutto- und Nettodaten ist erschreckend – mit dem Faktor zehn war nicht ohne weiteres zu rechnen. Mit eingeschaltetem Flush waren nur ein paar Megabyte erforderlich, also ca. 90 % weniger. In beiden Fällen wird letzten Endes aber der gesamte Baum durchlaufen, die Verarbeitungszeit war also identisch. Auch hier kann man unter Umständen sparen, indem man mit mehreren Wurzelknoten arbeitet.

Mehrere Wurzelknoten erhält man, indem man die XPath-Ausdrücke der aufzubauenden Twigs spezifiziert. Sind die Twigs erheblich kleiner als das gesamte zu verarbeitende Dokument, spart man eine entsprechende Menge an Speicher und Verarbeitungszeit. In unserem Beispiel zum Chunk-Modus konnten wir nur den Speicherverbrauch reduzieren, weil die Summe aller <chapter>-Elemente eben das gesamte Dokument ist. Widmen wir uns also einem passenderen Beispiel.

Im Beispiel unten finden wir ein Programm, das erneut ein DocBook-Dokument liest und die Titel der Kapitel ausgibt – ein minimales Inhaltsverzeichnis. Für diese Information ist es offensichtlich nicht erforderlich, das gesamte Kapitel zu lesen, nur die <title>-Elemente sind von Interesse. Als Wurzelknoten geben wir daher die Titel in Form des XPath-Ausdrucks chapter/title an.

Beispiel: Ein Programm mit vielen Twigs

use XML::Twig;

my $twig = new XML::Twig( TwigRoots => { 'chapter/title' => \&output_title });
$twig->parsefile( shift @ARGV );

sub output_title {
   my( $tree, $elem ) = @_;
   print $elem->text, "\n";
}

Die entscheidende Stelle ist in diesem Fall die Zeile mit dem Stichwort TwigRoots. Der Wert dieses Schlüssels ist eine Hashreferenz mit Paaren von XPath-Ausdrücken und Handlern. Das Programm baut in diesem Fall nur die Teilbäume auf, die den angegebenen XPath-Ausdrücken entsprechen. In diesem Fall ist das nur ein Bruchteil des gesamten Dokuments, wir können also einen minimalen Verbrauch an Speicher und Zeit erwarten.

Wieviel gewinnen wir? Bei denselben Testdaten begnügte sich unser Programm mit ca. 2 MB Speicher und benötigte 13 Sekunden, verglichen mit ursprünglich 30 MB und einer vollen Minute. Der Verbrauch an Ressourcen ist also signifikant niedriger.

XML::Twig kann für baumorientierte Programme eine enorme Performancesteigerung bedeuten, setzt aber ein genaues Verständnis der verschiedenen Modi und ihrer Vor- und Nachteile voraus. Wenn die Twigs oder Chunks groß sind, werden Sie insgesamt nichts sparen.

  

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema Perl & XML bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:

Copyright © 2003 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Perl & XML" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O’Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de