मिनी-पहेली: "ओल्ड-स्कूल" ट्री

समस्या का बयान

कुछ दिन पहले, एरिक लिपर्ट ने अपने शानदार एडवेंचर्स इन कोडिंग ब्लॉग पर एक बहुत ही सरल लेकिन मनोरंजक कार्य पोस्ट किया:



एक पेड़ है जिसे नोड वर्ग का उपयोग करके परिभाषित किया गया है, जिसमें एक ही नोड वाले बच्चे और कुछ पाठ हैं (मैं नीचे एक कक्षा कोड दूंगा)। इस तरह की एक लाइन (लाइन ब्रेक सहित) उत्पन्न करना आवश्यक है:

आपको यूनिकोड वर्णों का उपयोग करने की आवश्यकता है "un se └ (" (छद्म विज्ञान के साथ अच्छे पुराने चित्रों को याद रखें)। एरिक ने खुद के लिए जो लक्ष्य निर्धारित किया है, यह पता लगाने के लिए कि निर्णय लेते समय क्या प्राथमिकताएँ होंगी: पुनरावर्ती (एक पेड़ के रूप में), तेज या अधिक पठनीय।

स्रोत कोड कक्षा नोड:

class Node<br>{<br> public Node( string text, params Node[] children)<br> {<br> this .Text = text;<br> this .Children = children ?? new Node[] {};<br> }<br> public string Text { get ; private set ; }<br> public IList<Node> Children { get ; private set ; }<br>} <br><br> * This source code was highlighted with Source Code Highlighter .

स्रोत डेटा:

var root = new Node( "a" , <br> new Node( "b" ,<br> new Node( "c" , <br> new Node( "d" )),<br> new Node( "e" ,<br> new Node( "f" ))),<br> new Node( "g" , <br> new Node( "h" ,<br> new Node( "i" )),<br> new Node( "j" ))); <br><br> * This source code was highlighted with Source Code Highlighter .

कार्य यहां लापता लाइनों को भरना है:

sealed class Dumper<br>{<br> static public string Dump(Node root) { /* ... */ }<br> /* ... */ <br>} <br><br> * This source code was highlighted with Source Code Highlighter .

समाधान

इसलिए, जैसा कि मुझे हैबरपेज़र में "<स्पॉइलर>" टैग नहीं मिला, और मैं स्पष्ट रूप से समाधान प्रदान नहीं करना चाहता। अपने स्वयं के निर्णय को लिखने की खुशी से खुद को वंचित न करने के लिए, मैं अपने स्वयं के निर्णयों के लिंक प्रदान करूंगा और थोड़ा समझाऊंगा।



लेकिन मैं फिर भी आपको सलाह दूंगा कि आप अपना निर्णय लिखते हुए एक दर्जन मिनट बिताएँ। यदि कोई आईडीई या शुरुआत करने के लिए बहुत आलसी नहीं है, तो मैं स्निपेट कंपाइलर की सिफारिश करता हूं (हालांकि यह केवल .NET 3.5 के लिए है, 4.0 के लिए मुझे ऐसा कुछ भी नहीं मिला - ताकि कोड पूर्णता के साथ, बिना फाइलें बनाए)।

पहला दृष्टिकोण

सबसे पहले, मैंने खुद को सबसे LINQ-way जाने का कार्य निर्धारित किया, बिल्कुल निष्पादन की गति पर विचार नहीं किया। यह काफी दिलचस्प निकला - लाइनक जैसा विकल्प । कोड में सभी ट्री नोड्स और पुनरावृत्ति के दोनों पुनरावर्ती संलयन शामिल हैं। कृपया ध्यान दें कि गणना "आलसी" है, सभी लाइनें या तो StringBuilder द्वारा या LinkedList का उपयोग करके एकत्र की जाती हैं और फिर Join द्वारा एकत्रित की जाती हैं, जो लाइनों की अनावश्यक प्रतिलिपि या स्थानांतरण सरणियों को कम करता है।



विकल्प धीमा निकला। बहुत।

दूसरा तरीका

आलसी कंप्यूटिंग, आदि। बेशक यह सुंदर है, लेकिन मैं गति के संदर्भ में सबसे इष्टतम कार्यान्वयन लिखना चाहता था। यह देखते हुए कि "स्तर" इंडेंटेशन हमेशा समान होता है, और हम हर बार जब हम एक नया स्तर जोड़ते हैं, तो हम इसका उपयोग कर सकते हैं, मैंने इसे इस तरह के विकल्प में खींचने का फैसला किया। सभी एक समारोह में, केवल एक सहायक कंटेनर वर्ग जोड़ा गया। वही स्ट्रिंगबर्ल, लेकिन, इस बार, इंडेंट के टुकड़ों के लिए किसी भी सरणियों को छोड़ने का फैसला किया। और फिर, कोई पुनरावृत्ति नहीं - पेड़ के माध्यम से पारित होने और परिणाम का निर्माण एक साथ होता है।



इस विकल्प ने निष्पादन की गति के मामले में बहुत अच्छा होने से इनकार कर दिया। मैं अभी थोड़ा आगे चला जाऊंगा, मेरा कहना है कि यह कभी-कभी एरिक के "विस्तृत" संस्करण (जो गहराई से अधिक बच्चों के साथ है) से भी तेज है।

एरिक का फैसला

खैर, एरिक का फैसला । अजीब तरह से पर्याप्त है, इसमें मैंने अपने "त्वरित" निर्णय में बहुत कुछ पाया - उदाहरण के लिए, वह कैसे जांचता है कि "बच्चों" की सूची में अंतिम आइटम है या नहीं।



व्यक्तिगत रूप से, मुझे यह समस्या पसंद आई क्योंकि मुझे एक-दो बार कुछ इसी तरह हल करना था। और अपने दिमाग को फैलाना अच्छा है।



यदि कोई भी तेज़ विकल्प के साथ आता है - लिखो, तो C # कोड को अनुकूलित करने के लिए दृष्टिकोणों को देखना दिलचस्प है। और यद्यपि यह पोस्ट खेल प्रोग्रामिंग में लिखे गए समान है, लेकिन मुझे लगता है कि यह कार्य अन्य प्लेटफार्मों और भाषाओं के साथ कार्यान्वयन की तुलना करने के लिए बहुत सरल है।



इसके अलावा, शायद मेरी पोस्ट किसी को दिलचस्प दृष्टिकोण खोजने में मदद करेगी जो कि अन्य कार्यों में उपयोग की जा सकती है: एक पेड़ का उपयोग करते हुए IEnumerable दोनों पुनरावर्ती और नहीं; एक लिंक्डलिस्ट और शायद कुछ और का उपयोग करके तारों का निर्माण।



खैर, उन लोगों के लिए जिनके लिए कार्य तुच्छ लग रहा था, और समाधान कोई दिलचस्पी नहीं है, मैं समय बिताने के लिए माफी चाहता हूं।



युपीडी:

एरिक का केवल एक फ़ंक्शन के रूप में lam0x86 का संशोधित संस्करण: वॉच

लाइनक का उपयोग करते हुए सक्रिय रूप से स्टेक से दो बहुत ही संक्षिप्त विकल्प