Algorithmische Komplexität von XML-Parsern/Validatoren

Question

Ich muss wissen, wie sich die Größe und Komplexität des Eingabedokuments auf die Leistung verschiedener XML-Tools (Parser, Validatoren, XPath-Ausdrucksauswerter usw.) auswirkt.Gibt es Ressourcen, die dokumentieren, wie sich CPU-Zeit und Speichernutzung auf ... auswirken?also was?Dokumentgröße in Bytes?Anzahl der Knoten?Und ist die Beziehung linear, polynomisch oder schlimmer?

Aktualisieren

In einem Artikel im IEEE Computer Magazine, Band 41 Nr. 9, September 2008, untersuchen die Autoren vier beliebte XML-Parsing-Modelle (DOM, SAX, StAX und VTD).Sie führen einige sehr grundlegende Leistungstests durch, die zeigen, dass der Durchsatz eines DOM-Parsers halbiert wird, wenn die Größe der Eingabedatei von 1-15 KB auf 1-15 MB oder etwa 1000x größer erhöht wird.Der Durchsatz der anderen Modelle wird nicht wesentlich beeinträchtigt.

Leider wurden keine detaillierteren Studien durchgeführt, beispielsweise zum Durchsatz/Speicherverbrauch als Funktion der Anzahl der Knoten/Größe.

Der Artikel ist Hier.

Aktualisieren

Ich konnte keine formelle Lösung für dieses Problem finden.Ich habe einige Experimente durchgeführt, um die Anzahl der Knoten in einem XML-Dokument als Funktion der Größe des Dokuments in Bytes zu messen.Ich arbeite an einem Lagerverwaltungssystem und die XML-Dokumente sind typische Lagerdokumente, z.B.Vorabversandbenachrichtigung usw.

Die folgende Grafik zeigt die Beziehung zwischen der Größe in Bytes und der Anzahl der Knoten (die proportional zum Speicherbedarf des Dokuments unter einem DOM-Modell sein sollte).Die verschiedenen Farben entsprechen unterschiedlichen Arten von Dokumenten.Der Maßstab ist Log/Log.Die schwarze Linie passt am besten zu den blauen Punkten.Es ist interessant festzustellen, dass bei allen Arten von Dokumenten die Beziehung zwischen Bytegröße und Knotengröße linear ist, der Proportionalitätskoeffizient jedoch sehr unterschiedlich sein kann.

Answer 1

Wenn ich mit diesem Problem konfrontiert wäre und bei Google nichts finden könnte, würde ich wahrscheinlich versuchen, es selbst zu lösen.

Einige „Hintergründe“-Sachen, um ein Gefühl dafür zu bekommen, wohin es führt.Aber ich müsste irgendwie eine Vorstellung davon haben, wie man einen XML-Parser macht.Informationen zu nicht-algorithmischen Benchmarks finden Sie hier:

• http://www.xml.com/pub/a/Benchmark/exec.html
• http://www.devx.com/xml/Article/16922
• http://xerces.apache.org/xerces2-j/faq-performance.html

Answer 2

Ich denke, dass es zu viele Variablen gibt, um eine einfache Komplexitätsmetrik zu erstellen, es sei denn, man trifft viele Annahmen.

Ein einfacher Parser im SAX-Stil sollte hinsichtlich der Dokumentgröße linear und hinsichtlich des Speichers flach sein.

So etwas wie XPath lässt sich nicht nur anhand des Eingabedokuments beschreiben, da die Komplexität des XPath-Ausdrucks eine große Rolle spielt.

Ebenso kann bei der Schemavalidierung ein großes, aber einfaches Schema durchaus linear sein, wohingegen ein kleineres Schema mit einer viel komplexeren Struktur eine schlechtere Laufzeitleistung aufweisen würde.

Wie bei den meisten Leistungsfragen besteht die einzige Möglichkeit, genaue Antworten zu erhalten, darin, sie zu messen und zu sehen, was passiert!

Answer 3

Rob Walker hat recht:Das Problem wird nicht detailliert genug spezifiziert.Betrachtet man nur Parser (und ignoriert die Frage, ob sie eine Validierung durchführen), gibt es zwei Hauptvarianten:baumbasiert – denken Sie an DOM – und Streaming/Ereignisbasiert – denken Sie SAXOPHON (drücken) und StAX (ziehen).Im Großen und Ganzen verbrauchen die baumbasierten Ansätze mehr Speicher und sind langsamer (da Sie das gesamte Dokument vollständig analysieren müssen), während die Streaming-/Ereignis-basierten Ansätze weniger Speicher verbrauchen und schneller sind.Baumbasierte Parser gelten im Allgemeinen als einfacher zu verwenden, obwohl StAX als enorme Verbesserung (in Bezug auf Benutzerfreundlichkeit) gegenüber SAX angepriesen wird.

Answer 4

Ich hatte vor, extrem große XML-Dateien in meine Anwendung zu laden.Ich habe die Frage hier auf Stack Overflow gestellt: Schnellstmögliche XML-Verarbeitung für sehr große Dokumente.

Und ja, es war der Parsing-Teil, der den Engpass darstellte.

Am Ende habe ich überhaupt keine XML-Parser verwendet.Stattdessen habe ich die Zeichen einzeln so effizient wie möglich analysiert und dabei die Geschwindigkeit optimiert.Dies führte zu Geschwindigkeiten von 40 MB pro Sekunde auf einem 3-GHz-Windows-PC für das Lesen, Parsen und Laden der internen Datenstruktur.

Es würde mich sehr interessieren, wie die verschiedenen XML-Parsing-Modi im Vergleich dazu abschneiden.