c - सी में मेमोरी-कुशल डबली लिंक्ड लिस्ट क्या है?




data-structures memory-efficient (4)

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

Google पर खोज करने के बाद, मैं सबसे करीब आया था। लेकिन, मैं कुछ भी समझ नहीं सका।

क्या कोई मुझे बता सकता है कि सी में मेमोरी-कुशल डबली लिंक्ड लिस्ट क्या है? सामान्य डबली लिंक्ड लिस्ट से यह अलग कैसे है?

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


एक्सओआर लिंक्ड सूची की आपको पहले से ही एक विस्तृत विस्तृत स्पष्टीकरण मिला है, मैं मेमोरी ऑप्टिमाइज़ेशन पर कुछ और विचार साझा करूंगा।

  1. पॉइंटर्स आमतौर पर 64 बिट मशीनों पर 8 बाइट्स लेते हैं। 32 बिट पॉइंटर्स के साथ 4 जीबी एड्रेस करने योग्य से अधिक RAM में किसी भी बिंदु को संबोधित करना आवश्यक है।

  2. मेमोरी प्रबंधक आम तौर पर बाइट्स नहीं, निश्चित आकार ब्लॉक के साथ सौदा करते हैं। उदाहरण के लिए सी मॉलोक आमतौर पर 16 बाइट ग्रैन्युलरिटी के भीतर आवंटित करता है।

इन दो चीजों का अर्थ यह है कि यदि आपका डेटा 1 बाइट है, तो संबंधित दोगुनी लिंक्ड सूची तत्व 32 बाइट्स (8 + 8 + 1, निकटतम 16 एकाधिक तक गोलाकार) ले जाएगा। एक्सओआर चाल के साथ आप इसे 16 तक नीचे ला सकते हैं।

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

यदि आप एक सामान्य सूची वर्ग विकसित नहीं कर रहे हैं, लेकिन आप अपने आवेदन के लिए विशिष्ट उपयोग पैटर्न जानते हैं, ऐसे मामलों में ऐसे मेमोरी मैनेजर को लागू करना एक आसान काम हो सकता है। उदाहरण के लिए, यदि आप जानते हैं कि आप कभी भी 1000 से अधिक तत्व आवंटित नहीं करेंगे और प्रत्येक तत्व 5 बाइट्स लेता है, तो आप मेमोरी मैनेजर को 5000-बाइट सरणी के रूप में एक वेरिएबल के साथ कार्यान्वित कर सकते हैं जिसमें पहले फ्री बाइट की अनुक्रमणिका होती है, और जैसे ही आप अतिरिक्त तत्व आवंटित करते हैं, आप बस उस इंडेक्स को ले लें और इसे आवंटित आकार से आगे बढ़ाएं। इस मामले में आपके पॉइंटर्स वास्तविक पॉइंटर्स नहीं होंगे (जैसे int *) लेकिन केवल 5000-बाइट सरणी के अंदर इंडेक्स होंगे।


ठीक है, तो आपने एक्सओआर लिंक्ड सूची देखी है, जो आपको प्रति आइटम एक पॉइंटर बचाती है ... लेकिन यह एक बदसूरत, बदसूरत डेटा संरचना है, और आप जितनी अच्छी तरह से कर सकते हैं उससे दूर है।

यदि आप स्मृति के बारे में चिंतित हैं, तो प्रतिदिन 1 से अधिक तत्वों के साथ एक दोगुनी-लिंक्ड सूची का उपयोग करना हमेशा बेहतर होता है, जैसे सरणी की एक लिंक की गई सूची।

उदाहरण के लिए, जबकि एक एक्सओआर लिंक्ड सूची में प्रति आइटम 1 पॉइंटर खर्च होता है, साथ ही आइटम स्वयं, 16 आइटम प्रति नोड के साथ एक दोगुनी-लिंक्ड सूची प्रत्येक 16 आइटम के लिए 3 पॉइंटर्स या प्रति आइटम 3/16 पॉइंटर्स खर्च करती है। (अतिरिक्त सूचक पूर्णांक की लागत है जो रिकॉर्ड करता है कि नोड में कितनी वस्तुएं हैं) यह 1 से कम है।

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

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

यह निर्धारित करने के लिए कि कैसे और कब आवंटित या मुक्त नोड्स निर्धारित करने के लिए कई संभावित रणनीतियां हैं।


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

एक मेमोरी-कुशल लिंक्ड सूची को एक्सओआर लिंक्ड लिस्ट भी कहा जाता है।

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

एक एक्सओआर (^) लिंक्ड लिस्ट एक लिंक लिस्ट है जिसमें next और back पॉइंटर्स को स्टोर करने की बजाय, हम केवल next और back पॉइंटर्स दोनों के काम करने के लिए एक पॉइंटर का उपयोग करते हैं। आइए पहले एक्सओआर लॉजिक गेट्स गुण देखें:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

आइए अब एक उदाहरण लें। हमारे पास चार नोड्स के साथ एक दोगुनी जुड़ी सूची है: ए, बी, सी, डी । यहां यह कैसा दिखता है:

यदि आप देखते हैं, प्रत्येक नोड में दो पॉइंटर्स होते हैं, और डेटा को संग्रहीत करने के लिए 1 चर। तो हम तीन चर का उपयोग कर रहे हैं।

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

एक मेमोरी-कुशल डबली लिंक्ड लिस्ट एक लिंक्ड लिस्ट है जिसमें हम XOR और उसके गुणों का उपयोग करके आगे और पीछे जाने के लिए केवल एक पॉइंटर का उपयोग करते हैं।

यहां एक चित्रमय प्रतिनिधित्व है:

आप आगे और आगे कैसे जाते हैं?

आपके पास एक अस्थायी चर है (केवल एक, नोड में नहीं)। मान लीजिए कि आप नोड को बाएं से दाएं स्थानांतरित कर रहे हैं। तो आप नोड ए पर शुरू करते हैं। नोड ए के सूचक में, आप नोड बी के पते को स्टोर करते हैं। फिर आप नोड बी पर जाते हैं। अस्थायी चर में, नोड बी पर जाने के दौरान, आप नोड ए के पते को स्टोर करते हैं।

नोड बी के लिंक (पॉइंटर) वैरिएबल में A ^ C का पता A ^ C । आप पिछले नोड का पता ले लेंगे (जो ए है) और एक्सओआर वर्तमान लिंक फ़ील्ड के साथ, आपको सी का पता देकर तर्कसंगत रूप से, यह इस तरह दिखेगा:

A ^ (A ^ C)

आइए अब समीकरण को सरल बनाएं। हम ब्रांड्स को हटा सकते हैं और एसोसिएटिव प्रॉपर्टी की वजह से इसे फिर से लिख सकते हैं:

A ^ A ^ C

हम इसे और सरल बना सकते हैं

0 ^ C

दूसरी ("कोई नहीं (2)" तालिका में बताए गए अनुसार) संपत्ति।

तालिका के अनुसार पहले ("कोई नहीं (1)" की वजह से) संपत्ति, यह मूल रूप से है

C

यदि आप यह सब समझ नहीं सकते हैं, तो बस तालिका में बताए गए तीसरे संपत्ति ("कोई नहीं (3)" देखें।

अब, आपको नोड सी का पता मिला है। यह वापस जाने के लिए एक ही प्रक्रिया होगी।

आइए मान लें कि आप नोड सी से नोड बी तक जा रहे थे। आप अस्थायी चर में नोड सी के पते को स्टोर करेंगे, फिर से ऊपर दी गई प्रक्रिया करें।

नोट: A , B , C जैसे सब कुछ पते हैं। मुझे यह स्पष्ट करने के लिए बतशेबा के लिए धन्यवाद।

एक्सओआर लिंक्ड लिस्ट के नुकसान

  • चूंकि लुंडिन ने उल्लेख किया है, सभी रूपांतरणों को / to uintptr_t से किया जाना है।

  • जैसा कि सामी कुहमोमन ने उल्लेख किया है, आपको केवल एक यादृच्छिक नोड न केवल एक अच्छी तरह परिभाषित प्रारंभ बिंदु से शुरू करना होगा।

  • आप सिर्फ एक नोड कूद नहीं सकते हैं। आपको क्रम में जाना है।

यह भी ध्यान रखें कि ज्यादातर मामलों में एक एक्सओआर लिंक्ड लिस्ट दोगुनी-लिंक्ड सूची से बेहतर नहीं है।

संदर्भ


यह एक पुरानी प्रोग्रामिंग चाल है जो आपको स्मृति को बचाने की अनुमति देती है। मुझे नहीं लगता कि इसका अब और अधिक उपयोग किया जाता है, क्योंकि स्मृति पुराने संसाधनों के रूप में उतना ही तंग नहीं है जितना पुराने दिनों में था।

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

कम-मेमोरी कार्यान्वयन में, आप एक ही मान के साथ "अगला" और "पिछला" प्रतिस्थापित करते हैं, जो "अगली" और "पिछली" की बिटवाई अनन्य-OR (bitwise-XOR) है। इसलिए आप आसन्न तत्व पॉइंटर्स के लिए एक आधा तक भंडारण को कम करते हैं।

इस तकनीक का उपयोग करके, किसी भी दिशा में सूची को पार करना अभी भी संभव है, लेकिन ऐसा करने के लिए आपको पिछले (या अगले) तत्व का पता जानना होगा। उदाहरण के लिए, यदि आप आगे की दिशा में सूची को घुमा रहे हैं, और आपके पास "पिछला" का पता है, तो आप वर्तमान संयुक्त सूचक मूल्य के साथ "पिछला" के bitwise-XOR को ले कर "अगला" प्राप्त कर सकते हैं, जो कि है "पिछला" एक्सओआर "अगला"। नतीजा "पिछला" एक्सओआर "पिछला" एक्सओआर "अगला" है, जो सिर्फ "अगला" है। विपरीत दिशा में भी किया जा सकता है।

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

दूसरा नकारात्मक यह है कि इस प्रकार की पॉइंटर चाल सामान्य डेटा प्रकार की जांच तंत्र को रोकती है जो एक कंपाइलर की उम्मीद कर सकती है।

यह एक चालाक चाल है, लेकिन सभी ईमानदारी में मुझे इन दिनों इसका उपयोग करने के बहुत कम कारण दिखाई देते हैं।





mem.-efficient-linkedlist