Factorio में B-Tree

 (razberry.substack.com)
4 पॉइंट द्वारा GN⁺ 2023-11-17 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Database Internals बुक क्लब का B-Tree अध्याय पढ़ने के बाद, डेटा संरचना को कोड की बजाय Factorio फैक्टरी संरचना के रूप में लागू करके अवधारणा को दृश्य रूप से परखा गया
  • BST में बाएँ·दाएँ शाखाएँ तभी संभव हैं जब keys को sort किया जा सके, और अगर मान एक तरफ़ ज़्यादा जमा हो जाएँ तो search efficiency रैखिक list के स्तर तक गिर सकती है
  • डिस्क-आधारित storage में BST का rebalance cost और कई pages पढ़ने का बोझ होता है, जबकि B-Tree एक node में कई keys रखकर इस समस्या को कम करता है
  • Factorio implementation में nodes और comparison operations को लकड़ी के chest और बैंगनी filter inserter से दिखाया गया है, और search path बनाने के लिए items का एक मनमाना sort order तय किया गया है
  • B-Tree version में प्रति node 3 keys और 4 pointers का उपयोग किया गया, जिससे 2 स्तरों में BST की तुलना में कहीं अधिक keys रखी जा सकती हैं, लेकिन value representation और manual sorting की समस्या अभी भी बनी हुई है

BST और B-Tree का अंतर

  • Binary Search Tree (BST) में हर node एक key रखता है, और कम key को बाएँ node की ओर, जबकि बड़ी key को दाएँ node की ओर भेजता है
    • उदाहरण root key 8, बाएँ 3, दाएँ 10 से शुरू होता है
    • यह केवल sort किए जा सकने वाले values पर काम करता है, जहाँ key values की ऊँच-नीच की तुलना की जा सकती है
  • अगर values ज़्यादातर एक ही तरफ़ जुड़ती जाएँ तो BST का संतुलन बिगड़ जाता है
    • सबसे खराब स्थिति में यह 8 -> 10 -> 14 जैसी रैखिक sorted list के लगभग समान हो जाता है
    • 10 को root पर रखकर 8, 14 को दोनों तरफ़ रखने जैसे तरीके से इस असंतुलन को ठीक किया जा सकता है
  • डिस्क-आधारित storage में BST नुकसानदेह होता है
    • लगातार rebalance करने पर डिस्क और pointers को बार-बार update करना पड़ता है
    • पड़ोसी nodes अलग-अलग pages में stored हो सकते हैं, इसलिए एक search में भी कई pages पढ़ने पड़ सकते हैं
  • B-Tree एक node में कई keys रखता है, और keys की संख्या + 1 pointers से child nodes की ओर इशारा करता है
    • उदाहरण का [17 | 24] node, 17 से छोटी key, 17 और 24 के बीच की key, और 24 से बड़ी key वाले तीन child nodes में branch करता है

Factorio के अंदर लागू किया गया search tree

  • Factorio एक factory-building game है, और इस implementation में हर tree node को गेम के अंदर की संरचना से दर्शाया गया है
  • पहले एक साधारण BST बनाया गया
    • हर node में एक key रखने वाला लकड़ी का chest और दूसरे nodes तक जाने वाले दो paths होते हैं
    • materials के बीच कोई default comparison method नहीं होने के कारण wood, coal, stone, brick, copper, iron, steel क्रम में एक मनमाना sorting standard रखा गया
    • बैंगनी filter inserter comparison check का काम करते हैं
      • पहले node में एक inserter यह जाँचता है कि item brick के बराबर है या नहीं
      • दूसरा inserter यह देखता है कि वह wood, coal, stone की तरह brick से छोटा है या नहीं
      • तीसरा inserter copper, iron, steel जैसे बड़े values को अलग करता है
    • ऊपर दाईं ओर conveyor belt में गलती से आए items हटाने के लिए एक garbage collector भी रखा गया
  • B-Tree implementation में एक node के लिए और अधिक संरचनाओं की ज़रूरत होती है
    • हर node में 3 keys, 3 filter inserter, 3 लकड़ी के chest, और 4 child pointers रखे गए
    • इससे एक ही depth पर अधिक जानकारी रखी जा सकती है
    • 2 स्तरों में BST 2 keys रखता है, लेकिन B-Tree 12 keys रखता है
    • 3 स्तरों में B-Tree 48 keys तक बढ़ जाता है
  • Factorio में 48 items को हाथ से चुनकर sort करना नहीं चाहने के कारण, बेहतर value representation का तरीका मिलने तक B-Tree को खाली छोड़ा गया
  • BST और B-Tree की साथ-साथ तुलना की गई है, और YouTube वीडियो भी साथ रखा गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-11-17
Hacker News की रायें

  • यह एक अक्षम design है, लेकिन Factorio में computer science theory लागू करने का मतलब अनिवार्य रूप से optimal न होने वाले तरीके से खेलना भी है
    Factorio B-Tree दिखाने के लिए बना game नहीं है; उसके tools भी आखिरकार Factorio खेलने के लिए ही design किए गए हैं

    1. 2-3 tree, red-black tree, B-Tree जैसे self-balancing trees का core कोई single tree structure अपने-आप में नहीं, बल्कि उसका खुद balance करना है; Factorio में tree को खुद को restructure करने लायक नहीं बनाया जा सकता, इसलिए उसकी सबसे बड़ी खूबी ही गायब है
    2. optimization के नजरिए से inserter, belt से धीमा है. एक belt पर 4 inserter लगाने पर भी वे लगभग 12 items प्रति सेकंड ही ले जा पाते हैं, जबकि blue belt 45 items प्रति सेकंड धकेल सकता है. अगर केवल belt इस्तेमाल करने वाला optimal design हो, तो 45 items प्रति सेकंड पर काम करने वाले splitter का इस्तेमाल होना चाहिए
    3. इसलिए splitter और computer science का मिलन-बिंदु Factorio के splitter और Benes network हैं. अगर आप सिर्फ 2-input 2-output crossbar से बने networks पढ़ना चाहते हैं, तो https://en.wikipedia.org/wiki/Clos_network से शुरू कर सकते हैं. Benes network असल में 2-input 2-output size का Clos network ही है, और Clos network 5-बनाम-7 जैसे मनमाने sizes में भी हो सकता है
      Factorio में देखने लायक meta शायद “mixed belt” designs है
    • और खास रूप में, sushi belt होता है, जिसमें एक belt कई materials को balanced तरीके से लेकर खुद ही एक loop में घूमता है
      कुछ designs तय ratio में नए items को केवल स्वीकार करते हैं, जबकि कुछ गड़बड़ी होने पर सच में फिर से balance भी करते हैं. निजी तौर पर मुझे यह सबसे पसंद है: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      यह example in-game circuit logic इस्तेमाल करता है, लेकिन Factorio forum में बिना circuit वाला section भी है: https://forums.factorio.com/viewforum.php?f=202
      दिलचस्प बात यह है कि Factorio का “fish” object एक बेकार joke item है, और क्योंकि उसका कहीं इस्तेमाल नहीं होता, कभी-कभी उसे null value, belt ने एक चक्कर पूरा कर लिया इसका flag, या debugging tool के रूप में इस्तेमाल किया जाता है: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • सोचता हूं कि “Scriptorio” जैसा कोई Factorio extension हो, जो conveyor belt पर JSON रखने दे. साथ में JavaScript या Lua function factories भी इस्तेमाल हों
      तब insert/search किए जाने वाले objects ही नहीं, B-Tree खुद भी conveyor belts और inserters से move कराया जा सकेगा
      factory से गुजरते conveyor belt loop के जरिए recursive search function लिखकर, leaf तक पहुंचने तक tree को एक-एक level खोलते हुए चलाया जा सकता है और loop तोड़कर result output किया जा सकता है
      यह standard JavaScript के बजाय data-flow जैसा एक रोचक execution model है. क्या अलग-अलग conveyor belts, inserters और factories में उसी underlying JSON object की multiple references रखकर “quantum tunneling” या “action at a distance” allow करना चाहिए? उपयोगी तो हो सकता है, लेकिन Factorio परंपरागत रूप से हर physical item को unique identity वाला मानता है, इसलिए multiple references support न करना शायद ज्यादा “realistic” होगा. या फिर “Quantum Tunneling JSON” technology research करने के बाद केवल “JSON Reference Entangler Factory” में ही multiple references बनाने दिए जा सकते हैं
    • Clos network वाला लेख सरसरी तौर पर देखने पर लगता है कि अगर Factorio में ऐसा network बनाया जा सके, तो यहां दिखने जैसी simple neural network design भी संभव लगती है: [1]
      किसी खास position पर पहुंचने वाले resource density को weight देकर output बदलने जैसी चीज भी संभव लगती है. यहां दिख रहे mechanism [2] को देखें तो merging/splitting और तीन belt speeds से density-weighted decision-making बनाई जा सकती है
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • अगली बार देखना चाहूंगा कि क्या self-balancing तक implement किया जा सकता है. मुझे लगा bots यहां काम के हो सकते हैं, लेकिन पता नहीं bots से blueprints dynamically construct करवाना संभव है या नहीं
    • इसलिए मैं Factorio नहीं खेलता. इतना brain resource मानवता के लिए इस्तेमाल किया जा सकता है, और result दिखाने पर social media reactions भी मिल सकते हैं
      screen पर numbers के बदले brainpower मांगने वाले games मेरी list में सबसे नीचे हैं. मैं कुछ नया सीखना चाहता हूं
      puzzle element हो सकता है और हम तय कर सकते हैं कि वह मजेदार है, लेकिन पढ़ाई को भी मजेदार मान सकते हैं, ऐसा नहीं है क्या

  • शानदार काम है
    “Database Internals” को book club में पढ़ रहा हूं, और सुना है कि इस हफ्ते B-Tree को cover करने वाला chapter 2 था
    संदर्भ के लिए, आवेदन बंद हो चुके हैं, लेकिन अगर चाहें तो Database Internals लेकर यहां के schedule और notes के साथ “read-only” mode में follow कर सकते हैं: https://eatonphil.com/2023-database-internals.html

  • “बाइनरी सर्च ट्री disk-based storage के लिए अच्छा नहीं है” वाली वजहें memory storage पर भी लागू होती हैं
    एक B-Tree node को search करना, binary tree में उतनी ही मात्रा के pointers follow करने से तेज़ होता है। हाँ, implementation complexity बढ़ती है, लेकिन अगर आप C नहीं लिख रहे हैं तो आम तौर पर tree-based map खुद implement नहीं करेंगे
    ऐसी variants भी संभव हैं जिनमें internal nodes में ज़्यादा entries रखी जाएँ और values सिर्फ leaves में store हों। बशर्ते आप map नहीं, सिर्फ set न बना रहे हों। इसमें पड़ोसी nodes को भी link कर दें तो यह असल में skip list के काफी करीब हो जाता है

  • समझ नहीं आता कि ठीक यहीं Factorio content क्यों आ गया और फिर से करीब 100 घंटे डूब जाने की इच्छा क्यों जगा दी। इस साल भी खेलने लायक अच्छे games पहले ही बहुत ज़्यादा हैं

    • अगले साल के आखिर तक बड़ा rebalance और Space Age expansion pack planned है, इसलिए तब तक इंतज़ार करना भी ठीक हो सकता है

  • यह सब splitters से भी किया जा सकता है, और chests या filter inserters की ज़रूरत नहीं लगती। explanation अच्छा है

    • कैसे करना है, समझ नहीं आ रहा
      बात सिर्फ output को कई lines में बाँटने की नहीं है। chests यहाँ 2D में रखे गए B-Tree के उस “node” में stored items को represent करते हैं
      video देखने का समय नहीं था, लेकिन article और screenshots देखकर लगता है कि inserters में related logic लगा है, जो tree की “sorted” property बनाए रखने के लिए items को सही child node path पर भेजता है
      original post में key values की choice देखें तो splitters से बाँटना भी संभव तो होगा, लेकिन याद के मुताबिक splitter सिर्फ एक filter ले सकता है, इसलिए हर branch point पर कई splitters चाहिए होंगे। मतलब उस branch point के item count जितने। filter inserters कई filters allow करते हैं, इसलिए यहाँ थोड़ा बेहतर हैं, और पहले screenshot में भी दिखता है
      बेशक B-Tree design को पूरी तरह छोड़कर n splitters से n chests में sort कर सकते हैं, लेकिन वह मज़ेदार नहीं है और लगता नहीं कि original post का इरादा भी वही था
    • हर inserter को कई items assign किए गए हैं
      splitter filter सिर्फ एक item को एक तरफ भेजता है और बाकी को दूसरी तरफ। लेकिन यह example अलग है, क्योंकि कई types एक तरफ जाते हैं और कई types दूसरी तरफ
    • कई items को sort/filter करना पड़ता है। उदाहरण के लिए पहले node में wood, coal, stone को left भेजना है और metals को right, लेकिन splitter filter सिर्फ एक item filter कर सकता है

  • सोच रहा हूँ कि Factorio सच में इतना अच्छा game है क्या। सब कहते हैं अच्छा है, लेकिन factory बनाना वाला topic थोड़ा boring लगता है और डर है कि game बहुत repetitive होगा

    • try करने से पहले मैं भी काफी skeptical था और वही चिंता थी। फिर होश आया तो देखता हूँ कि 100 घंटे से ज़्यादा लगा चुका था
    • जितने Factorio players को मैं जानता हूँ, सबने 1,000 घंटे से ज़्यादा लगाए हैं

  • सचमुच शानदार है, लेकिन लिखने वालों के बीच की बात कहूँ तो sentences की शुरुआत में capital letters न इस्तेमाल करना काफी distracting लगता है

  • मुझे लगा था कि इसे Factorio के circuit system से implement किया जाएगा