B-Bäume in Factorio

 (razberry.substack.com)
4 Punkte von GN⁺ 2023-11-17 | 1 Kommentare | Auf WhatsApp teilen
  • Nach der Lektüre des Kapitels zu B-Trees im Buchclub zu Database Internals wurde die Datenstruktur nicht als Code, sondern als Fabrikstruktur in Factorio implementiert, um das Konzept visuell zu überprüfen.
  • Ein BST kann nur dann nach links und rechts verzweigen, wenn Schlüssel sortierbar sind; häufen sich Werte auf einer Seite, kann die Sucheffizienz auf das Niveau einer linearen Liste sinken.
  • Bei plattenbasierter Speicherung sind die Rebalancing-Kosten eines BST und das Lesen mehrerer Pages problematisch; ein B-Tree reduziert dieses Problem, indem er mehrere Schlüssel in einem Node speichert.
  • Die Factorio-Implementierung stellt Nodes und Vergleichsoperationen mit Holzkisten und violetten Filtergreifarmen dar und legt eine willkürliche Sortierreihenfolge für Items fest, um Suchpfade zu erzeugen.
  • Die B-Tree-Version verwendet 3 Schlüssel und 4 Pointer pro Node und kann auf 2 Ebenen deutlich mehr Schlüssel aufnehmen als ein BST; Probleme bei der Wertdarstellung und der manuellen Sortierung bleiben jedoch bestehen.

Unterschied zwischen BST und B-Tree

  • Ein binärer Suchbaum (BST) speichert in jedem Node einen Schlüssel; niedrigere Schlüssel gehen zum linken Node, höhere Schlüssel zum rechten Node.
    • Das Beispiel beginnt mit dem Root-Schlüssel 8, links 3 und rechts 10.
    • Es funktioniert nur mit sortierbaren Werten, bei denen sich höhere und niedrigere Schlüssel vergleichen lassen.
  • Wenn viele Werte nur auf einer Seite hinzugefügt werden, gerät der BST aus dem Gleichgewicht.
    • Im schlimmsten Fall wird er fast zu einer linear sortierten Liste wie 8 -> 10 -> 14.
    • Die Unwucht lässt sich korrigieren, indem man etwa 10 als Pivot an die Root setzt und 8 sowie 14 auf beide Seiten verteilt.
  • Bei plattenbasierter Speicherung ist ein BST im Nachteil.
    • Wenn ständig rebalanciert wird, müssen Platte und Pointer häufig aktualisiert werden.
    • Benachbarte Nodes können auf unterschiedlichen Pages gespeichert sein, sodass selbst für eine einzelne Suche mehrere Pages gelesen werden müssen.
  • Ein B-Tree speichert mehrere Schlüssel in einem Node und verweist mit Anzahl der Schlüssel + 1 Pointern auf Child-Nodes.
    • Der Beispiel-Node [17 | 24] verzweigt zu drei Child-Nodes: Schlüssel kleiner als 17, Schlüssel zwischen 17 und 24 sowie Schlüssel größer als 24.

Der in Factorio implementierte Suchbaum

  • Factorio ist ein Fabrikbau-Spiel; in der Implementierung wird jeder Tree-Node als Struktur im Spiel dargestellt.
  • Zunächst wird ein einfacher BST gebaut.
    • Jeder Node hat eine Holzkiste, die einen Schlüssel enthält, sowie zwei Pfade zu anderen Nodes.
    • Da es zwischen Materialien keine eingebaute Vergleichsmethode gibt, wird mit wood, coal, stone, brick, copper, iron, steel eine willkürliche Sortierreihenfolge festgelegt.
    • Violette Filtergreifarme übernehmen die Vergleichsprüfung.
      • Im ersten Node prüft ein Greifarm, ob das Item brick entspricht.
      • Der zweite Greifarm prüft, ob es kleiner als brick ist, etwa wood, coal, stone.
      • Der dritte Greifarm filtert größere Werte wie copper, iron, steel heraus.
    • Oben rechts gibt es außerdem einen Garbage Collector, der Items entfernt, die fälschlich auf das Förderband geraten sind.
  • Die B-Tree-Implementierung benötigt in einem einzelnen Node mehr Strukturen.
    • Jeder Node enthält 3 Schlüssel, 3 Filtergreifarme, 3 Holzkisten und 4 Child-Pointer.
    • Auf derselben Tiefe kann er mehr Informationen speichern.
    • Auf 2 Ebenen speichert ein BST 2 Schlüssel, ein B-Tree dagegen 12 Schlüssel.
    • Auf 3 Ebenen wächst der B-Tree auf bis zu 48 Schlüssel.
  • Da es unpraktisch wäre, 48 Items in Factorio manuell auszuwählen und zu sortieren, bleibt der B-Tree leer, bis eine bessere Methode zur Wertdarstellung gefunden ist.
  • BST und B-Tree werden nebeneinander verglichen; außerdem ist ein YouTube-Video beigefügt.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-11-17
Hacker-News-Kommentare

  • Es ist ein ineffizientes Design, aber Informatiktheorie in Factorio umzusetzen bedeutet zwangsläufig auch, auf nicht optimale Weise zu spielen.
    Factorio ist kein Spiel, das dafür gemacht wurde, einen B-Tree vorzuführen; auch die Werkzeuge sind letztlich dafür ausgelegt, Factorio zu spielen.

    1. Der Kern von selbstbalancierenden Bäumen wie 2-3-Bäumen, Red-Black Trees oder B-Trees ist nicht die einzelne Baumstruktur an sich, sondern der Teil, in dem sie sich selbst ausbalancieren. In Factorio kann man den Baum aber nicht dazu bringen, sich selbst umzubauen, daher fehlt sein wichtigstes Merkmal.
    2. Aus Optimierungssicht sind Inserter langsamer als Bänder. Selbst mit vier Insertern pro Band bewegt man nur etwa 12 Items pro Sekunde, während ein blaues Band 45 Items pro Sekunde transportieren kann. Ein optimales Design, das nur Bänder verwendet, müsste mit Splittern arbeiten, die mit 45 Items pro Sekunde laufen.
    3. Der Punkt, an dem Splitter und Informatik aufeinandertreffen, sind daher die Splitter in Factorio und Benes-Netzwerke. Wenn man Netzwerke untersuchen will, die nur aus 2-Eingang-2-Ausgang-Crossbars bestehen, kann man bei https://en.wikipedia.org/wiki/Clos_network anfangen. Ein Benes-Netzwerk ist nur ein Clos-Netzwerk der Größe 2 Eingänge/2 Ausgänge, und Clos-Netzwerke sind auch in beliebigen Größen wie 5 zu 7 möglich.
      Die Meta, nach der man in Factorio suchen sollte, scheinen Designs mit „gemischten Bändern“ zu sein.
    • Eine konkretere Form davon sind Sushi-Bänder, bei denen ein einzelnes Band mehrere Materialien in ausgewogenem Verhältnis transportiert und im Kreis läuft.
      Manche Designs nehmen neue Items nur in einem festen Verhältnis auf, andere balancieren sich tatsächlich wieder aus, wenn sie aus dem Gleichgewicht geraten. Mir persönlich gefällt dieses hier am besten: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Dieses Beispiel nutzt die Schaltungslogik im Spiel, aber im Factorio-Forum gibt es auch einen Bereich ohne Schaltungen: https://forums.factorio.com/viewforum.php?f=202
      Interessant ist, dass das „fish“-Objekt in Factorio ein nutzloses Scherz-Item ist. Weil es nirgendwo verwendet wird, dient es manchmal als Nullwert, als Flag dafür, dass ein Band eine Runde abgeschlossen hat, oder als Debugging-Werkzeug: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Ich frage mich, wie es wäre, wenn es eine Factorio-Erweiterung wie „Scriptorio“ gäbe, mit der man JSON auf Förderbänder legen kann. Dazu könnte man Fabriken für JavaScript- oder Lua-Funktionen verwenden.
      Dann ließen sich nicht nur die einzufügenden oder zu suchenden Objekte, sondern auch der B-Tree selbst mit Förderbändern und Insertern bewegen.
      Man könnte eine rekursive Suchfunktion als Förderband-Loop durch die Fabrik schreiben, die den Baum Level für Level abträgt, bis sie ein Blatt erreicht, dann die Schleife unterbricht und das Ergebnis ausgibt.
      Das wäre ein interessantes Ausführungsmodell, eher Datenfluss als Standard-JavaScript. Sollte man zulassen, dass verschiedene Förderbänder, Inserter und Fabriken über mehrere Referenzen auf dasselbe zugrunde liegende JSON-Objekt zeigen und damit „Quantentunneln“ oder „Fernwirkung“ erlauben? Das könnte nützlich sein, aber Factorio behandelt traditionell jedes physische Item als etwas mit eigener Identität; keine mehrfachen Referenzen zu unterstützen, wäre daher vielleicht „realistischer“. Oder man könnte erst die Technologie „Quantum Tunneling JSON“ erforschen und mehrere Referenzen nur in einer „JSON Reference Entangler Factory“ erzeugen lassen.
    • Wenn ich den Artikel zu Clos-Netzwerken grob überfliege, scheint es so, als könnte man, falls sich solche Netzwerke in Factorio bauen lassen, auch einfache neuronale Netzwerkdesigns wie die hier gezeigten umsetzen: [1]
      Es müsste auch möglich sein, die Ausgabe zu verändern, indem man die Ressourcendichte gewichtet, die an einer bestimmten Position ankommt. Mit dem hier gezeigten Mechanismus [2] könnte man vermutlich durch Zusammenführen, Aufteilen und die drei Bandgeschwindigkeiten dichtegewichtete Entscheidungen bauen.
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Als Nächstes würde ich gern sehen, ob man auch Selbstbalancierung implementieren kann. Ich dachte, Bots könnten hier nützlich sein, bin mir aber nicht sicher, ob man Bots dazu bringen kann, Blueprints dynamisch zu bauen.
    • Deshalb spiele ich Factorio nicht. Diese Menge an Denkkapazität kann man für die Menschheit einsetzen, und wenn man das Ergebnis zeigt, bekommt man auch Reaktionen in sozialen Medien.
      Spiele, die Gehirnleistung im Austausch gegen Zahlen auf dem Bildschirm verlangen, stehen ganz unten auf meiner Liste. Ich möchte etwas Neues lernen.
      Es mag Puzzle-Elemente geben, und wir können beschließen, dass das Spaß macht, aber könnten wir nicht genauso beschließen, dass Lernen Spaß macht?

  • Großartige Arbeit.
    „Database Internals“ wird gerade in einem Buchclub gelesen, und diese Woche war Kapitel 2 zu B-Trees dran.
    Nebenbei: Die Anmeldung ist zwar geschlossen, aber wer möchte, kann sich Database Internals besorgen und hier anhand des Zeitplans und der Notizen „nur lesend“ mitmachen: https://eatonphil.com/2023-database-internals.html

  • Die Gründe dafür, dass „binäre Suchbäume schlecht für festplattenbasierte Speicher sind“, gelten auch für Speicher im RAM.
    Einen einzelnen B-Tree-Knoten zu durchsuchen ist schneller, als in einem binären Baum dieselbe Anzahl an Pointern zu verfolgen. Natürlich steigt die Implementierungskomplexität, aber wenn man nicht gerade C verwendet, implementiert man baumbasierte Maps normalerweise ohnehin nicht selbst.
    Varianten sind ebenfalls möglich, etwa mehr Einträge in interne Knoten zu legen und Werte nur in den Blättern zu speichern. Vorausgesetzt, man baut nicht nur eine Menge statt einer Map. Verknüpft man zusätzlich benachbarte Knoten, nähert sich das im Grunde einer Skip List an.

  • Ich weiß nicht, warum ausgerechnet hier Factorio-Content auftaucht und wieder den Drang auslöst, ungefähr 100 Stunden darin zu versenken. Dieses Jahr gibt es ohnehin schon zu viele gute Spiele, die man spielen könnte.

    • Gegen Ende nächsten Jahres sind ein großes Rebalancing und die Space Age-Erweiterung geplant; vielleicht lohnt es sich also, bis dahin zu warten.

  • Das ließe sich alles auch mit Splittern machen; Kisten oder Filter-Inserter scheinen nicht nötig zu sein. Die Erklärung ist gut.

    • Ich sehe nicht, wie das gehen soll.
      Es geht nicht einfach darum, Ausgaben auf mehrere Linien aufzuteilen. Die Kisten repräsentieren hier die Items, die in dem jeweiligen „Knoten“ des zweidimensional angeordneten B-Trees gespeichert sind.
      Ich hatte keine Zeit, das Video anzusehen, aber nach Text und Screenshots steckt die relevante Logik in den Insertern: Sie schicken Items über den passenden Pfad zum Kindknoten, sodass die „sortierte“ Eigenschaft des Baums erhalten bleibt.
      Nach der Wahl der Schlüsselwerte im Originalbeitrag wäre eine Aufteilung mit Splittern zwar möglich, aber soweit ich mich erinnere, kann ein Splitter nur einen Filter haben, sodass man an jedem Verzweigungspunkt mehrere bräuchte. Das heißt: so viele, wie es Items an diesem Verzweigungspunkt gibt. Filter-Inserter erlauben mehrere Filter und sind hier daher etwas besser; das sieht man auch im ersten Screenshot.
      Natürlich könnte man das B-Tree-Design komplett aufgeben und mit n Splittern in n Kisten sortieren, aber das wäre langweilig und scheint auch nicht die Absicht des Originalbeitrags zu sein.
    • Jedem Inserter werden mehrere Items zugewiesen.
      Ein Splitter-Filter schickt nur ein bestimmtes Item auf eine Seite und alles andere auf die andere. Dieses Beispiel ist aber anders: Mehrere Typen gehen auf die eine Seite und mehrere Typen auf die andere.
    • Mehrere Items müssen sortiert und gefiltert werden. Im ersten Knoten müssten zum Beispiel Holz, Kohle und Stein nach links und Metalle nach rechts geschickt werden, aber ein Splitter-Filter kann nur ein einziges Item filtern.

  • Ich frage mich, ob Factorio wirklich so ein gutes Spiel ist. Alle sagen, es sei großartig, aber das Thema Fabriken bauen wirkt etwas langweilig, und ich habe Sorge, dass das Spiel zu repetitiv ist.

    • Bevor ich es ausprobiert habe, war ich auch ziemlich skeptisch und hatte dieselben Bedenken. Dann habe ich mich irgendwann dabei ertappt, über 100 Stunden hineingesteckt zu haben.
    • Alle Factorio-Spieler, die ich kenne, haben über 1.000 Stunden investiert.

  • Wirklich cool, aber unter Leuten, die schreiben wollen: Es wirkt ziemlich ablenkend, am Satzanfang keine Großbuchstaben zu verwenden.

  • Ich dachte, das würde mit Factorios Schaltungssystem umgesetzt.