रस्सियाँ - फास्ट लाइन्स

हेलो, हैबर।
हममें से ज्यादातर लोग एक या दूसरे तरीके से काम करते हैं। इसे टाला नहीं जा सकता - यदि आप कोड लिखते हैं, तो आपको हर दिन लाइनों को मोड़ने, उन्हें घटक भागों में तोड़ने, और इंडेक्स द्वारा व्यक्तिगत वर्णों तक पहुंचने के लिए बर्बाद किया जाता है। हम लंबे समय से इस तथ्य के आदी रहे हैं कि तार एक निश्चित लंबाई के पात्रों के सरणियाँ हैं, और यह उनके साथ काम करने में संबंधित प्रतिबंधों को पूरा करता है।
इसलिए, हम जल्दी से दो लाइनों को जोड़ नहीं सकते हैं - इसके लिए हमें पहले आवश्यक मात्रा में मेमोरी आवंटित करनी होगी, और फिर वहां मौजूद लाइनों से डेटा कॉपी करना होगा। जाहिर है, इस तरह के ऑपरेशन में ओ (एन) के आदेश की जटिलता है, जहां एन लाइनों की कुल लंबाई है।
यही कारण है कि कोड

string s = ""; for (int i = 0; i < 100000; i++) s += "a"; 

इतनी धीमी गति से काम करता है।

विशाल तार को जल्दी से बदलना चाहते हैं? इस तथ्य को पसंद नहीं है कि स्ट्रिंग को भंडारण के लिए स्मृति के एक सन्निहित क्षेत्र की आवश्यकता है? तार बनाने के लिए बफ़र्स के उपयोग से थक गए हैं?


डेटा संरचना जो हमें बचाएगा उसे रस्सी स्ट्रिंग , या "रस्सी स्ट्रिंग" कहा जाता है। इसके संचालन का सिद्धांत बहुत सरल है और सहज विचार से शाब्दिक रूप से अनुमान लगाया जा सकता है।

विचार

मान लें कि हमें दो लाइनें जोड़ने की आवश्यकता है:



क्लासिक लाइनों के लिए, हम केवल आवश्यक आकार के मेमोरी क्षेत्र का चयन करते हैं, पहली पंक्ति की सामग्री को शुरुआत में और दूसरे से अंत तक कॉपी करते हैं:



जैसा कि ऊपर उल्लेख किया गया है, इस ऑपरेशन की जटिलता ओ (एन) है।

लेकिन क्या होगा अगर हम इस जानकारी का उपयोग करते हैं कि हमारा परिणामी स्ट्रिंग दो स्रोत वाले का एक संयोजन है? दरअसल, हम एक वस्तु बनाते हैं जो एक स्ट्रिंग इंटरफ़ेस प्रदान करती है और इसके घटकों के बारे में जानकारी संग्रहीत करती है - स्रोत तार:



स्ट्रिंग्स के संयोजन का यह तरीका ओ (1) के लिए काम करता है - हमें केवल स्रोत स्ट्रिंग्स के लिए एक आवरण ऑब्जेक्ट बनाने की आवश्यकता है। चूँकि यह ऑब्जेक्ट भी एक स्ट्रिंग है, इसलिए इसे अन्य स्ट्रिंग्स के साथ जोड़ा जा सकता है, जो हमें आवश्यक हैं:



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

अनुक्रमण

अब हम इसके सूचकांक द्वारा एक स्ट्रिंग चरित्र प्राप्त करने के संचालन को लागू करते हैं। ऐसा करने के लिए, हम पेड़ के नोड्स के लिए एक अतिरिक्त विशेषता का परिचय देते हैं - वजन। यदि प्रतीकों का एक हिस्सा सीधे पेड़ के नोड (नोड - लीफ) में संग्रहीत किया जाता है, तो इसका वजन इन प्रतीकों की संख्या के बराबर है। अन्यथा, नोड का वजन इसके वंश के वजन के योग के बराबर है। दूसरे शब्दों में, एक नोड का वजन स्ट्रिंग की लंबाई है जो इसे दर्शाता है।

हमें नोड नोड द्वारा दर्शाए गए स्ट्रिंग के ith चरित्र को प्राप्त करने की आवश्यकता है। तब दो मामले सामने आ सकते हैं:

• नोड - शीट। तब इसमें सीधे डेटा होता है और यह हमारे लिए "आंतरिक" स्ट्रिंग के i-th वर्ण को वापस करने के लिए पर्याप्त है।
• नोड समग्र है। फिर आपको यह पता लगाने की आवश्यकता है कि नोड के किस वंश को खोज जारी रखना चाहिए। यदि बाएं बच्चे का वजन i से अधिक है - मांगे गए चरित्र बाएं प्रतिस्थापन का i-th वर्ण है, अन्यथा यह सही प्रतिस्थापन का (iw) -थ चरित्र है, जहां w बाएं उपरी का वजन है।

इन गणनाओं के बाद, एल्गोरिथ्म का पुनरावर्ती संस्करण (साथ ही पुनरावृत्त एक) स्पष्ट हो जाता है।

अब हम O (1) के लिए तारों को समतल कर सकते हैं और O (h) - पेड़ की ऊँचाई के लिए उनमें अक्षरों को अनुक्रमित कर सकते हैं। लेकिन पूरी खुशी के लिए, आपको सीखना होगा कि कैसे जल्दी से दो लाइनों में टूटने, हटाने और एक सबरिंग डालने के संचालन को निष्पादित करना है।

टूट रहा है

तो, हमारे पास एक तार है और हमारे लिए यह आवश्यक है कि हम इसके कुछ पदों में दो पदार्थों में विभाजित करें k (चित्र में संख्याएँ इसी पेड़ों के आकार हैं):



"लाइन ब्रेक" का स्थान हमेशा पेड़ की पत्तियों में से एक में स्थित होता है। हम इस शीट को मूल शीट के दो नए भागों में विभाजित करते हैं। इसके अलावा, इस ऑपरेशन के लिए हमें शीट की सामग्री को नए लोगों को कॉपी करने की आवश्यकता नहीं है, बस शीट की ऐसी विशेषताओं को ऑफसेट और लंबाई के रूप में दर्ज करें और नई शीटों में मूल के पात्रों के सरणी में पॉइंटर्स को सहेजें, केवल ऑफ़सेट और लंबाई को बदलते हुए:



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



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



स्ट्रिंग स्प्लिट ऑपरेशन की जटिलता स्पष्ट रूप से ओ (एच) है।

हटाएं और चिपकाएँ

पहले से लागू किए गए विभाजन और विलय के कार्यों के लिए धन्यवाद, विलोपन और सम्मिलन तत्व रूप से किया जाता है - एक विकल्प को हटाने के लिए, हटाए गए अनुभाग की शुरुआत और अंत में स्रोत लाइन को तोड़ने और अंतिम लाइनों को गोंद करने के लिए पर्याप्त है। एक विशिष्ट स्थिति में लाइनों में सम्मिलित करने के लिए, हम मूल लाइन को दो सब्सट्रिंग्स में तोड़ते हैं और उन्हें वांछित क्रम में एक सम्मिलित के साथ गोंद करते हैं। दोनों ऑपरेशनों में O (h) का स्पर्शोन्मुखी व्यवहार है।

अनुकूलन

संतुलन

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



इससे बचने के लिए, हम लाइनों के प्रत्येक संयोजन पर परिणाम के संतुलन की जांच करेंगे और यदि आवश्यक हो, तो इसे संतुलित करते हुए, पूरे पेड़ का पुनर्निर्माण करें। संतुलन के लिए एक अच्छी स्थिति यह है कि स्ट्रिंग की लंबाई फाइबोनैचि संख्या की कम से कम (h + 2) होनी चाहिए। इस स्थिति के लिए औचित्य के साथ-साथ ग्लूइंग ऑपरेशन के अतिरिक्त संशोधनों को बोम, एटकिन्सन और प्लास ने अपने काम में दिया था।

छोटी रेखाओं का प्रत्यक्ष संघटन

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

अंतिम स्थिति कैशिंग

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

पिछले अनुकूलन के साथ मिलकर, यह तकनीक हमें O (ln (n)) से लगभग O (1) तक सूचकांक स्पर्शोन्नति में सुधार करने की अनुमति देगा।

परिणाम

परिणामस्वरूप हमें क्या मिलता है? हम एक निरंतर स्ट्रिंग कार्यान्वयन प्राप्त करेंगे जिसमें भंडारण के लिए एक निरंतर मेमोरी क्षेत्र की आवश्यकता नहीं है, सम्मिलन, विलोपन और कंक्रीटिंग के लॉगरिदमिक स्पर्शोन्मुख व्यवहार (शास्त्रीय स्ट्रिंग्स में ओ (एन के बजाय)) और लगभग ओ (1) को अनुक्रमित करने पर ध्यान देने योग्य है।

और अंत में, मैं आपको कुछ उपयोगी लिंक दे दूंगा: अंग्रेजी विकि में एक लेख , एक जावा कार्यान्वयन और SGI वेबसाइट पर C ++ कार्यान्वयन का विवरण ।

रस्सियों का उपयोग करें, ल्यूक!