Atree: सरल और कुशल pointer-less Tree implementation

• C++ में Apter Trees
• सिर्फ़ दो vectors का उपयोग करके सरल रूप से दर्शाया गया tree: [node value, parent index)
• ज़्यादातर tree, binary tree की तरह implement किए जाते हैं, जहाँ हर node में अपनी value और बाएँ/दाएँ child node के pointers शामिल होते हैं
• इस तरह की data structure को recursion से implement करना पड़ता है, और cache behavior तथा बार-बार होने वाले malloc() की वजह से यह धीमी हो सकती है
• multi-layer software में कौन tree node को "own" करता है, यह concept जटिल हो सकता है
• Apter tree काफ़ी तेज़, समझने में आसान, और implement करने में आसान है

यह कैसे काम करता है

• समान आकार के दो arrays से implement किया जाता है
  • data का vector (array) d
  • parent indices का vector p. d vector का index key की तरह उपयोग होता है (c)
  • अक्सर key/index c integer type का होता है
• अगर Coco, Molly और Arca का parent है, और Arca का एक child Cricket है, तो structure इस तरह होगा
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• जिसका parent 0 है और key 0 है, वह node root node है (Apter tree में root node अनिवार्य होता है, या फिर -1 का मतलब "कोई parent नहीं" हो सकता है, लेकिन यहाँ इसे नज़रअंदाज़ किया गया है)
• कंप्यूटर vectors को बहुत तेज़ी से manipulate कर सकता है। pointer operations की तुलना में यह काफ़ी तेज़ है, इसलिए algorithms की big-O notation की तुलना व्यवहार में उतनी अर्थपूर्ण नहीं होती

यह क्यों महत्वपूर्ण है

• यह implementation style, लेखक द्वारा देखी गई tree implementations में सबसे elegant है
• सही vector operation library के साथ इसे समझना आसान है और bugs ढूँढना भी आसान है
• इसकी simplicity के कारण इसे दूसरे use cases में आसानी से लागू किया जा सकता है
• parent index vector को नज़रअंदाज़ करके values पर तेज़ी से iterate किया जा सकता है, जो एक तरह के freely available Deep Map जैसा है
• यह GPU-friendly है और embedded environments में उपयोग करना आसान है
• vectors का size किसी निश्चित सीमा से आगे न बढ़ने देकर security को आसानी से बनाए रखा जा सकता है

उत्पत्ति

• लेखक इस technique के आविष्कारक को खोजने की कोशिश कर रहे हैं, और अनुमान है कि 60s और 70s के vector-oriented दौर में इसका पहले से कोई नाम रहा होगा
• Apter द्वारा बताए गए रूप में इसका पहला complete description देखा गया, लेकिन K3 में भी यह अच्छी तरह documented है
• APL पारंपरिक तरीके से tree implement करता है, लेकिन vector graphs के लिए इसी तरह की techniques का उपयोग करता है
• J users के बीच भी यह जाना-पहचाना है, और Rosetta Code में J language की tree implementation पर इसका विवरण है
• John Earnest vector tree implementation को और विस्तार से समझाते हैं, जिसमें deletion entries के लिए "offset index" approach भी शामिल है
• एक और जटिल approach हर item की depth को track करना है

दूसरी सामान्य tree implementations

• FreeBSD का kernel tree implementation, klib के tree, Ruby का tree class, और Python declarative tree classes जैसे उदाहरण मौजूद हैं
• ये Apter tree जैसा बिल्कुल वही काम नहीं करते, और कुछ implementations generalization की वजह से काफ़ी बड़े हैं

इस code की वर्तमान स्थिति

• C++17 सीखने के लिए इसे implement करने का प्रयास किया गया
• यह अभी production use के लिए तैयार नहीं है, और C++ के बारे में अभी और सीखने की ज़रूरत है

GN⁺ की राय

• Apter Trees, पारंपरिक जटिल tree structures को सरल बनाकर तेज़ और कुशल data management संभव बनाते हैं
• vector-based tree implementation memory overhead को कम कर सकता है और linear access के ज़रिए performance बेहतर कर सकता है
• यह लेख software engineering में data structures के लिए एक innovative approach की खोज को रोचक बनाता है

[GN⁺]

Hacker News राय

• एक उपयोगकर्ता ने यह देखकर आश्चर्य व्यक्त किया कि उनका काम Hacker News पर लिंक किया गया था। उन्होंने हल्के array-आधारित data structures में अपनी रुचि का उल्लेख किया, खासकर उस implementation style का जो अक्सर 3D model skinning के लिए node trees में इस्तेमाल होता है। उन्होंने समझाया कि अगर array को इस तरह sort किया जाए कि parent node child node से पहले आए, तो सभी nodes के लिए world transforms को फिर से calculate करना एक साधारण loop से किया जा सकता है.
• एक अन्य उपयोगकर्ता ने, इस टिप्पणी के जवाब में कि इस तरह की tree style में child nodes पर iterate करना O(N) है, कहा कि first child और next sibling को point करने वाले pointers जोड़कर atree design को generalize करना वास्तव में आसान है। उन्होंने यह भी कहा कि ज़रूरी operations को support करने के लिए data structure को बदलना चाहिए.
• एक उपयोगकर्ता ने दावा किया कि nodes को array में store करना और index को pointer की तरह इस्तेमाल करना tree algorithms को implement करने के लिए ज़रूरी है। खास तौर पर, अगर node के children तक पहुँचना हो, तो memory बचाने के लिए internal nodes और leaf nodes के लिए अलग structures पर विचार करना चाहिए.
• एक अन्य उपयोगकर्ता ने कहा कि parent array से tree को represent करने का तरीका Hacker News पर इतना ध्यान पा रहा है, यह कुछ अजीब है। उनके अनुसार, यह दिखाता है कि अच्छी presentation किसी बुनियादी idea को कितनी दूर तक पहुँचा सकती है.
• एक उपयोगकर्ता ने इशारा किया कि यह project बस system pointers को अपने pointers से बदलने भर का काम करता है.
• एक अन्य उपयोगकर्ता ने सुझाव दिया कि अगर उद्देश्य mallocs को कम करना और data locality को बेहतर बनाना है, तो node pool का उपयोग करने वाली पारंपरिक tree implementation आज़मानी चाहिए.
• एक टिप्पणी में Aaron Hsu की APL का उपयोग करने वाली व्याख्या देखने की सिफारिश की गई.
• एक उपयोगकर्ता ने structure को इस तरह बदलने का सुझाव दिया कि किसी node के सभी children को साथ में pack किया जाए। उन्होंने कहा कि इससे binary search के जरिए किसी node के सभी children की सूची ढूँढी जा सकती है और यह cache-friendly भी होगा.
• एक टिप्पणी में array के index को handle या index-handle कहे जाने का ज़िक्र है, और कहा गया कि tree को represent करने का यह तरीका heap और disjoint set जैसी classic data structures की याद दिलाता है.
• अंत में, एक टिप्पणी में समझाया गया कि array index भी एक तरह का pointer माना जा सकता है, और पारंपरिक tree implementations में malloc की ज़रूरत इसलिए पड़ती है क्योंकि nodes को dynamically जोड़ना या हटाना पड़ सकता है। अगर tree का आकार सीमित हो और deletions बार-बार न हों, तो array implementation उपयुक्त हो सकती है.