allgemein: Parser vorgehensweise.

[BrightAngel]

Hallo liebe DP Community!
Derzeit beschäftige ich mich mit einem Parser, der xml parsen soll.
(Ja, ich weiß, es gibt schon tausend und einen XML Parser , ich möchte nur selbst ans Werk, weil ich einfach grundlegend das Problem "parsen" intersannt finde.)

Jetzt zur Sache: Ich habe vor die Daten nur EINMAL im Speicher zu haben. D.h. ich nehme als Ausgangspunkt eine Stringvariable mit dem XML Inhalt.

Jetzt gehe ich den "Text" Zeichen für Zeichen durch. Ich habe eine spezielle Abwandlung von TList geschrieben, die mir nicht nur einen Pointer, sondern gleich einen ganzen Record zurückgibt.
Unter anderem sind da zwei (Index und Value) Pointer auf die Char Zeichen im Ausgangsstring drin, zwei Mal die Anzahl der zu lesenden Zeichen (Ja ich weiß, ist ein String zu Fuß ), die ID des Elternelements und der Typ(also: Knoten oder Attribut).
Wenn ich jetzt die Zeichen im String manipuliere, muss ich natürlich alle folgenden Pointer anpassen, da sich ja die Positionen verschieben. Beim verschieben muss ich aber auch den string-Teil weiter verschieben. Das braucht rechenzeit.

FRAGE: Was ist jetzt effizienter: Meine beschriebene Möglichkeit, beim durchparsen alles in einzelStrings Zerlegen (Brauch ich mehr Speicher)? Oder Objekte?
Oder was ganz Anderes (d.h. Bin ich auf dem Holzweg??? ) ???

Grüße
Brighty

[himitsu]

Viel Rechenzeit benötigt das Verschieben der nachfolgenden Nodes nicht unbedingt.

Wenn/Da du in den Nodes doch bestimmt auch die untergeordneten Nodes auflistest.
Den nachfolgenden/vorhergehenden Geschwisterknoten müßte man nicht unbedingt in jedem Knoten speichern, da diese ja auch im Elternknoten aufgelistet sind.
Also im Prinpip muß man einfach alle nachfolgenden Knoten durchgehn und überall nur einen Offset (die Verschiebung) aufrechnen.
Den String selber kann man ja komplett, für alle Knoten, auf einmal verschieben.


Aber ob du so weniger Speicher benötigst, das kommt darauf an, wie groß die XML-Datei ist und wie viel/oft etwas geändert wird.

Unter Umständen muß man ja alles umkopieren, selbst wenn man ganz am Ende nur eine Kleinigkeit einfügt.
Vorallem wenn nicht genug platz für diesen String ist.

Auch benötigst du einen "großen" zusammenhängenden Speicherplatz, wärend die Daten auch in kleineren Speicherlücken verteilt sein kann, wenn man nicht alles zusammenhängend hat.

Zitat:

(Brauch ich mehr Speicher)? Oder Objekte?

Wie gesagt, das kommt auf den Einzelfall drauf an
und ob du/wann du mehr Objekte benötigst, das kommt wohl erstmal grundlegend auf die Verwaltung deiner Daten an.

- viele XML-Libs haben z.B. für jedes Attribut ein eigenes Objekt
- in meiner Lib werden alle Attribute eines Knotens in nur einem Objekt verwaltet

[mimi]

Je nach dem wie groß deine XML Dateien werden, würde ich vielleicht sogar die Änderungen nur im Speicher machen und dem später speichern. Z.B. wenn der User auf Speichern klickt oder eine Automatisches Speichern alle 10 Änderungen oder alle 10 Minuten. Weiß du wie ich meine ? So wird auch die Festplatte geschont und vor allem die CPU.

Wird die XML Datei zu groß, gibt es natürlich ein Problem. Wobei ich auch nicht weiß, was zu Groß währe. 1 MB ? 10 MB ? 20 ? oder noch mehr ?
Hier würde es sich anbieten, mehrere Packte zu bilden. Du ließt z.b. die ersten 100 Einträge ein und dann die nächste, sobald der User, diese Sehen möchte. Auf diese Art und weise machen es einige Programme unter Linux. Z.B. um PDF Dateien anzuschauen.

[BrightAngel]

Erstmal danke für die Antworten!
@himitsu:

Zitat:

Auch benötigst du einen "großen" zusammenhängenden Speicherplatz, wärend die Daten auch in kleineren Speicherlücken verteilt sein kann, wenn man nicht alles zusammenhängend hat.

Genau da hängts bei mir :
1. wenn ich kompakte nullterminierte strings nehme und die beim ändern vergrößere, dann passen sie irgendwann nicht mehr an die stelle im RAM und werden verschoben (ans Ende). Der alte platz wird zwar frei, kann aber nur von gleich großen oder kleineren einheiten gefüllt werden.
Verbrauch der Rechenzeit recht gering, da nur wenige Pointer und daten verschoben/angepasst werden müssen.
Sehe ich das Richtig????
2. wenn ich gleich große bauklötze nehme, verschenke ich dazwischen platz, kann aber vergrößern (aber auch nur bis zu einem Maximum[ich bin gebunden]). Gerade große Bäume würden da probleme machen, da ein großer Rest evtl. verschoben werden muss. Wenigster Rechenaufwand, größter Speicherverbrauch oder? <- fällt für mich dann weg.
3. wenn ich einen langen string benutze, muss ich viele Pointer ändern (danke!: Offset), aber immernoch weniger, als wenn ich alles neuparsen würde.

Was von den dreien ist jetzt die beste Lösung? also wenn man nicht weiß wie groß die files sind.

Also im Prinzip: Wie aufwändig ist das Verschieben von sagen wir utopischen 100MB (dazu kommt es NICHT!!! ) im Speicher?
Wird da jede einzelne Zelle neu beschrieben oder werden da einfach die Klötze angepasst?
Ist dieser Aufwand jetzt weniger rechenintensiv als die gleiche Menge an Daten zu verwalten (Lösung 1 (da muss ja verglichen werden ob der Speicherblock in die Lücke passt))

Ich weiß vom Anpassen der TList, dass die Anwendungen gerne Speicherblöcke von 64kb (weitere Blockgrößen) anfordern.


@mimi: Wie lese ich einen Baum TEILWEISE ein? Woher weiß ich denn vorher, ob ein Tag gerade an Stelle X geöffnet ist???

Ich weiß, viele Fragen und Unsicherheit...Großes DANKE schonmal für eure Mühe, ich weiß, bin schwieriger Patient...

Gruß, Brighty

[himitsu]

Eine gewisse Defragmentierung im Speicher hast du eigentlich immer.

beim dem Speicher:
wenn du nun die XMLDaten alle in einem String hast, brauchst du auch einen "sehr" großen "freien" Speicherbereich im "RAM" dafür, wo dieser String reinpaßt.
Wenn der String nun vergrößert werden muß und das nicht mehr an Ort und Stelle geht, dann brauchst du einen neuen und größeren Speicherblock.
Der alte Speicherblock ist zwar jetzt frei, aber auch zu klein und kann nicht mehr verwendet werden, wenn der String weiterwächst ... wenn der String also oft vergrößert und verschoben wird, hast du zwar immernoch massig Speicher frei, aber irgendwann kann es passieren, daß kein Block mehr vorhanden ist, welcher groß genug ist.

Wenn man alles getrennt hat, dann benötigt man zwar mehr Speicher, kann aber dafür auch viele "kleine" Lücken ausnutzen.

Im Endeffekt kommt es auf den Einzelfall an und grob kann man wohl sagen
- ein zusammenhängender Speicher belegt weniger speicher, aber effektiv könnte es dennoch mehr belegen, inkl. dem unnutzbaren und zukleinen Blöcken
- getrennt kann man besser verteilen und auch schneller ändern, da man nicht immer alles in einem großen Speicher umkopieren muß

praktisch :
- viele Änderungen = getrennt
- wenig/keine Änderungen = zusammenhängend

Zitat:

Wie aufwändig ist das Verschieben

- einmal alles zusammen mit Move/MoveMemory verschieben, also ab der Stelle wo was verändert wird
- wenn man Pech hat und die Größe des Strings nicht an Ort und Stelle verändern kann, dann muß auch noch der ganze String umkopiert werden
- und nun muß man nur noch die Start-Indize der Knoten verschieben (einfache Integeraddition), wessen Daten umkopiert/verschoben wurden.

[mimi]

Zitat:

@mimi: Wie lese ich einen Baum TEILWEISE ein? Woher weiß ich denn vorher, ob ein Tag gerade an Stelle X geöffnet ist??? Question

Z.B. wenn du nur eine bestimmte Anzahl von Tags einliest. Z.B. nur 10 Root-Tags. je nach dem wie viele es gibt.

Zu deinem Problem: Ich habe schon seit längeren eine Idee, wie ich eine eigene DB erstellen könnte. Das passt ganz gut hierein denke ich:
Es gibt Bereiche die eine Feste Größe haben. Je nach Datentyp. Nur bei Datentypen, die eine Dynamische Größe haben, wird es Problematisch. Es gibt eine Tabelle gleich am Anfang. Beispielweise ist die 500 Byte groß. Davor wird gespeichert wo es in der Tabelle weiter geht und nach der Tabelle wird gespeichert, wo die Tabelle weiter geführt wird.

Datentypen, die jetzt eine Dynamische Größe haben, könnten jetzt, am Ende Eingefügt werden. Sagen wir dieser Block ist 1000 Byte groß. Die Brauchen dann zwar mehr Speicherplatzt, den sie vielleicht nie brauche, aber dafür kannst du diese Datenstätze schnell ändern.

Gelöscht wird z.b. gar nicht, sondern es wird nur der Platz frei geben. Die Idee Basiert darauf, Blöcke zu bilden, die eine bestimmte Größe haben.

Vielleicht klappt das auch so im RAM. Ist ein Block zuende, wird der nächste Angefangen. Da die Blöcke Kompatibel zu einander sein müssen / sollten, muss immer die Position wo der Nächste Block ist, abgespeichert werden am ende des Blocks.

Umgesetzt habe ich diese Idee noch nicht, da es noch einige ungeklärte Fragen gibt. Z.B. die DB wächst, also wachsen die Positions Angaben mit. Wenn ich jetzt aber vor dem Block nur 100 Byte belege, und ich aber 200 brauche, wird es zu Problem kommen. Ich hoffe ihr wisst was ich meine.

Ich glaube auch, so oder so ähnlich machen das auch die meisten DB'S die es inzwischen gibt.

[BrightAngel]

Danke für die Antworten! Habt mit sehr geholfen. Ich glaube ich werde jetzt geteilte Strings verwenden. Danke für die MOVE funktion.
In der Hilfe ist in der gleichen Gruppe auch die Heap-steuer-funktionen zu finden. Macht es Sinn die Daten auf dieser Ebene zu verwalten???
Ich habe mal irgendwo gelesen, dass Delphi einen Speichermanager besitzt (TMemoryManager )???
Regelt der schon intelligent das anordnen der Datenteile
(also: passt der Block dahin, wenn ja schreib ihn da rein)?
Bzw. Greifen die funktionen AllocMem u.ä. auf diesen intelligenten (ist er das??) Manager zurück oder muss ich mir da auch noch ne Klasse schreiben, um möglichst platzsparend zu arbeiten???

Werde mich dann mal dransetzen. Darf ich euch dann nochmal am Ende nach eurer Meinung fragen (himitsu, mimi, weitere?)?

Danke für eure Unterstützung!

P.S. @mimi: Deine Idee mit der Datenbank gefällt mir. Wenn du willst, wollen wir uns gemeinsam dranwagen? Ich hab da auch schonmal drüber nachgedacht. Theoretisch muss die "Indextabelle" am Anfang des Files stehen, jedoch die selbe Standartblockgröße haben, wie die Datenblöcke die folgen, oder? Aber ich glaube wir sollten das Thema entweder in nem neuen Thread beginnen oder per PM???

[mimi]

Zitat:

n? Ich hab da auch schonmal drüber nachgedacht. Theoretisch muss die "Indextabelle" am Anfang des Files stehen, jedoch die selbe Standartblockgröße haben, wie die Datenblöcke die folgen, oder?

Nicht unbedingt. Die Blöcke jeder Tabelle können unterschiedlich groß sein. Im Prinzip könnte jeder Block in einer Tabelle eine andere Größe aufweisen. Beim Suchen muss so oder so, von Anfang an durch gesucht werden.

Zitat:

Aber ich glaube wir sollten das Thema entweder in nem neuen Thread beginnen oder per PM???

JA ! Vielleicht sogar in einem Extra Thread dazu. Vielleicht gibt es ja noch mehr Personen, die dazu was sagen können. Ich habe schon zwei mal versucht diese Idee umzusetzen. Im Prinzip dürfte es bis auf einige Probleme, relativ einfach sein.

Meint ihr so oder so ähnlich machen das auch die "Großen" Datenbanken wie SQL ? oder vielleicht sogar das Dateitsystem ?
Das Problem ist ja immer das Löschen oder Hinzufügen. Bei kleineren Datenmengen könnte, die Datei jedes mal neu erstellt werden aber bei 1 TB nicht mehr...

Edit01: Alles was mit meiner Idee zu tun hat, bitte hier rein: http://www.delphipraxis.net/internal...127271#1127271
Dort können wir die Idee weiter verfolgen.