👨🏼‍🔧 💼 ⚙️ एक पाठ संपादक में स्मृति का संगठन 🍹 👨‍👦‍👦 🏺

कम से कम सबसे सरल पाठ संपादक को कम स्तर पर प्रोग्राम करने की कोशिश करने वाले सभी को संपादन योग्य पाठ को संग्रहीत करने के लिए स्मृति को व्यवस्थित करने के कार्य का सामना करना पड़ा। पाठ को संग्रहीत करने के लिए डेटा संरचना को निम्न आवश्यकताओं को पूरा करना चाहिए:

कम स्मृति उपरि है। उपलब्ध मेमोरी का अधिकांश उपयोग पाठ को संग्रहीत करने के लिए किया जाना चाहिए, ओवरहेड जानकारी पर नहीं;
पाठ में किसी भी स्थान पर कुशल सम्मिलन और विलोपन की अनुमति दें।

इन आवश्यकताओं को पूरा करना एक ही समय में आसान नहीं है। यदि हम अच्छी तरह से ज्ञात डेटा संरचनाओं, जैसे कि सरणियों, सूचियों, पेड़ों, ढेर, कतारों, रिंग बफ़र्स पर विचार करते हैं - तो ऐसी संरचना जो हमें दोनों आवश्यकताओं को प्रभावी ढंग से पूरा करने की अनुमति देती है, नहीं मिली है। एक सरणी के मामले में, हमारे पास महत्वहीन मेमोरी ओवरहेड है, लेकिन सम्मिलित ऑपरेशन में जटिलता ओ (n) है, जहां n संपादित पाठ का आकार है। एक सूची के मामले में, डालने और हटाने की जटिलता हे (1) है, हालांकि, मेमोरी ओवरहेड पाठ के आकार से कई गुना अधिक है। संपादक में पाठ संग्रहीत करने के लिए पेड़, ढेर, अंगूठी बफ़र, साहचर्य सरणियाँ और अन्य संरचनाएं पूरी तरह से अनुपयुक्त हैं।

हाइब्रिड समाधान होते हैं जब पाठ को सरणियों के एक सेट में संग्रहीत किया जाता है, जो बदले में, एक सूची में संयुक्त होते हैं। ऐसा लगता है कि यह दृष्टिकोण आपको सरणियों और सूचियों के फायदे (त्वरित मेमोरी / कम मेमोरी ओवरहेड के साथ हटाने) को संयोजित करने की अनुमति देता है। हालांकि, इस तरह के समाधान को लागू करना मुश्किल है। यह भी स्मृति विखंडन की ओर जाता है।

मैं आपके ध्यान में संपादन योग्य पाठ को संग्रहीत करने के लिए एक प्रभावी डेटा संरचना लाता हूं, जिसे लागू करना आसान है, किसी भी स्थान पर निरंतर मेमोरी ओवरहेड और त्वरित सम्मिलित / हटाना है। यह आपको उन फ़ाइलों को प्रभावी ढंग से संपादित करने की अनुमति देता है जो पूरी तरह से रैम में फिट नहीं होते हैं।

इस तथ्य के बावजूद कि इस डेटा संरचना को बहुत पहले खोजा गया था और 8-बिट युग में पुराने कंप्यूटरों पर पाठ संपादकों में उपयोग किया गया था, पूर्वजों का यह गुप्त ज्ञान काफी हद तक खो गया था और आधुनिक संपादकों में दुर्लभ है। नोटपैड या सुदूर में 10 मेगाबाइट की एक पंक्ति से युक्त फ़ाइल खोलने का प्रयास करें। वर्णों को सम्मिलित करना और हटाना अंतिम सेकंड में होगा।

विवरण

हम एक निश्चित आकार के मेमोरी ब्लॉक लेते हैं (पुराने 8-बिट कंप्यूटर में, इस ब्लॉक के लिए सभी मुफ्त मेमोरी ली जाती है) और इस ब्लॉक की शुरुआत में कर्सर से पहले संपादन योग्य टेक्स्ट और ब्लॉक के अंत में कर्सर के बाद का टेक्स्ट रखें। पाठ को दो निरंतर टुकड़ों में मेमोरी में संग्रहीत किया जाता है, और उनके बीच के अंतराल में सभी उपलब्ध मुफ्त टेक्स्ट मेमोरी है। पाठ को संपादित करने की प्रक्रिया में, हम इस अपरिवर्तनीय का समर्थन करते हैं: बफर की शुरुआत में कर्सर से पहले पाठ होता है, और अंत में कर्सर के बाद का पाठ होता है। वह सब है!

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

के विश्लेषण

पेस्ट और डिलीट ऑपरेशंस सस्ते होते हैं: O (1) दोनों जब किसी एक कैरेक्टर और उनके ग्रुप को पेस्ट करते हैं (उदाहरण के लिए, क्लिपबोर्ड से पेस्ट करना)।
मेमोरी ओवरहेड कम है: O (1)। केवल कर्सर स्थिति और कुल बफर आकार को संग्रहीत करने की आवश्यकता है।
सूचकांक खोज ऑपरेशन सस्ता है: ओ (1)।
सामग्री के अनुभाग की प्रतिलिपि बनाने का कार्य (उदाहरण के लिए, क्लिपबोर्ड पर कॉपी करने या डिस्क पर पाठ को सहेजने के लिए) हे (n) है, जहां n प्रतिलिपि किए गए अनुभाग का आकार है। एक सरणी के लिए जटिलता समान है।

दूसरे शब्दों में, उपरोक्त कार्यों के लिए, सरणी को प्रदान करने वाले सभी लाभों का एहसास करना संभव था।

गैप बफर का उपयोग करते समय, कर्सर को हिलाने की लागत एक टेक्स्ट एडिटर में दिखाई देती है। आखिरकार, अपरिवर्तनीय को सुनिश्चित करने के लिए, आपको बफर के निचले भरे हुए हिस्से से ऊपर या इसके विपरीत पाठ को कॉपी करना होगा। कर्सर को ले जाने की कठिनाई O (n) है, जहां n वह स्थान है जहां कर्सर चलता है। पाठ के आरंभ से अंत तक चलते समय, ध्यान देने योग्य उपयोगकर्ता विलंब हो सकता है। हालाँकि, किसी पाठ के आरंभ से अंत तक इसे संपादित करते समय अपेक्षाकृत दुर्लभ संचालन होता है। अधिक बार किसी वर्ण, रेखा या पृष्ठ के आगे या पीछे की ओर से मूवमेंट होते हैं, और फिर आपको केवल पाठ के एक छोटे से भाग को स्थानांतरित करना होता है। 8-बिट कंप्यूटर के लिए भी विलंब अदृश्य होगा।

इस प्रकार, गैप बफर टेक्स्ट एडिटिंग प्रक्रिया की संपत्ति का शोषण करता है जो उस स्थान पर हमेशा कार्रवाई करता है और हटाता है जहां कर्सर होता है; बदले में, कर्सर आंदोलनों आमतौर पर छोटे होते हैं।

विविधताओं

1. छाया रिकॉर्डिंग कर्सर

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

2. उन फ़ाइलों को संपादित करना जो रैम में फिट नहीं होती हैं

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

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

मेमोरी में एक स्टैक ऊपर या नीचे हो सकता है, और एक फाइल के रूप में लागू स्टैक केवल बड़ा हो सकता है। केवल फ़ाइल के अंत में हम डेटा को जोड़ सकते हैं, या इसके विपरीत, उन्हें वहां से हटा सकते हैं। यदि हम अब मेमोरी ऑपरेशंस पर लौटते हैं और विभिन्न दिशाओं में बढ़ते हुए ढेरों पर विचार करते हैं, तो हम देख सकते हैं कि ढेर ऊपर की तरफ बढ़ रहा है, डेटा को सीधे क्रम में व्यवस्थित किया जाता है, ताकि स्टैक पर उनके प्लेसमेंट के क्रम के संबंध में, और नीचे की तरफ बढ़ते हुए स्टैक में, रिवर्स ऑर्डर में । इसलिए अगर हम गैप बफर को दो स्टैक के रूप में ऊपर की ओर बढ़ाना चाहते हैं, तो हमें दूसरे स्टैक में उन तत्वों के क्रम को बदलना होगा, जो कर्सर के बाद टेक्स्ट को स्टोर करते हैं। इसलिए, अस्थायी फ़ाइल जिसमें कर्सर के बाद डेटा होता है, उसे रिवर्स ऑर्डर में, वापस सामने रखना होगा।

अस्थायी फ़ाइलों में, हम ढेर की सभी सामग्रियों को संग्रहीत नहीं करेंगे, लेकिन केवल उनके निचले हिस्से को। ऊपरी भाग रैम में स्थित होगा, एक प्रकार का "स्थानीय" गैप बफर बनाने और उपयोगकर्ता को पहले की तरह अनुमति देने के लिए, जल्दी से पाठ को संपादित करने और कुछ सीमाओं के भीतर इसके चारों ओर घूमने के लिए। जब कर्सर मेमोरी में लोड किए गए क्षेत्र के बाहर के पाठ पर चला जाता है, तो कर्सर से उसके भाग को अस्थायी फ़ाइलों में से एक में सहेजा जाएगा, और लापता भाग दूसरे से लोड किया जाएगा।

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

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

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

पाठ को मेमोरी में लोड किए बिना वर्णित तरीके से कार्यान्वित करना, इसलिए, डिस्क स्थान पर मध्यम ओवरहेड: अस्थायी फ़ाइलों को पाठ के आकार के बराबर स्थान की आवश्यकता होती है।

यह दिलचस्प है कि भले ही पाठ की एक बड़ी मात्रा मूल रूप से रैम में मिलती है, एक संपादक का उपयोग करते समय जो इसे अपनी संपूर्णता में लोड नहीं करता है, ऐसे दस्तावेज़ तेजी से खुलेंगे। फिर से, उपयोगकर्ता की सुविधा में सुधार।

निष्कर्ष

यह पहली बार नहीं है जब मैं इस तथ्य के बारे में आया हूं कि विकलांग कंप्यूटरों के लिए विकसित कुछ तकनीकों को हमारे समय में भुला दिया गया है, जिससे अक्षम समाधानों का प्रसार होता है। मुझे उम्मीद है कि इस लेख में वर्णित "पूर्वजों का गुप्त ज्ञान" अच्छे पाठ संपादकों के उद्भव में मदद करेगा।

धन्यवाद

मैंने पहली बार zx.pk.ru फोरम के एक विषय में एक ईएसएल उपयोगकर्ता से वर्णित डेटा संरचना के बारे में सीखा। उन्होंने ZX स्पेक्ट्रम जैसे सीमित संसाधनों वाले कंप्यूटर के संबंध में एक टेक्स्ट एडिटर के लिए मेमोरी के आयोजन के मुद्दे पर भी चर्चा की।

एक पाठ संपादक में स्मृति का संगठन