Atree: Eine einfache und effiziente pointerlose Tree-Implementierung

• Apter Trees in C++
• Ein Tree, der mit nur zwei Vektoren – Knotenwerten und Elternindizes – einfach dargestellt wird
• Die meisten Trees werden wie Binärbäume implementiert, wobei jeder Knoten seinen Wert und Pointer auf seine linken/rechten Kindknoten enthält
• Solche Datenstrukturen müssen rekursiv implementiert werden und können wegen Cache-Verhalten und häufigem malloc() langsam sein
• Das Konzept, wer einen Tree-Knoten „besitzt“, kann in mehrschichtiger Software kompliziert werden
• Apter Trees sind deutlich schneller, leichter nachzuvollziehen und einfacher zu implementieren

Funktionsweise

• Implementiert mit zwei Arrays gleicher Größe
  • Vektor (Array) der Daten d
  • Vektor p der Elternindizes. Der Index im Vektor d wird als Schlüssel verwendet (c)
  • Oft ist der Schlüssel/Index c ein Integer-Typ
• Wenn Coco der Elternknoten von Molly und Arca ist und Arca ein Kind namens Cricket hat, ergibt sich folgende Struktur
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• Ein Knoten mit Elternwert 0 und Schlüssel 0 ist der Root-Knoten (bei Apter Trees ist ein Root-Knoten entweder Pflicht oder -1 bedeutet „kein Elternknoten“, wird hier aber ignoriert)
• Computer können Vektoren sehr schnell verarbeiten. Da das viel schneller ist als Pointer-Operationen, ist ein Vergleich der Big-O-Notation von Algorithmen in der Praxis kaum sinnvoll

Warum das wichtig ist

• Diese Implementierungsweise ist die eleganteste Tree-Implementierung, die der Autor bisher gesehen hat
• Mit einer geeigneten Bibliothek für Vektoroperationen ist sie leicht zu verstehen und Bugs sind leichter zu finden
• Durch ihre Einfachheit lässt sie sich leicht auf andere Einsatzszenarien anwenden
• Man kann den Vektor der Elternindizes ignorieren und schnell über die Werte iterieren; das ist wie ein kostenlos nutzbares Deep Map
• GPU-freundlich und leicht in Embedded-Umgebungen einsetzbar
• Sicherheit lässt sich leicht aufrechterhalten, indem verhindert wird, dass die Vektoren über eine bestimmte Größe hinaus wachsen

Herkunft

• Es wird versucht herauszufinden, wer diese Technik erfunden hat; vermutet wird, dass sie in der vektororientierten Ära der 60er- und 70er-Jahre bereits einen Namen hatte
• Die erste vollständige Beschreibung wurde so, wie Apter sie erklärt hat, gesehen, sie ist aber auch in K3 gut dokumentiert
• APL implementiert Trees auf traditionelle Weise, verwendet aber ähnliche Techniken für Vektorgrafen
• Auch J-Nutzern ist das bekannt; auf Rosetta Code gibt es eine Beschreibung einer Tree-Implementierung in J
• John Earnest erklärt Vektor-Tree-Implementierungen ausführlicher und beschreibt dabei auch Löschvorgänge, einschließlich eines Ansatzes mit „Offset-Indizes“
• Ein komplexerer Ansatz besteht darin, die Tiefe jedes Eintrags zu verfolgen

Andere gängige Tree-Implementierungen

• Es gibt unter anderem die Kernel-Tree-Implementierung von FreeBSD, Trees in klib, die Tree-Klasse von Ruby und deklarative Tree-Klassen in Python
• Diese leisten nicht dasselbe wie Apter Trees, und einige sind durch ihre Generalisierung deutlich umfangreicher

Stand dieses Codes

• Dies ist ein Versuch, das beim Lernen von C++17 umzusetzen
• Es ist noch nicht einsatzbereit, und es muss noch mehr über C++ gelernt werden

Meinung von GN⁺

• Apter Trees vereinfachen bestehende komplexe Tree-Strukturen und ermöglichen schnelle und effiziente Datenverwaltung
• Eine vektorbasierte Tree-Implementierung kann den Speicher-Overhead minimieren und die Leistung durch linearen Zugriff verbessern
• Der Artikel bietet eine interessante Perspektive auf innovative Ansätze für Datenstrukturen im Software Engineering

[GN⁺]

Hacker-News-Kommentare

• Ein Nutzer äußerte seine Überraschung darüber, seine eigene Arbeit auf Hacker News verlinkt zu sehen. Er interessierte sich sehr für leichtgewichtige arraybasierte Datenstrukturen und erwähnte insbesondere eine Implementierungsweise, die häufig für Knotentrees beim Skinning von 3D-Modellen verwendet wird. Wenn man das Array so sortiert, dass Elternknoten vor ihren Kindknoten stehen, kann die Neuberechnung der Welttransformationen für alle Knoten mit einer einfachen Schleife erledigt werden.
• Ein anderer Nutzer bemerkte zu dem Kommentar, dass das Iterieren über Kindknoten in diesem Tree-Stil O(N) sei, dass sich das atree-Design in der Praxis leicht verallgemeinern lasse, indem man Pointer auf das „erste Kind“ und das „nächste Geschwister“ ergänzt. Außerdem empfahl er, die Datenstruktur so zu verändern, dass sie die tatsächlich benötigten Operationen unterstützt.
• Ein Nutzer behauptete, dass das Speichern von Knoten in einem Array und die Verwendung von Indizes als Pointer für die Implementierung von Tree-Algorithmen essenziell sei. Insbesondere wenn auf die Kinder eines Knotens zugegriffen werden müsse, riet er dazu, zur Speicherersparnis separate Strukturen für innere Knoten und Blattknoten in Betracht zu ziehen.
• Ein weiterer Nutzer merkte an, dass es etwas seltsam sei, dass die Darstellung eines Trees über ein Eltern-Array auf Hacker News so viel Aufmerksamkeit bekomme. Das zeige, wie weit eine gute Präsentation eine grundlegende Idee tragen könne.
• Ein Nutzer wies darauf hin, dass dieses Projekt letztlich nur System-Pointer durch eigene Pointer ersetze.
• Ein anderer Nutzer schlug vor, bei dem Wunsch, mallocs zu reduzieren und die Datenlokalität zu verbessern, eine traditionelle Tree-Implementierung mit einem Node-Pool auszuprobieren.
• Es gibt einen Kommentar mit der Empfehlung, sich die Erklärung von Aaron Hsu mit APL anzusehen.
• Ein Nutzer schlug eine Strukturänderung vor, bei der alle Kinder eines Knotens zusammen gepackt werden. Dadurch könne man die vollständige Kindliste eines Knotens per binärer Suche finden, und die Struktur hätte cachefreundliche Eigenschaften.
• Es gibt einen Kommentar zur Bezeichnung von Indizes innerhalb eines Arrays als „Handles“ oder „Index-Handles“, außerdem wurde erwähnt, dass diese Art der Tree-Repräsentation an klassische Datenstrukturen wie Heaps und Disjoint Sets erinnere.
• Abschließend erklärt ein Kommentar, dass auch Array-Indizes eine Art „Pointer“ seien und dass traditionelle Tree-Implementierungen malloc benötigen, weil Knoten dynamisch hinzugefügt oder entfernt werden müssen. Wenn die Größe des Trees begrenzt ist und selten gelöscht wird, könne eine Array-Implementierung gut geeignet sein.