जावा में अनियंत्रित लिंक्ड सूची

सभी को नमस्कार।

समय-समय पर मैं, अधिकांश प्रोग्रामर की तरह, कुछ नई संरचनाएं और एल्गोरिदम सीखता हूं।

इस बार मैं कैश गुमनामी एल्गोरिदम पर लेखों के पार आया। ये एल्गोरिदम हैं जो शुरू में आधुनिक प्रोसेसर के कैशिंग सिस्टम के साथ काम करने के लिए अधिक अनुकूलित हैं।

इस समूह के प्रतिनिधियों में से एक अनियंत्रित लिंक्ड सूची है।

यह क्या है?

यह समझने के लिए कि यह क्या है और इसके साथ क्या खाया जाता है, मैं सबसे लोकप्रिय सूची कार्यान्वयन को याद करने का सुझाव देता हूं: ArrayList (कुछ सरलीकरण के साथ हम सूची के बजाय सरणियों के बारे में बात करेंगे) और LinkedList।

उनके मुख्य लाभों और नुकसानों पर विचार करें:

ArrayList :

गौरव

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

कमियों

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

लिंक्डलिस्ट :

गौरव

• अपेक्षाकृत सरल और तेजी से मध्य डालने का कार्य;
• अत्यधिक खंडित स्मृति के साथ काम करते समय कोई समस्या नहीं होती है।

कमियों

• समान आकार के डेटा (4 गुना तक) के भंडारण के लिए आवश्यक मेमोरी की बड़ी मात्रा;
• जब एक सूची पर पुनरावृत्ति होती है, तो सबसे खराब स्थिति में कैश मिस की संख्या सूची नोड्स की संख्या के बराबर हो सकती है। यहां तक ​​कि सबसे अच्छे मामले में, जब सभी नोड्स एक के बाद एक मेमोरी में होते हैं, तो नोड्स के बड़े आकार के कारण, कैश मिस की संख्या ArrayList की तुलना में कई गुना बड़ी होगी।

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

सीधे शब्दों में कहा जाए तो UnrolledLinkedList लंबाई n के सरणियों से जुड़ी (डबल कनेक्टेड) ​​सूची है। यही है, प्रत्येक नोड में एक मान नहीं है, लेकिन एक मान है। इसी समय, सरणी काफी छोटा है ताकि डालने और हटाने के संचालन बहुत तेज हो और मेमोरी विखंडन में नोड्स बनाने की क्षमता पर कम प्रभाव पड़ता है, लेकिन कैश मिस की संख्या को कम करने के लिए पूरी तरह से कैश लाइन में फिट होने के लिए पर्याप्त है। इसके अतिरिक्त, प्रत्येक नोड इसमें जोड़े गए तत्वों की संख्या को संग्रहीत करता है। आलेखीय रूप से, इस सूची को निम्नानुसार दर्शाया जा सकता है:



इस सूची के संचालन पर विचार करें:

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

आलेखीय रूप से, इस ऑपरेशन को निम्नानुसार दर्शाया जा सकता है:



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

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

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

कैश मिस की संख्या के बारे में बोलते हुए, जब इस तरह की सूची के बारे में पता चलता है, तो इसका अनुमान लगाया जा सकता है (एन / एन + 1) (एन / बी), जहां एन सूची की लंबाई है, एन नोड सरणी की लंबाई है, बी कैश लाइन की लंबाई है। यह अनुमान ArrayList के लिए अनुमान के काफी करीब है।

लेखन के समय, मुझे यह भी विचार था कि इस तरह की सूची केवल एक नोड को लॉक करने की क्षमता के साथ समवर्ती संग्रह का एक काफी प्रभावी कार्यान्वयन हो सकती है। हालांकि, यह एक नए अध्ययन और एक नए लेख के लिए एक विषय है।

सूत्र जिठुब पर तैनात हैं।
वे एक क्रूड कोड हैं, इसलिए कृपया गुणवत्ता के लिए बहुत मुश्किल न करें। हालाँकि, किसी भी मामले में, मैं किसी भी आलोचना का आभारी रहूंगा।

विभिन्न सूचियों को मापने और उनकी तुलना करने के लिए स्रोतों में कुछ प्रयास हैं, हालांकि, मैं उन्हें लेख में प्रस्तुत करने में शर्मिंदा हूं, क्योंकि मुझे बहुत यकीन नहीं है कि सभी माप सही तरीके से किए गए थे और मैंने पैर में खुद को गोली नहीं मारी थी। सूचियों पर बिंदुओं के अंतिम स्थान के लिए बेंचमार्किंग विशेषज्ञों की मदद से मुझे बहुत खुशी होगी!

आपका ध्यान देने के लिए धन्यवाद।

सूत्रों का कहना है:
blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx
en.wikipedia.org/wiki/Unrolled_linked_list

UPD: अभी भी प्रदर्शन और आकार की माप के लिए मिला है। Microbenchmarking के लिए मैंने google-tool कैलिपर का उपयोग किया।
यहाँ परिणाम हैं:
रैखिक पुनरावृत्ति
लंबाई बेंचमार्क हमें रैखिक क्रम
1000 अनियंत्रित सूची 6.34 =
1000 ArrayListIteration 5.56 =
1000 लिंक्डलीस्टेरियेशन 5.93 =
100000 अनियंत्रित सूची 827.68 ==
100000 ArrayListIteration 637.05 =
100000 लिंक्डलीस्टेरियेशन 1124.38 ==
1000000 अनियंत्रित सूची 9056.77 ==========================
1000000 ArrayListIteration 6731.73 ==================
१००,००० लिंक्डलिस्टेरियेशन ११.9००.९ ६ ===================================

रैंडम एक्सेस:
लंबाई बेंचमार्क हमें रैखिक क्रम
1000 अनियंत्रित सूची 6.34 =
1000 ArrayListIteration 5.53 =
1000 लिंक्डलिस्ट 5 5.97 =
100000 अनियंत्रित सूची 844.30 ==
100000 ArrayListIteration 652.21 =
100000 लिंक्डलीस्टेरिएशन 1106.90 ===
1000000 अनियंत्रित सूची 9066.88 =============================
1000000 ArrayListIteration 6723.21 ======================
1,000,000 लिंक्डलिस्ट 10,339.15 =====================================

का आकार:
एक ArrayList का औसत आकार 45172432,000 बाइट्स // काफी ईमानदार परिणाम नहीं है, लेकिन मात्रा में क्रमिक वृद्धि के साथ स्मृति की खपत का संकेत है।
1KK के साथ एक ArrayList का औसत आकार 24000064,000 बाइट्स है
एक अनरोलडलिस्ट में एक बिट का औसत आकार 26250048,000 बाइट्स है
एक लिंक्डलिस्ट में एक बिट का औसत आकार 56000048,000 बाइट्स है

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