ऐरे-आधारित बनाम सूची-आधारित ढेर और कतार

Question

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

विशेष रूप से, मैं push() और दोनों कतारों और ढेर के लिए pop(), दोनों सरणियों और लिंक की गई सूची (इस प्रकार 2 आपरेशन एक्स 2 संरचनाओं एक्स 2 कार्यान्वयन, या 8 मान) के रूप में लागू की तुलना करने के लिए देख रहा हूँ।

इसके अतिरिक्त, मैं इनमें से दोनों के लिए सर्वोत्तम, औसत और सबसे खराब केस मानों की सराहना करता हूं, और जो कुछ भी वे उपभोग करते हैं उससे संबंधित कुछ भी।

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

मैं सिर्फ यह निर्धारित करने का एक तरीका ढूंढ रहा हूं कि मुझे कहां और कहाँ एक सरणी आधारित कार्यान्वयन का उपयोग करना चाहिए, दोनों स्टैक्स और कतारों के लिए एक सूची-आधारित कार्यान्वयन बनाम।

Answer 1

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

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

एक गतिशील सरणी में, हम ओ (1) समय में किसी भी तत्व तक पहुंच सकते हैं। हम amortized O(1) में एक तत्व भी जोड़ सकते हैं, जिसका अर्थ है कि एन सम्मिलन के लिए कुल समय ओ (एन) है, हालांकि किसी भी प्रविष्टि पर वास्तविक समय सीमा बहुत खराब हो सकती है।आम तौर पर, अधिकांश प्रविष्टियां ओ (1) को प्रीलोकेटेड स्पेस में जोड़कर लागू होती हैं, लेकिन सरणी क्षमता को दोगुनी करके तत्वों की प्रतिलिपि बनाकर Θ (एन) समय में प्रविष्टियों की एक छोटी संख्या चलती है। अतिरिक्त जगह आवंटित करके और तत्वों की आलसी प्रतिलिपि बनाकर इसे कम करने की कोशिश करने के लिए तकनीकें हैं (उदाहरण के लिए this data structure देखें)। आमतौर पर, एक गतिशील सरणी का स्मृति उपयोग काफी अच्छा होता है - जब सरणी पूरी तरह से पूर्ण होती है, उदाहरण के लिए, केवल ओ (1) अतिरिक्त ओवरहेड होता है - हालांकि सरणी के आकार में दोगुनी हो जाने के ठीक बाद ओ (एन) अप्रयुक्त हो सकता है सरणी में आवंटित तत्व। चूंकि आवंटन कम होते हैं और पहुंच तेजी से होती हैं, गतिशील सरणी आमतौर पर लिंक्ड सूचियों की तुलना में तेज़ी से होती हैं।

अब, चलिए एक लिंक्ड सूची या गतिशील सरणी का उपयोग करके एक स्टैक और कतार को कार्यान्वित करने के बारे में सोचें।

• ढेर: यह करने के लिए कई तरीके हैं, इसलिए मुझे लगता है कि आप निम्नलिखित कार्यान्वयन का उपयोग कर रहे समझेंगे
  • लिंक्ड सूची: एक सिर सूचक के साथ एक singly-linked list के रूप में।
  • सरणी: एक dynamic array
• कतार के रूप में:
  • लिंक्ड सूची: एक सिर और पूंछ सूचक के साथ एक अकेले लिंक्ड सूची के रूप में।
  • ऐरे: circular buffer एक सरणी द्वारा समर्थित।

के बदले में प्रत्येक पर विचार करें।

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

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

कतार एक सिंगल-लिंक्ड सूची द्वारा समर्थित है। लिंक्ड लिस्ट में प्रवेश करना एकल-लिंक्ड सूची के पीछे संलग्न करके कार्यान्वित किया जा सकता है, जो सबसे खराब समय का समय ओ (1) लेता है। पहले तत्व को हटाकर Dequeuing लागू किया जा सकता है, जो सबसे खराब मामले समय ओ (1) भी लेता है। इसके लिए प्रति एनक्यूयू के लिए एक नया आवंटन भी आवश्यक है, जो धीमा हो सकता है।

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

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

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

आशा है कि इससे मदद मिलती है!

Answer 2

क्षमा करें अगर मैंने आपके प्रश्न को गलत समझा, लेकिन अगर मैंने नहीं किया, तो मुझे विश्वास है कि यह वह उत्तर है जिसे आप ढूंढ रहे हैं।

वेक्टर के साथ, आप केवल कंटेनर के अंत में तत्वों को कुशलतापूर्वक जोड़/हटा सकते हैं। एक डेक के साथ, आप कंटेनर की शुरुआत/अंत में तत्वों को कुशलतापूर्वक जोड़/हटा सकते हैं। एक सूची के साथ, आप कंटेनर में कहीं भी तत्वों को कुशलता से सम्मिलित/हटा सकते हैं।

वेक्टर/डेक यादृच्छिक अभिगम इटरेटर के लिए अनुमति देते हैं। सूचियों केवल अनुक्रमिक पहुंच की अनुमति देता है।

डेटा का उपयोग करने और स्टोर करने की आपको कैसे आवश्यकता है यह निर्धारित करने के लिए कि आप कौन सा उचित निर्धारित करते हैं।

संपादित करें:

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