Baumdesign (Split aus Nullpointerthread)



  • SeppJ schrieb:

    Entweder braucht es das Nullsetzen (zum Beispiel Blätter von Baumstrukturen)

    Das wäre dan aber eher ein unique_ptr.reset().


  • Mod

    blattfresser schrieb:

    SeppJ schrieb:

    Entweder braucht es das Nullsetzen (zum Beispiel Blätter von Baumstrukturen)

    Das wäre dan aber eher ein unique_ptr.reset().

    Nee, ich programmiere keine Bäume mit unique_ptr. Der unique_ptr drückt ein Besitzverhältnis aus, das nicht da ist. Und was für ein Smartpointertyp wäre dann der Zeiger vom Blatt auf seinen Vorgänger?

    edit: Und bitte wieder zum Thema. Das Design von Datenstrukturen kannst du in einem anderen Thread diskutieren, wenn du das für nötig hältst.



  • SeppJ schrieb:

    Und was für ein Smartpointertyp wäre dann der Zeiger vom Blatt auf seinen Vorgänger?

    Du scheinst andere Bäume als ich zu programmieren. Einen Pointer auf den Vorgänger habe ich noch nie benötigt. Aber das wäre dann ein roher Pointer.



  • edit: hier stand bullshit


  • Mod

    blattfresser schrieb:

    SeppJ schrieb:

    Und was für ein Smartpointertyp wäre dann der Zeiger vom Blatt auf seinen Vorgänger?

    Du scheinst andere Bäume als ich zu programmieren.

    Komische Bäume programmierst du. Ganz schön umständlich, wenn man kein nächstes Element zu einem Blatt finden kann, oder? Und sicherlich auch sehr langsam, ohne jegliche Möglichkeit, die Tiefe der Äste auszugleichen.



  • SeppJ schrieb:

    Komische Bäume programmierst du. Ganz schön umständlich, wenn man kein nächstes Element zu einem Blatt finden kann, oder? Und sicherlich auch sehr langsam, ohne jegliche Möglichkeit, die Tiefe der Äste auszugleichen.

    Ich laufe immer von der Root nach unten, dann kann ich mir den Weg doch merken.

    Gibt nur wenige Ausnahmen, wo das nicht so einfach geht. Red-Black-Trees zum Beispiel, aber selbst da gibt es welche, die kommen ohne den Parent-Pointer aus (LLRB).



  • Ich mag den Parentpointer auch (bzw. nutze ich lieber Indizes, ich will das meist auch serialisieren). Sagen wir, ein Benutzer macht ne Auswahl aus einem Baum, übergibt das irgendeinem und dieser irgendjemand möchte etwas über die Eltern erfahren oder eben Nachbarn kennenlernen.

    Da braucht man nur das Node selbst, klettert hoch und bei den Nachbarn wieder runter und gut ist. Ansonsten muss "irgendjemand" wieder komplett runterklettern. Unterschied zu Deinem, blattfresser, Szenario ist einfach, dass man gerne auch Mal außerhalb einer Iteration auf ein Blatt referenziert und dann Eltern-Infos erhalten möchte. Passiert bei mir produktiv ständig.


  • Mod

    blattfresser schrieb:

    SeppJ schrieb:

    Komische Bäume programmierst du. Ganz schön umständlich, wenn man kein nächstes Element zu einem Blatt finden kann, oder? Und sicherlich auch sehr langsam, ohne jegliche Möglichkeit, die Tiefe der Äste auszugleichen.

    Ich laufe immer von der Root nach unten, dann kann ich mir den Weg doch merken.

    Und das kommt dir nicht irgendwie unnötig umständlich vor? Beispielsweise wenn du einen Iterator brauchst? Schleppt der in sich Information über den gesamten Baum mit sich? Und wenn ich etwas einfüge oder lösche wird der Iterator also ungültig?

    Ich sag ja nicht, dass man keine Bäume ohne parent-Zeiger programmieren kann, ich sage aber, dass die Nachteile den geringen Mehraufwand des einen Pointer pro Element in praktisch allen Szenarien mehr als aufwiegen. edit: Ich bin mal gespannt, welche Ausnahmeszenario du konstruierst, bei dem der Parentpointer Nachteile hat. 🙂



  • Mal Butter bei die Fische mit konkreten Beipielen: Quadtree. Da gehe ich von Objekten aus. Die meisten befinden sich in Blattknoten. Um sie zu verschieben, wandere ich nach oben und dann wieder nach unten. Es ware nicht gut, alle Blattknoten abzuwandern um an die Objekte zu kommen, denn die meisten Blattknoten sind leer.

    Ich laufe immer von der Root nach unten, dann kann ich mir den Weg doch merken.

    Nun, wie du siehst, ist es anwendungsspezifisch.



  • knivil schrieb:

    Mal Butter bei die Fische mit konkreten Beipielen: Quadtree. Da gehe ich von Objekten aus. Die meisten befinden sich in Blattknoten. Um sie zu verschieben, wandere ich nach oben und dann wieder nach unten. Es ware nicht gut, alle Blattknoten abzuwandern um an die Objekte zu kommen, denn die meisten Blattknoten sind leer.

    Mein noch konkreteres Beispiel: Physiksimulation/Game mit verschiedenen Objekten im Quadtree. Alle bewegen sich gleichzeitig.

    Also rekursiv den Quadtree besuchen, Weg merken. Objekt gefunden: Hochmarschieren soweit nötig (den Weg hab ich mir gemerkt), dann wieder runter (das steht im Knoten).



  • Und dann musst Du dir beim Durchlauf des Algos etwas merken anstatt das bei Initialisierung zu tun. Du sparst vielleicht für außerhalb des Algos Speicher, aber ob das kritisch ist? Ich bezweifle das Mal sehr stark.



  • Eisflamme schrieb:

    Und dann musst Du dir beim Durchlauf des Algos etwas merken anstatt das bei Initialisierung zu tun. Du sparst vielleicht für außerhalb des Algos Speicher, aber ob das kritisch ist? Ich bezweifle das Mal sehr stark.

    Ich spare mir selbst im Algo Speicher O(log n) Overhead statt O(n).
    Wenig kompakter Speicher ist beim Quadtree das, was letztendlich die Geschwindigkeit ausmacht.



  • Das verstehe ich nicht. In deinem Fall merkst Du Dir etwas, um irgendwo hinzuwandern. Im Merkfall hat man es sich schon gemerkt und wandert darüber. Wo Du jetzt Performance gewinnst - v.a. sogar O(n - log n) - bleibt mir verschlossen.



  • Wenig kompakter Speicher ist beim Quadtree das, was letztendlich die Geschwindigkeit ausmacht.

    Das kann ich nicht bestaetigen. Zumal man bei Kollisionserkennung alle Objekte einer Node haben moechte und eben die Objekte aus darueberliegeneden Knoten. Somit ist es natuerlich, schnell an den Blattknoten des Objektes zu kommen und an alle drueberliegenden Knoten. Ein Quadtree ist eine Hilfsdatenstruktur, im Zentrum stehen die Objekte, d.h. die Arbeit mit Objekten wird optimiert. Alle Blattknoten zu besuchen, um mit den Objekten zu arbeiten, ist nicht optimal oder natuerlich. Der Overhead eines weiteren Pointers liegt bei etwa 16%

    node
    {
        node* parent;
        objects* objs;
        number obj_count;
        node* quadrants[4];
    }
    

    Also rekursiv den Quadtree besuchen

    Warum, wenn das Objekt weiss wo es ist? Auch skaliert dein Algorithmus mit der Anzahl der Knoten und Objekten, meiner mit der Anzahl der Objekte. Selbstverstaendlich ist der Speicherverbrauch eines Knotens bei tiefen Quadtrees abzuwaegen, aber Speicher ist billiger als Rechenleistung.



  • SeppJ schrieb:

    Nee, ich programmiere keine Bäume mit unique_ptr. Der unique_ptr drückt ein Besitzverhältnis aus, das nicht da ist. Und was für ein Smartpointertyp wäre dann der Zeiger vom Blatt auf seinen Vorgänger?

    Also fuer mich besitzt ein parent seine child-Knoten. Einen rohen Zeiger als parent zu verwenden ist auch ganz natuerlich: Der Parent lebt *immer* laenger als der Child.

    Koenntest du das mal ein wenig erleutern?


  • Mod

    Kellerautomat schrieb:

    Koenntest du das mal ein wenig erleutern?

    Klar:

    Einen rohen Zeiger als parent zu verwenden ist auch ganz natuerlich: Der Parent lebt *immer* laenger als der Child.

    Nein? In welcher Art Baum soll das denn der Fall sein? Hast du noch nie ein Element gelöscht? Noch nie umgeordnet? Wo ist denn da das Besitzverhältnis? Die Parent-Child Beziehung ist beliebig austauschbar und wird auch oft verändert. Ist das jedes Mal ein Besitzwechsel? Schlimmer noch: Wenn das Parent gelöscht wird, sollen in der Regel die Kinder gar nicht gelöscht werden, sondern werden woanders wieder eingebaut. Also das genaue Gegenteil von dem, was ein Besitzverhältnis aussagt!



  • knivil schrieb:

    Wenig kompakter Speicher ist beim Quadtree das, was letztendlich die Geschwindigkeit ausmacht.

    Das kann ich nicht bestaetigen. Zumal man bei Kollisionserkennung alle Objekte einer Node haben moechte und eben die Objekte aus darueberliegeneden Knoten. Somit ist es natuerlich, schnell an den Blattknoten des Objektes zu kommen und an alle drueberliegenden Knoten.

    Kannst du mir mal dein Quadtree-Design erklären (oder einen Link geben), ich verstehe nicht ganz, wie du das machst. Vielleicht ist mein Ansatz doch nicht so gut.

    Ich habe ein

    struct node {
      int next; // die vier Unterknoten sind nodes[next], nodes[next+1], ... nodes[next+3]
    
      object* objects;
      number obj_count;
    };
    std::vector<node> nodes; // Einmalig 1GB virtual Memory reservieren, dadurch keine Allokation nötig
    

    Bei jedem Frame wird der gesamte Quadtree neu aufgebaut und das Objekt überall da eingefügt, wo es draufliegt (das zuständige Quadrat ist aus dem Kontext klar, du musst das eigentlich auch in der Node speichern).
    Die Kollisionserkennung passiert beim Einfügen der Objekte. Ich muss nur die Objekte testen, die in den Blättern vorkommen, in denen das Objekt eingefügt wird.

    Speicherst du nur das Zentrum vom Objekt ab oder alle Knoten, in denen es drauf liegt? Zweiteres ist nicht einfach zum updaten und erstes ist für Kollisionserkennung schwer.

    @knivil:

    Koenntest du das mal ein wenig erleutern?



  • knivil besitzt einen Audi R8 und einen Fiat Panda. SeppJ hat kein Auto und ist derzeit auf der Suche nach einem Sportwagen. Eisflamme faehrt einen VW Golf.

    Im Handschuhfach von knivils Audi befindet sich ein Buch, in dem alle bisherigen Besitzer aufgelistet sind. knivil verkauft den Wagen an SeppJ fuer 100k€ und schreibt ihn als neuen Besitzer im Buch ein. Da ihm jedoch die Erhaltungs- und Spritkosten zu hoch sind, verkauft er den Audi weiter an Eisflamme und traegt ihn als neuen Besitzer ein.

    Zu jeder Zeit hat ein Auto genau *einen* Besitzer. Der Besitzer ist aber nicht fuer die Lebenszeit des Autos der selbe. Ebenso faehrt keine der beteiligten Personen dasselbe Auto ihr Leben lang.



  • SeppJ schrieb:

    Ist das jedes Mal ein Besitzwechsel?

    Ja.

    R
        / \
       P
      / \
     A   B
    / \ / \
    
         R
        / \
       P
      / \
     A
    / \
       B
    
         R
        / \
       A
      / \
         B
    

    Wenn left und right jedesmal unique_ptr's sind, kannst du das mit swap und move so hinschreiben, dass P automatisch gelöscht wird, weil niemand mehr dafür verantwortlich ist. Sind genau die gleichen Operationen wie mit rohen Pointern, nur viel leichter Exception-sicher und ohne Speicherleck.



  • Ich finde, es kommt darauf an. Bäume können besitzend sein, wenn Elemente ohnehin nur dort vorkommen, sie können aber auch rein zeigend sein, dann strukturiert der Baum eben bereits vorhandene Elemente in einer möglichen Art und Weise. Das gestattet dieselben Objekte aber auch noch in anderen Datenstrukturen anzuordnen. Der Baum ist somit eine Art Zugriffsstruktur.

    In meinem Projekt handhabe ich das mit letzterem, also dem, was SeppJ empfiehlt, weil die baumartige Anordnung nur eine Ausprägung der möglichen Strukturierungen ist.

    Wenn man aber die Zeiger auch im Baum mit new und delete anlegen möchte... habe das mal durchdacht, eigentlich hat man durch unique_ptr nicht wirklich mehr Overhead. Es wirkte für mich nur zunächst unintuitiv beim Ziel-Parentnode einen leeren Child anzulegen, in den man dann den Quell-unique_ptr moved. Dann wiederum passiert dasselbe, wenn man klassisch new/delete verwendet. Also finde ich das eigentlich ganz okay.


Log in to reply