Effizienzfrage bei TreeSet / XML-Verarbeitung

[Ajachs]

Hallo,

mein Programm hat ein Effizienzproblem, von dem ich hoffe, dass es sich beheben lässt. Die Szenerie:

Ich habe ein Korpus aus XML-Dokumenten (etwas über 90 MB), annotierte Zeitungstexte. Jedes einzelne Wort darin ist von eimem <W>-Tag umschlossen, der unter anderem das Attribut Lemma="..." enthält. [Ein Lemma ist die Wörterbuchform des konkreten Wortes; kommt zum Beispiel im Text "rätst" vor, so lautet das Lemma dazu "raten".]
Nun will ich alle diese Dokumente einlesen und aus den Daten eine Liste erstellen, die für jedes Lemma dessen Frequenz (wie oft kommt es vor), alle seine Wortformen und wiederum deren Frequenzen abspeichert, also zum Beispiel:

Lemma=raten,
Frequenz=3,
Wortform1=rätst, Frequenz1=2,
Wortform2=ratet, Frequenz2=1

Dafür habe ich eine Lemma-Klasse erstellt, die genau diese Infos pro Lemma-Objekt abspeichert. Ferner gibt es die Klasse Lemmaliste, die ein TreeSet aus Lemma-Einträgen aufbaut und verwaltet, nud eine Start-Klasse, die Pfade abfragt, lädt und speichert.

Allein das Einlesen der Dateien (mit Abspeichern der Infos) dauert etwa zwanzig Minuten. Gelesen wird mit einem SAX-Parser, weil ich die Dateien nur einmal brauche und dann nicht mehr, das dürfte gegenüber DOM effizienter sein (?). Ich habe keine Ahnung, ob das angesichts von 90 MB Daten normal ist, kommt mir aber zu langsam vor.
Die anschließende Verarbeitung nimmt noch mehr Zeit in Anspruch, insgesamt läuft das Programm rund eine Stunde. (Die Ausgabe erfolgt übrigens auch in eine XML-Datei, diese ist über 7 MB groß.)

Die Bremse vermute ich in den Datenstrukturen, genauer den TreeSets, in denen die Lemmata gespeichert werden. Da ich aber genau das will - eine sortierte Liste, bei der ich keine pauschale Obergrenze angeben muss - fällt mir da auf Anhieb keine Alternative ein ...

Meine Parser-Methode ist unspektakulär, ich erzeuge einen SAX-Parser und lasse ihn auf die Datei/en los. Die Eventhandler machen auch nichts Besonderes, extrahieren zwei Strings aus jedem <W>-Tag (eben Wort und Lemma) - dann aber werden die Funde in ein TreeSet mit Lemma-Einträgen eingefügt und, falls der Eintrag schon vorhanden ist, über das Set iteriert und die Frequenzangaben aktualisiert.
Für jedes Dokument wird ein solches TreeSet erstellt und dann vereinigt mit den bisher schon erstellten TreeSets.
Die meiste Zeit aber nimmt offenbar die Ausgabe in die XML-Datei in Anspruch (bzw. zunächst in einen großen String, der dann im letzten Schritt in die Datei geschrieben wird), auch hier wird wieder über das TreeSet iteriert.

Lässt sich anhand der Beschreibung schon etwas sagen - etwa zur Datenstruktur oder allgemeinen Herangehensweise - oder soll ich lieber Code posten?

 

[Marco13]

Viele Schritte, viele potentielle Bottlenecks,... am besten wäre ein Compilerlauf.

(bzw. zunächst in einen großen String,

Vermutlich wohl einen StringBuilder?!

 

[Ajachs]

Ha, nein, ich Depp! Und daran lags natürlich. Die Ausgabe nimmt jetzt vernünftige Zeit ein. Danke!
Bleibt das Einlesen ... Was meinst du mit Compilerlauf; die Ausführung tracen?

 

[Empire Phoenix]

pack mal am anfang ne 2 mins verzögerung ein (Thread.sleep)
in der du dich mit JVisualVm (Im bin des jdk) mit verbindest und den profiler auf cpu stellst.
Vermutungsn sind toll , aber besser mal rausfindenw o die zeit verlorengeht ehe man was bastelt.

 

[Marco13]

Vermutungsn sind toll ,
Compilerläufe auch, aber wenn man beim Bubblesort feststellt, dass die Vergleiche viel Zeit brauchen, und dann versucht, die Vergleiche zu optimieren, ist das auch blöd

Es könnte sein, dass die TreeSet da einfach nicht geeignet ist. Müßte man sich genauer ansehen / überlegen. (Evtl ist (NUR zum Beispiel!) erst Einfügen in eine Liste und anschließendes Sortieren günstiger, je nachdem, was da genau abläuft...)

Aber als eine Art "Pseudo-Compiler-Lauf" könntest du z.B. mal beim Einlesen das Erstellen und Einfügen der Daten weglassen (so das quasi nurnoch das Lesen übrig bleibt)

void readStuffFrom(XML xml)
{
    for (int i=0; i<10000; i++)
    {
        Node node = xml.getNode(i);

        // Mal kurz auskommentieren
        //MyData data = new MyData(node.x, node.y, node.z);
        //myDataStructure.add(data);
    }
}

damit man sieht, welchen Teil man sich dann genauer ansehen muss. Die VisualVM ist IMHO nicht sooo übersichtlich, wenn es um die Frage geht, WO genau wieviel Zeit drauf gegangen ist. Der TPTP ist etwas besser, aber auch nicht so leicht zu verwenden. Der Killer war "OptimizeIt" vom JBuilder - aber ziemlich teuer.
*abschweif*

 

[Ajachs]

Noch mal danke für die Antwort.

Es liegt tatsächlich nicht am Lesen, das rauscht nur so durch, wenn man die Listenoperationen wegkommentiert.
Das eigentlich Aufwändige beim Verarbeiten ist wohl die Testerei auf Doubletten. Ohne die Iterationen über die TreeSets, die überprüfen, ob ein gefundenes Lemma schon irgendwo notiert ist, ist das Programm schnell fertig (produziert dann allerdings gigantische Outputs, weil jedes Wort einzeln aufgeführt wird ).

Nun hab ich das TreeSet eigentlich extra gewählt, um leicht auf doppelte Einträge testen zu können, und ich kann ja auch mit

if ( (lliste.add(neueslemma)) == false)

testen, ob der Eintrag schon drin ist - aber ich kriege keinen Zugriff auf den Eintrag (?). Danach "muss" ich über das ganze TreeSet iterieren, um ihn zu finden. Bin ich zu blind, eine binäre Suchfunktion für TreeSets zu entdecken?

Die Collections.binarySearch nimmt mein TreeSet nicht an, ist ja auch eine AbstractCollection. =/ Ich hab mal stattdessen eine LinkedList verwendet und mir jeweils mit binärer Suche den Index des neu einzufügenden Elements geben lassen, um dann entsprechend zu reagieren. Das hat den Ablauf schon ordentlich beschleunigt.
Ein weiterer Vorteil: Die LinkedList kann trotzdem schon sortiert aufgebaut werden, weil binarySearch die Position zurückgibt, an der ein listenfremdes Element eingefügt werden muss.

 

[Marco13]

Häm? Beschreib' nochmal genauer, was du da mit dem TreeSet machst....?!

 

[Ajachs]

Entschuldigung, hab das Projekt ein paar Tage ruhen lassen, nachdem es soweit ging.

Das TreeSet war als Liste gedacht, in der Lemma-Einträge gespeichert werden. Ich brauchte einen Container, bei dem ich nicht vorher die Größe angeben muss, der sortiert ist oder sich sortieren lässt und in dem kein Eintrag doppelt vorkommt, sondern schon gefundene Einträge mit älteren unifiziert werden.
Gerade dieses Testen auf Doubletten hab ich aber durch eine Iteration über den ganzen Container umsetzen müssen, weil ich ja nicht nur gucken musste, ob ein Eintrag schon drin ist (was ja prinzipiell einfach mit "if ( (lliste.add(neueslemma)) == false)" ginge), sondern den dann auch verändern. Mit ner binären Suche wär das schneller gegangen, aber die hab ich fürs TreeSet nicht gefunden, also durch LinkedList ersetzt.

Bei der LinkedList führe ich einmal eine binäre Suche durch und kriege dann entweder den Index des zu ändernden Eintrags oder die Stelle, an der ein neuer Eintrag hin muss. Da das Ganze für jeden einzelnen Eintrag Zeit spart, ist das Programm insgesamt jetzt deutlich schneller.

 

[Marco13]

Hm. Klingt seltsam. Du hast also sowas wie

Entry neuerEintrag = zaubereNeuenEintrag();

Entry alterEintrag = treeSet.magicFunction(neuerEintrag); // Die Funktion gibt es nicht
if (alterEintrag == null) treeSet.add(neuerEintrag);
else alterEintrag.setzeWerteVon(neuerEintrag);

Das sieht von der Modellierung her erstmal seltsam aus: Nach welchen Kriterien werden die Einträge verglichen? Wenn zwei Einträge an die selbe Stelle im TreeSet gelegt werden würden, dann sollten sie auch gleich sein, d.h. man sollte den alten Eintrag gar nicht mehr benötigen... Wenn du genauer beschreiben würdest, das da gemacht wird, könnte man vielleicht eine Lösung finden. Kann gut sein, dass eine TreeMap für die Aufgabe besser geeignet wäre. Als ... erstmal auch "seltsam" aussehenden Workaround (der aber vielleicht vom Prinzip her das Problem lösen könnte) würde vielleicht sowas in Frage kommen:

TreeMap<Entry, Entry> treeMap = ... // Mappt jeden Eintrag auf sich selbst

Entry neuerEintrag = zaubereNeuenEintrag();

Entry alterEintrag = treeMap.put(neuerEintrag, neuerEintrag);  // Die Funktion gibt es!
if (alterEintrag != null)
{
    alterEintrag.setzeWerteVon(neuerEintrag);
    treeMap.put(alterEintrag, alterEintrag);
}

Aber das sieht eher nach etwas aus, was man "weiter unten" anpacken sollte - d.h. man sollte wohl eher die Eintrag-Klasse und deren Sortier- und Gleicheheits(!)-kriterium überdenken...