Factorio में B-ट्री

 (razberry.substack.com)
4 पॉइंट द्वारा GN⁺ 2023-11-17 | 1 टिप्पणियां | WhatsApp पर शेयर करें

B-ट्री के बारे में सीखना

  • Binary Search Trees (BSTs): हर node में एक key होती है; बायां node कम key value रखता है, और दायां node अधिक key value रखता है।

  • BST तभी काम करता है जब keys को sort किया जा सके, और अगर values सिर्फ एक तरफ जोड़ी जाएं तो balance बिगड़ जाता है और efficiency घट जाती है।

  • balance बिगड़े हुए BST को pivoting के जरिए ठीक किया जा सकता है, लेकिन यह disk-based storage के लिए उपयुक्त नहीं है (बार-बार rebalancing की ज़रूरत होती है, और पास-पास के node अलग-अलग pages में store हो सकते हैं)।

  • B-Trees: ऐसे nodes से बने होते हैं जिनमें binary tree की तुलना में अधिक keys और pointers होते हैं।

  • हर node में कई keys होती हैं, और हर key के अनुसार कई pointers होते हैं (उदाहरण: 17 और 24 keys वाला node उन nodes की ओर pointers रखेगा जिनकी keys 17 से छोटी हैं, 17 और 24 के बीच हैं, और 24 से बड़ी हैं)।

Factorio में B-ट्री का implementation

  • Factorio (factory-building game) में एक सरल binary search tree implementation: हर node एक wooden chest (key) और दो paths (pointers) से बना होता है।
  • materials की value की तुलना करने का कोई तरीका नहीं है, इसलिए एक मनमाना क्रम दिया जाता है, और filter inserters का उपयोग तुलना के लिए किया जाता है।
  • B-ट्री implementation अधिक जटिल है: हर node में तीन keys और चार child nodes की ओर pointers होते हैं।
  • B-ट्री अधिक जानकारी store कर सकता है, और items को manually sort करने के बजाय tree को फिलहाल खाली छोड़ा जाता है, जब तक बाद में इसे दर्शाने का बेहतर तरीका न मिल जाए।

GN⁺ की राय

  • इस लेख की सबसे महत्वपूर्ण बात B-ट्री की अवधारणा को समझना और उसे Factorio गेम में लागू करने का रचनात्मक तरीका है।
  • पाठकों के लिए दिलचस्प बात यह है कि यह computer science की जटिल data structures को गेम के माध्यम से visual और intuitive तरीके से समझने का अवसर देता है।
  • ऐसा दृष्टिकोण सीखने को अधिक मज़ेदार और आकर्षक बनाता है, और software engineering की बुनियादी अवधारणाओं को गेम जैसे गैर-पारंपरिक माध्यमों के जरिए समझने का नया तरीका पेश करता है।

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

1 टिप्पणियां

 
GN⁺ 2023-11-17
Hacker News राय
  • Factorio गेम का डिज़ाइन computer science theory को पूरी तरह प्रतिबिंबित नहीं करता, और सैद्धांतिक रूप से optimized play के बजाय गेम का आनंद लेने पर ध्यान देता है।
  • Factorio में self-balancing binary tree (2-3 tree, red-black tree, B-tree) को दोबारा संरचित नहीं किया जा सकता, इसलिए इसकी सबसे महत्वपूर्ण विशेषता, self-balancing, गायब है।
  • Optimization के नज़रिए से, Factorio के inserter belt से धीमे हैं; 4 inserter मिलकर एक belt पर प्रति सेकंड 12 items संभालते हैं, जबकि blue belt प्रति सेकंड 45 items तक संभाल सकती है, इसलिए optimal belt-only design के लिए splitter का उपयोग सुझाया जाता है।
  • Computer science और splitter का संयोजन Benes network की अवधारणा को शामिल करता है (ऐसा network जो केवल 2-input 2-output crossbar से बना हो), और efficient factory design के लिए इस पर अध्ययन करना ज़रूरी है।
  • Factorio में mixed belt design महत्वपूर्ण है, और database की internal structure पर किताबें पढ़ना मददगार हो सकता है।
  • Binary search tree (BST) disk-based storage के लिए उपयुक्त नहीं है, और B-tree node search binary tree pointer traversal से तेज़ होती है। Implementation complexity बढ़ती है, लेकिन जब तक आप C language का उपयोग नहीं कर रहे, tree-based map खुद implement करने की नौबत कम ही आती है।
  • यह भी बताया गया कि capital letters का न होना लेख पढ़ने में बाधा बन सकता है।
  • Factorio से जुड़ा content साझा होने पर फिर से सैकड़ों घंटे इस गेम में लगाने की इच्छा जाग उठती है।
  • हर काम केवल splitter से किया जा सकता है, और chest तथा filter inserter की ज़रूरत नहीं है।
  • यह भी कहा गया कि उम्मीद थी इसे Factorio के circuit का उपयोग करके implement किया गया होगा, लेकिन ऐसा नहीं था।