नकली पेड़: सरल UI के लिए indentation का उपयोग

 (ratfactor.com)
4 पॉइंट द्वारा GN⁺ 2024-01-01 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • भले ही UI को hierarchical दिखना हो, पहले यह जांचना चाहिए कि क्या डेटा में सचमुच parent-child relationship होना जरूरी है, या सिर्फ ऐसा दिखना ही काफी है
  • अगर असली tree की जरूरत नहीं है, तो parent ID के बजाय पूरी सूची के absolute sort order और indent वैल्यू से स्क्रीन पर संरचना दिखाई जा सकती है
  • Hiss game editor banana.eat जैसे नामों को sort करने के बाद dot (.) के बाद वाले हिस्से को indented दिखाकर namespace जैसा दिखने वाला UI बनाता है
  • यह तरीका उस word processor-शैली editing के ज्यादा करीब है जिसमें user items को ऊपर-नीचे ले जाता है और indent/outdent करता है, इसलिए tree data structure का बोझ कम हो जाता है
  • लेकिन अगर items के बीच संबंधों को वास्तव में query या maintain करना है, तो indentation या string symbol hacks के बजाय सचमुच का tree model चाहिए

पेड़ नहीं, लेकिन पेड़ जैसा दिखने वाला list

  • जब किसी application में Foo, Bar जैसी dynamic list को tree view में दिखाने की कोशिश की जाती है, तो आम तौर पर हर item को उसके parent item से जोड़ने वाली संरचना की कल्पना की जाती है
  • relational database में, उदाहरण के लिए, parent column में parent ID store की जा सकती है
    • Foo का parent null है
    • Foo 1 का parent Foo है
    • Foo 1.a का parent Foo 1 है
  • ऐसे tree data को SQL में लाने के लिए recursive CTE जैसी तकनीक की जरूरत पड़ सकती है
  • लेकिन कई lists में वास्तविक relationship से ज्यादा महत्वपूर्ण यह हो सकता है कि चीजें इंसानों को देखने में साफ-सुथरी तरह व्यवस्थित लगें

indentation value को data के रूप में store करने का तरीका

  • अगर असली parent-child relationship की जरूरत नहीं है, तो list को सिर्फ इन fields से store किया जा सकता है
    • id
    • sort
    • indent
    • name
  • sort किसी child group के भीतर का क्रम नहीं, बल्कि पूरी list का absolute order दिखाता है
  • indent item के आगे डाली जाने वाली space की मात्रा को सीधे दिखाता है, इसलिए screen rendering सरल हो जाती है
  • editing UI भी tree manipulation की तुलना में सरल हो सकता है
    • user items को ऊपर-नीचे move कर सकता है
    • item को indent या outdent कर सकता है
    • जरूरत हो तो सही indentation enforce करने के लिए कुछ सरल rules जोड़े जा सकते हैं
  • नतीजतन, सीधे computer science textbook वाले data structure को manipulate करने के बजाय अनुभव word processor में list edit करने जैसा हो जाता है

Hiss का dot (.) आधारित नकली namespace

  • text adventure game editor Hiss banana, banana.eat, banana.peel जैसे नामों को UI में hierarchical तरीके से दिखाता है
  • इसका मतलब यह नहीं कि HissScript में वास्तविक namespace feature implement किया गया है
  • implementation काफ़ी सरल है
    • object names को alphabetical order में sort किया जाता है
    • अगर name में dot (.) हो, तो पहले वाला हिस्सा काट दिया जाता है
    • बचे हुए हिस्से को indented करके दिखाया जाता है
  • example code का मुख्य logic भी इसी flow का पालन करता है
    • things.keys को sort किया जाता है
    • हर name में dot होने पर indentation जोड़कर dot से पहले वाला हिस्सा हटाकर output किया जाता है
    • dot न होने पर name को जैसा है वैसा output किया जाता है
  • इसके बाद कुछ और lines जोड़ी जाती हैं जो यह check करती हैं कि दिए गए prefix वाला “parent” item मौजूद है या नहीं
  • arbitrary depth की nesting भी जोड़ी जा सकती है, लेकिन उसे तब तक टाला गया है जब तक उसकी सच में जरूरत न हो
  • यह namespace जैसा दिखने वाला UI game को व्यवस्थित करने वाले व्यक्ति के लिए महत्वपूर्ण है, लेकिन game editor और player के लिए इसका कोई खास अर्थ नहीं है
    • dot वाला name भी बस एक name है
    • namespace जैसा दिखने वाला हिस्सा सिर्फ name को unique बनाए रखने का काम करता है

flat list के रूप में tree-जैसे cases को संभालना

  • Dave Long ने “low-tech real tree” के रूप में path और information को flat list में store करने का तरीका सुझाया
  • यह banana.eat वाले example जैसी ही insight है
  • find output जैसी path list की कल्पना की जा सकती है
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • अगर depth-first traversal चाहिए, तो paths को lexicographic order में sort करना काफी है
  • अगर breadth-first traversal चाहिए, तो path separator के आधार पर paths को उलटकर, depth match करने के लिए खाली items जोड़कर sort किया जा सकता है
  • यह example सिर्फ concept दिखाने के लिए है; व्यवहार में separator पर split करके array के रूप में process करना ज्यादा स्वाभाविक होगा
  • flat lists को कुल मिलाकर संभालना आसान होता है, और जहाँ संभव हो, items को plain old lists में रखने वाला approach पसंद किया जाता है

फ़र्श पर scrapbook वाली उपमा

  • व्यक्तिगत scrapbook बनाते समय फोटो, notes, postcards, tickets वगैरह को फ़र्श पर फैलाकर groups बनाए जा सकते हैं
  • इंसान को group relationship साफ़ दिखाई दे सकती है, लेकिन फ़र्श खुद उस relationship को enforce करने वाला कोई physical mechanism नहीं देता
  • इस उपमा का सार यह है कि दिखाई गई relationship और वास्तविक structural relationship अलग हो सकती हैं
  • UI list में भी यही बात लागू होती है: जो arrangement इंसान को hierarchical दिखती है, ज़रूरी नहीं कि वह internal data model में असली hierarchy ही हो

जब सचमुच tree की जरूरत हो

  • indentation या string symbols पर आधारित तरीका स्थिति के अनुसार काफी बदलना पड़ सकता है, और सामान्य programming context में इसे hack माना जा सकता है
  • अगर वास्तव में items के बीच relationship जाननी हो, तो parent ID, parent-child join table आदि जैसे data model के अनुरूप असली tree structure का उपयोग करना चाहिए
  • अगर स्थिति ऐसी हो जैसे बड़े research project को classify करना, जहाँ physical file cabinet और folder-level organization चाहिए, तो “फ़र्श वाला तरीका” उपयुक्त नहीं है
  • अगर किसी project में बाद में वास्तव में items के बीच संबंध जानने की जरूरत पड़ेगी, तो indentation या string के भीतर symbols की संख्या से structure की नकल करना project की पूरी उम्र और maintenance period में दर्दनाक रास्ता साबित हो सकता है

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

1 टिप्पणियां

 
GN⁺ 2024-01-01
Hacker News की रायें

  • पहला तरीका, यानी वह जो “जाहिर है, यही एक तरीका है” जैसा लगता है, adjacency list कहलाता है
    दूसरा “काफ़ी सरल तरीका” मैंने पहले नहीं देखा था, और इसके कुछ स्पष्ट नुकसान हैं, लेकिन कुछ मामलों में यह काफ़ी लग सकता है
    तीसरे “namespace वाले” तरीके को materialized path कहा जाता है, और यह tree को दर्शाने का एक और तरीका है; इसके अलावा nested sets भी होते हैं: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    जब लोग relational database को गंभीरता से लेते थे, तब यह सब अच्छी तरह जाना-पहचाना था, और उदाहरण के लिए http://www.dbazine.com/oracle/or-articles/tropashko4/ जैसे लेख भी थे
    अब यह भूला हुआ ज्ञान लगता है

    • मेरी पिछली नौकरी के सबसे नापसंद पलों में से एक वह था जब मैं किसी समस्या को समझाने में बहुत मेहनत कर रहा था, और तभी किसी ने पहचान लिया कि उसका नाम पहले से है और उस पर रिसर्च हो चुकी है—यानी यह एक मौजूदा अवधारणा है
      जब आप खुद किसी समस्या के अलग-अलग पहलुओं को समझ रहे होते हैं, तब उस अवधारणा का पहले से मौजूद नाम ढूँढना सच में बहुत मुश्किल लगता है
    • सही बात है। आजकल भर्ती किए जाने वाले युवा graduates हर चीज़ को NoSQL documents में ठूँस देना चाहते हैं और data modeling के बारे में लगभग सोचना ही नहीं चाहते
      नतीजा यह होता है कि tree दिखाने का सारा logic code में संभालना पड़ता है, जबकि modern relational databases और कुछ CTEs से कई use cases को बहुत elegant तरीके से लगभग मुफ़्त में संभाला जा सकता है
    • इसे भूला हुआ ज्ञान कहना मुश्किल है। “Joe Celko's Trees and Hierarchies in SQL” नाम की एक किताब भी है
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • अगर इस विषय में रुचि है, तो शुरुआत में https://en.m.wikipedia.org/wiki/Joe_Celko पर दी गई उनकी किताबों को देखना अच्छा रहेगा

  • Postgres में ltree data type और search operators हैं जो इस तरह native रूप से काम करते हैं: https://www.postgresql.org/docs/current/ltree.html
    उदाहरण के लिए, CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy'); की तरह डालकर
    SELECT path FROM test WHERE path <@ 'Top.Science'; से Top.Science और Top.Science.Astronomy खोजे जा सकते हैं

    • प्रोग्रामर सावधान: ltree की एक विचित्र बात यह है कि tree के रूप में देखने पर parent node बनने वाले intermediate paths का वास्तव में मौजूद होना ज़रूरी नहीं है
      ऊपर के उदाहरण में अगर Top.Science record हटा भी दें, तो Top.Science.Astronomy record नहीं कटेगा
      ltree value के labels materialized path के ज़रिए एक logical tree का संकेत देते हैं, लेकिन वे यह बाध्य नहीं करते कि संकेतित सभी parent nodes के लिए records मौजूद हों
      application के अनुसार यह ठीक वही व्यवहार हो सकता है जो आप चाहते हैं, या बिल्कुल उसका उलटा। अगर दूसरा मामला है, तो integrity बनाए रखने के लिए अलग व्यवस्था करनी होगी
    • अगर file paths स्टोर करने हों, तो क्या delimiter के रूप में / इस्तेमाल किया जा सकता है?
    • जानना चाहूँगा कि performance का अनुभव कैसा है। इसमें काफ़ी regex processing लगती दिखती है
    • SQL Server में भी बहुत मिलती-जुलती functionality है[1], और मेरे अनुभव में यह काफ़ी अच्छी तरह काम करती है
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • सोच रहा हूँ क्या यही काम JSON column से भी किया जा सकता है। तब nodes में strings के अलावा दूसरे data types भी इस्तेमाल किए जा सकते हैं
      बस चिंता यह है कि शायद JSON indexes, ltree indexes जितने अच्छे से काम न करें

  • यहाँ समस्या यह है कि इस संरचना का मूल्य आम तौर पर display tree में नहीं, बल्कि डेटा की hierarchy में होता है
    संभावना है कि आपको डेटा को traverse करना, संबंध दिखाना, या उसे reorder करना जैसे काम करने पड़ें
    database के data structure में visual information भरना जोखिम भरा और short-sighted लगता है

    • लेखक ने पहले ही साफ़ कहा है कि “लोग हमेशा सोचते हैं कि parent-child संबंधों को औपचारिक रूप से encode करना चाहिए, लेकिन वास्तव में हर बार ऐसा नहीं होता, और कभी-कभी सिर्फ nested display की ज़रूरत होती है”, तो उस पर यह प्रतिक्रिया कुछ अजीब लगती है
      क्या जवाब यह है कि “नहीं, ऐसा हो ही नहीं सकता”?
      YAGNI एक मशहूर design heuristic है, इसके पीछे वजह है। “मान लो कि हमेशा ज़रूरत पड़ेगी” सही नहीं है
    • विडंबना यह है कि अब भी डेटा के भीतर parent ID का ही उपयोग किया जा रहा है
      बस optimized data type के dedicated column में रखने के बजाय उसे data string के आगे जोड़ दिया गया है
      यह संख्या न भी हो, और ID column भी न हो, फिर भी यह किसी दूसरे expected value की ओर इशारा करने वाला identifier ही है; format बदल जाने से वह parent ID होना बंद नहीं हो जाता
    • मूल क्रम/indentation encoding में भी parent-child संबंध आसानी से reconstruct किए जा सकने चाहिए
      बेशक यह सुनिश्चित करना होगा कि parent के बिना child जैसी गलत indentation save न हो
      इसलिए सबसे आसान तरीका पहले order/depth के रूप में store करना है, और जब ज़रूरी features लागू करने हों तब parent/child model में migrate करना है
      लेकिन “indentation” को render होने वाली spaces की संख्या के रूप में नहीं, बल्कि tree में depth के रूप में अधिक abstract तरीके से परिभाषित करना बेहतर है। इससे गलत data ढूँढना आसान होता है, बाद की migration भी आसान होती है, और nested /, tabs, 8 spaces, 4 spaces, 1 space जैसी user-specific rendering flexibility भी मिलती है
    • अगर struct item_t { char key[255]; char display_value[255]; } जैसी data structure हो, और key में a/b/c की तरह एक consistent path separator हो, तो parent और child ढूँढना बहुत आसान हो जाता है
      सबसे खराब स्थिति में array को linear scan करना होगा, और अगर sort किया गया है, तो parent तक पहुँचने के लिए सिर्फ पिछले items देखने होंगे
    • पूरी तरह सहमत। Denormalization कभी-कभी अच्छा विकल्प हो सकता है, लेकिन इस मामले में यह कोई उचित justification नहीं लगता

  • मैंने एक ऐसी company शुरू की थी जहाँ tree-shaped data बहुत था। tree structure को indented list में बदलना O(n) समय में संभव है
    यह उस समय interview questions में से एक था, और कई SQL databases में ऐसे तरीके होते हैं जिनसे recursive query के बिना भी tree के हिस्से को तेज़ी से लाकर render करने लायक रूप में store किया जा सकता है
    एक बार आप इन concepts को समझ लें, तो डेटा को सही तरह tree के रूप में store करने के फायदे इस तरह की indentation से कहीं ज़्यादा होते हैं

    • अगर उन फायदों की ज़रूरत ही नहीं है, तो यह बहुत मायने नहीं रखता

  • “SQL query के ज़रिए relational database से tree-structured data लाने का एक तरीका recursive CTE(Common Table Expressions) का उपयोग करना है, और यह उसके नाम जितना ही मज़ेदार है”
    CTE डरावना नहीं है, recursive CTE समेत भी, और इसकी आदत पड़ जाए तो यह सच में मज़ेदार लग सकता है

    • CTE कोई खास मज़ेदार चीज़ नहीं है। जिस हिस्से में दिलचस्पी है उसे debug करने के लिए CTE tower को किसी दूसरी SQL window में copy-paste करना मेरे लिए मनोरंजन नहीं है
    • normalized representation से tree data assemble करते समय recursive CTE बहुत धीमा था
      hierarchy depth d वाले node path को assemble करने पर query result मिलने का समय कम से कम d गुना धीमा हो गया
      फायदा यह था कि tree edit operations सस्ते थे, लेकिन वे read की तुलना में बहुत कम होते थे
    • CTE ठीक है। लेखक इस जानकारी को table में bake करने के बजाय, CTE से formatted names वाली एक view भी बना सकता था

  • “लोगों को वास्तव में tree चाहिए या ज़रूरत होती है, ऐसा कम होता है; ज़्यादा बार उन्हें सिर्फ tree जैसा दिखने वाला कुछ चाहिए होता है” — इस बिंदु पर HN और Reddit का फर्क दिखता है
    HN में child comments, parent comment के nextSibling होते हैं, और parent के indentation value में 1 जोड़कर उसे tree जैसा दिखाया जाता है
    Reddit में, कम से कम old.reddit.com पर, child comments वास्तव में parent comment के अंदर nested होते हैं। नई site के बारे में नहीं पता

    • आपका मतलब वास्तविक display से नहीं, बल्कि HTML structure से है, सही? स्क्रीन पर दिखने वाला रूप तो लगभग एक जैसा है
    • यह कल्पना करना मुश्किल है कि backend में इसे सचमुच ऐसे store किया जाता होगा
      डेटा पर होने वाले सारे operations, पहले tree structure infer करके फिर उसे वापस implicit tree format में translate करने वाली जटिल अव्यवस्था बन जाएँगे
    • फिर folding कैसे काम करती है, यह जानने की जिज्ञासा है

  • लेख का मुख्य विचार सरल है। समस्या के अनुसार सही structure का उपयोग करना चाहिए
    लेकिन मुझे इसकी narrative गलत लगती है। database से tree लाने के लिए CTE अनिवार्य नहीं है; आप flat list ला सकते हैं और local स्तर पर tree बना सकते हैं। बाद की manipulation के लिए भी वैसे भी ऐसा करना पड़ सकता है
    इसी तर्क से, list store करने के लिए relational database इस्तेमाल करने वालों से यह भी कहा जा सकता है कि text file में store करो। network latency की लागत क्यों उठानी?
    दूसरी ओर, प्रस्तावित structure बड़े tree में branch को move करने और depth बदलने के लिए पर्याप्त अच्छा नहीं है, क्योंकि इसकी लागत linear है
    शुरुआत से ही इरादा साफ़ करना चाहिए था। तीन examples समझाने के बाद निष्कर्ष में “अगर tree चाहिए तो tree इस्तेमाल करो” कहकर उन्हें निष्प्रभावी नहीं करना चाहिए था। हालाँकि अगर यह बात लेख की शुरुआत में होती, तो यह काफी कम clickbait लगता

  • कुछ साल पहले OpenGL के बारे में मुझे इसी तरह की समझ मिली थी। मुझे hierarchical 3D objects की दुनिया draw करने की ज़रूरत नहीं थी, बल्कि sorted triangle list draw करनी थी
    उस विचार ने दिमाग में एक switch on कर दिया, और कई optimizations बहुत आसान हो गईं

    • सही है। 2000 के बाद के 3D games में simplicity एक बड़ी ताकत रही है
      जिन games में complex entity hierarchies होती हैं, उनमें भी render queue में डालते समय transparency sorting जैसी वजहों से अक्सर उन्हें flat structure में fold करना पड़ता है
      “चीज़ों की flat list” ECS/DOD की बुनियाद भी है

  • database में इस तरह के काम को संभालने पर पूरी की पूरी किताबें हैं
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • लोग कहते थे कि सारी किताबें beginners के लिए होती हैं, अच्छा है

  • fake tree बनाने का एक और तरीका JSON blob store करना है
    अगर डेटा के संबंध सिर्फ अंदरूनी हों, तो unique और ordered sorting numbers बनाए रखने की तुलना में यह आसान हो सकता है

    • nested JSON में व्यक्त किया गया tree, database में parent reference store करके मिलने वाले virtual tree की तुलना में कुछ मायनों में ज़्यादा “real” tree माना जा सकता है