Announcement: there is an English version of this forum on Der Browser DOM ist ja eine Baumstruktur. Es gibt Nodes, normalerweise Text Nodes oder Element Nodes. Jedes Element hat Attribute mit Werten und kann weitere Nodes beinhalten. Bei jedem Element ist die Anzahl enthaltener Nodes bekannt, und man kann auf das n-te Unterelement direkt zugreifen. Man kann auch auf das Parent Element, das nächste, sowie das vorherige Element zugreifen. Also eigentlich in alle Richtungen wie man lustig ist. Zudem kann man Elemente einfügen, entfernen, usw. Nun interessiert mich, wie setzt man das am besten um, und wie machen es die Browser? Wie wichtig ist es effektiv, Speicherplatz zu Sparen, und wie bringt man das damit unter einen Hut schnell und einfach Elemente einzufügen und zu entfernen? Und wie würdet ihr das machen? Für die Elementnamen und Attributnamen würde ich String Interning verwenden. Die Strings in ein grosses Set, und in der Baum Struktur für den selben String dann den selben Pointer nehmen. Kleine Strings die in den Pointer passen kann man Stattdessen aber auch gleich dort ablegen. Aber was mach ich beim Baum selbst? Wenn ich linked lists Verwende, geht das einfügen und entfernen schnell, aber direkter Zugriff auf das n-te Unterelement hat man damit nicht (und die Pointer brauchen Speicherplatz). Bei einem Array kann man dafür nicht einfach so ein Element in der Mitte einfügen, da muss man dann alle nachfolgenden Kopieren. Und wie macht man das mit dem Ermitteln des übergeordneten Elements am besten? Einfach jedem Element einen Pointer verpassen? Sicher gibt es da heute bessere Möglichkeiten, als simple Arrays und Linked Lists, was ist heutzutage so State of the Art, um diese Art von Baumstruktur abzubilden?
:
Bearbeitet durch User
Oliver S. schrieb: > https://lists.isocpp.org/std-proposals/2021/02/2357.php > > Mal so als Einstieg, und Hinweis… Da scheint es eher um Suchbäume zu gehen, als um generische Baumstrukturen.
Daniel A. schrieb: > Nun interessiert mich, wie setzt man das am besten um, Wenn es schnell gehen soll: da der Inhalt aus Strings besteht, knallt man am besten die ganze (letztlich XML in UTF8) Datei in den Hauptspeicher oder mappt sie falls die Speicherverwaltung das hergibt. Das kostet genau 1 alloc und 1 Verwaltungsinformation. Dann parst man speicherintern den Baum und baut eine verlinkte Baumstruktur parallel dazu auf, das geht bei linear durchackern sehr einfach weil man immer weiss auf welcher Ebene man ist. Die Knoten sind alle gleich (Array), mit next und child-Verweisen platzsparend als Arrayindizes, und an Stelle von strings gibt es nur Offsets in das geladene/gemappte Dateiobjekt, daher sind alle Knoten gleich gross, sie haben keine längenvariablen Member So sind alle childs eine lineare Liste in der Reihenfolge in der sie in der Datei standen, zum Zugriff auf den String nutzt man eine Funktion die Escapements umsetzt. Das Suchen in dem Baum geht also langsam. Wer möchte fügt den Nodes nun noch B+ Baum Pointer hinzu und baut nach Namen sortierte Suchbäume in jeder Ebene auf. Einfügen/Löschen passiert in Folge durch umändern der Verweise im Tree, neue Knoten hinten ans Array. Wenn der Kram gespeichert werden soll traverst man durch den Baum und schreibt in der Reihenfolge raus. Praktisch alle XML Bibliotheken machen es anders, führen zu zigtausenden im Speicher allozierter Objekte mit jeweils ihrer Verwaltungsinformation was locker doppelt bis vierfach so viel Speicher kostet. Das macht es drastisch langsamer beim laden, aber schneller beim lookup.
Daniel A. schrieb: > Und wie würdet ihr das machen? Kommt darauf an was man mit dem Baum machen will. Brauche ich den ganzen Baum oder nur bestimmte Infos davon, einmalig, will ich den Baum ändern, danach speichern oder ....
Franko S. schrieb: > Kommt darauf an was man mit dem Baum machen will. Ich will etwas zwischen einem GUI Toolkit und Display Server machen. Im Grunde will ich es am Ende für das selbe verwenden, wie ein Browser. Eventuell baue ich später auch einen Browser darauf auf. Heutige Display Server wie z.B. wayland und X11 sind ja so aufgebaut, dass die Anwendung quasi direkt in die Fenster zeichnet, das wird meistens von GUI Toolkits wegabstrahiert, die auch teils einen UI Tree haben. Ich will in die andere Richtung gehen. Anwendung und Display Server halten einen UI Tree synchron, und der Display Server kümmert sich um das Rendering, statt das GUI Toolkit / die Anwendung. Die Anwendung soll gar nicht erst wissen, wie Grosse UI Elemente sind, oder wo die Platziert werden, etc. Die soll nur den UI Tree manipulieren. Ich will, dass das UI noch flüssig läuft, selbst wenn man sich vom Mars aus per Remote Desktop auf seinem Rechner einloggt. Michael B. schrieb: > Wenn es schnell gehen soll: da der Inhalt aus Strings besteht, knallt > man am besten die ganze (letztlich XML in UTF8) Datei in den > Hauptspeicher oder mappt sie falls die Speicherverwaltung das hergibt. Manchmal werde ich eine XML-Artige Datei als Ausgangspunkt haben, aber nicht immer. Ich hatte eigentlich vor, den UI Tree API getrennt vom Parser zu halten, so dass man zwar eine Datei parsen könnte, aber man auch einen eigenen Parser für eigene Dateiformate nutzen könnte, oder anhand anderer Kriterien den UI-Tree zusammen bauen kann. Halt so wie beim Browser, wo man eine HTML Datei laden kann, aber man kann auch mit doument.createElement() usw. den DOM selbst zusammenbauen. Michael B. schrieb: > Das kostet genau 1 alloc und 1 Verwaltungsinformation. Einzelne Allokationen kann ich eventuell trotzdem gering halten. Bei dynamischen Array Implementationen, wo man vorher nicht weiss, wie viele Elemente da rein kommen, gibt es die Speicher Verdopplungstechnik. Wenn der Speicher nicht reicht, verdoppelt man ihn. Damit wird immer <50% Speicher verschwendet, und gleichzeitig gibt es nur sehr wenige (re)allokationen. Michael B. schrieb: > mit next und child-Verweisen platzsparend als > Arrayindizes, und an Stelle von strings gibt es nur Offsets in das > geladene/gemappte Dateiobjekt, daher sind alle Knoten gleich gross, sie > haben keine längenvariablen Member Neben den Child Nodes gibt es doch auch noch die Liste der Attribute, die hat doch auch eine variable Grösse? Und bei dem ganzen hab ich doch immer noch das Problem, dass ich beim Einfügen eines Elements wo anders als am Ende die restlichen Elemente kopieren müsste, das wäre sicher nicht sonderlich effizient.
Daniel A. schrieb: > Und bei dem ganzen hab ich doch immer noch das Problem, dass ich beim > Einfügen eines Elements wo anders als am Ende die restlichen Elemente > kopieren müsste Nein. Die Reihenfolge ist verpointert, du hast bei jedem Element den Arrayindex des nächsten, der kann also auch woanders als direkt dahinter stehen. Nur löschen passiert durch wegname der darauf verweisenden Pointer(Indizes), nicht physikalischem entfernen (man konnte den Platz aber in eine free list stecken). Daniel A. schrieb: > Anwendung und Display Server halten einen UI Tree synchron So so, und wo ist der gespeichert ? Verändernde Zugriffe darauf können zu stark unterschiedlichem Rendering führen, eventuell gar nicht beabsichtigt weil gleich danach noch eine Änderung wieder alles gerade rückt.
Michael B. schrieb: > Nein. Die Reihenfolge ist verpointert, du hast bei jedem Element den > Arrayindex des nächsten, der kann also auch woanders als direkt dahinter > stehen. Ok, aber dann kann ich nicht mehr direkt auf das n-te Element Zugreifen. Aber vielleicht ist das am Ende ja halb so wild, wie oft macht man das in der Praxis schon. Michael B. schrieb: > Daniel A. schrieb: >> Anwendung und Display Server halten einen UI Tree synchron > > So so, und wo ist der gespeichert ? Einmal bei der Anwendung, das ist die Autoritative Version, und einmal beim Display Server, der das dann rendert. Michael B. schrieb: > Verändernde Zugriffe darauf können zu stark unterschiedlichem Rendering > führen, eventuell gar nicht beabsichtigt weil gleich danach noch eine > Änderung wieder alles gerade rückt. Dann muss ich halt Transaktionen oder so einbauen.
:
Bearbeitet durch User
Daniel A. schrieb: > Einmal bei der Anwendung, das ist die Autoritative Version, und einmal > beim Display Server, der das dann rendert. DOPPELT ? Irre.
Michael B. schrieb: > DOPPELT ? Ja, auf dem Display Server brauch ich es, um es rendern zu können. Und bei der Anwendung brauch ich es, falls die Verbindung mal abreissen sollte, sonnst verliert die Anwendung ihr ganzes UI. Eigentlich könnte ich auch mehrere Display Server haben, dann hätte ich noch mehr Kopien davon. (Anwendung und Display Server sollen auf unterschiedlichen PCs sein können).
Daniel A. schrieb: > Der Browser DOM ist ja eine Baumstruktur. > Es gibt Nodes, normalerweise Text Nodes oder Element Nodes. Jedes > Element hat Attribute mit Werten und kann weitere Nodes beinhalten. Bei > jedem Element ist die Anzahl enthaltener Nodes bekannt, und man kann auf > das n-te Unterelement direkt zugreifen. Man kann auch auf das Parent > Element, das nächste, sowie das vorherige Element zugreifen. > Also eigentlich in alle Richtungen wie man lustig ist. > Zudem kann man Elemente einfügen, entfernen, usw. > > Nun interessiert mich, wie setzt man das am besten um, und wie machen es > die Browser? Was Du oben als Anforderung beschrieben hast, wird von einem klassischen Dateisystem geleistet. Du kannst Dir zur Verdeutlichung die tumben FAT-artigen Dateisystemen angucken, aber eben auch NTFS oder ext4. > Wie wichtig ist es effektiv, Speicherplatz zu Sparen, Speicherplatz ist halt immer relativ knapp im Vergleich zu langsameren Speichermedien (HDD, SDD) und wird in einer virtuellen Speicherverwaltung eben auch mal ausgelagert. > und wie bringt man > das damit unter einen Hut schnell und einfach Elemente einzufügen und zu > entfernen? > Und wie würdet ihr das machen? > > Für die Elementnamen und Attributnamen würde ich String Interning > verwenden. Die Strings in ein grosses Set, und in der Baum Struktur für > den selben String dann den selben Pointer nehmen. > Kleine Strings die in den Pointer passen kann man Stattdessen aber auch > gleich dort ablegen. > > Aber was mach ich beim Baum selbst? Wenn ich linked lists Verwende, geht > das einfügen und entfernen schnell, aber direkter Zugriff auf das n-te > Unterelement hat man damit nicht (und die Pointer brauchen > Speicherplatz). Bei einem Array kann man dafür nicht einfach so ein > Element in der Mitte einfügen, da muss man dann alle nachfolgenden > Kopieren. Arrays, die in Form eines zusammenhängenden Speicherblocks realisiert worden sind, und die damit dem Vorteil des Direktzugriffs [in der Informatik heißt es dann Zugriff in O(1) ] bieten, sind zur Verwaltung von dynamischen Arrays ungeeignet. Zwischenbemerkung Die sogenannte O-Notation wie von mir gerade verwendet, ist ein Schlüsselkonzept zum Verständnis der Laufzeit von Algorithmen, das müsstest Du Dir mal ansehen. Sinnvoll ist es, Arrays auch als Baum zu verwalten. Du verlierst dann zwar die Direktzugriffsfähigkeit, ein Zugriff auf ein Element der m Töchter eines Blatts kannst Du aber in O(log(m)) realisieren. > > Und wie macht man das mit dem Ermitteln des übergeordneten Elements am > besten? Einfach jedem Element einen Pointer verpassen? Ja. Das ist dann das Attribut "Vater/Mutter". Zeigt dieses Attribut auf das eigene Element, handelt es sich um die Wurzel. Auf diese Art und Weise kannst Du die gesamte Baumstruktur mit einem Typ verwalten. Die jeweiligen Inhalte, die die "Nutzlast" enthalten, kannst Du mit einem Attribut, das auf ein Nutzlast-Element zeigt, versuchen abzubilden. Den dynamisch lange Namen eines Elementes kannst Du auch "nutzlastartig" verwalten. Ein Hash Deines Namens mit konstanter Länge im Baumelement würde Dir aber das Leben leichter machen, wenn der Name das Sortierkriterium der Söhne/Töchter eines Elements sein soll. > > Sicher gibt es da heute bessere Möglichkeiten, als simple Arrays und > Linked Lists, was ist heutzutage so State of the Art, um diese Art von > Baumstruktur abzubilden? Bei modernen Dateisystemen sind B+-Bäume en vogue. Abhängig von den spezifischen Anforderungen Deines Projekts und der typischen Ausprägung Deiner Bäume (wachsen die z.B. sehr in die Breite, als hat ein Element sehr viele Töchter?) können andere Strukturen attraktiver sein.
Daniel A. schrieb: > Also eigentlich in alle Richtungen wie man lustig ist. > Zudem kann man Elemente einfügen, entfernen, usw. > > Nun interessiert mich, wie setzt man das am besten um Eine Struktur, die diese Vielfalt an Navigations- und Manipulationsmöglichkeiten alle effizient abbildet wirds nicht geben, allerdings wirst Du auch so gut wie nie alle diese Möglichkeiten hinreichend oft brauchen, daß sich darauf zu optimieren auch nur ansatzweise auszahlt. Daniel A. schrieb: > einen UI Tree Hmm... mit wievielen Elementen in so 'nem UI-Tree rechnest Du denn, um selbst ein 4K-Display so mit UI-Elementen zumüllen zu können, daß Du Dein UI nicht mehr bedienen willst? ;) 1000 oder meinetwegen 10000? Sollte eigentlich auf aktuellen Rechnern selbst als single-linked-list noch ausreichend schnell bleiben, denk ich mal. ;) Ich denke am öftesten wirst Du wohl den UI-Tree zwecks Rendering traversieren müssen oder den Baum aus einem persistenten Format (z.B. XML-Datei) aufbauen müssen. Daniel A. schrieb: > Ich will, dass das UI noch flüssig läuft, selbst wenn man > sich vom Mars aus per Remote Desktop auf seinem Rechner einloggt. Okay, dann vergiss schleunigst alles über Algorithmen, Datenstrukturen und Programmierung und tauche in die wunderbare Welt der (theoretischen) Physik ein; Du wirst nämlich erstmal Subraum-Kommunikation erfinden müssen. ;)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.