एसटीएल की जटिलता Deque :: डालने()

Question

मैं सी ++ मानक 2003 (अध्याय 23.2.1.3) से deque::insert() की जटिलता के रूप में निम्नानुसार सीखा प्रवेश बिंदु से दूरी की न्यूनतम सीमा में डेक की शुरुआत और सम्मिलन बिंदु से दूरी को डेक के अंत तक दूरी में रैखिक।

मैं हमेशा स्मृति खंडों के संग्रह के रूप में एसएलएल डेक के कार्यान्वयन को समझता हूं। इसलिए एक सम्मिलन केवल प्रविष्टि स्थिति के समान स्मृति खंड में तत्वों को प्रभावित करेगा। मेरा सवाल यह है कि, "मानक प्रविष्टि से दूरी की न्यूनतम सीमा में डेक की शुरुआत और प्रविष्टि बिंदु से डेक के अंत तक दूरी" से मानक क्या मतलब है?

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

एक और अनुमान यह हो सकता है कि, insert() सभी इटरेटर्स को अमान्य कर देगा, डेक को सभी इटरेटर अपडेट करने की आवश्यकता है। इसलिए यह रैखिक है।

Answer 1

std :: डेक सामान्य रूप से (हमेशा?) स्मृति के टुकड़ों के संग्रह के रूप में लागू किया जाता है, लेकिन संग्रह के बीच में एक नया तत्व डालने के लिए यह सामान्य रूप से एक नया नया हिस्सा नहीं डालेगा । इस प्रकार, यह पता लगाएगा कि प्रविष्टि बिंदु शुरुआत या अंत के करीब है, और मौजूदा तत्वों को मौजूदा खंड में नए तत्व के लिए जगह बनाने के लिए घुमाएं। यह संग्रह की शुरुआत या अंत में केवल स्मृति का एक नया हिस्सा जोड़ देगा।

Answer 2

डाले गए तत्वों की संख्या (प्रतिलिपि निर्माण) पर रैखिक। इसके अलावा, विशेष लाइब्रेरी कार्यान्वयन के आधार पर, स्थिति के बीच तत्वों की संख्या और डेक के सिरों में से एक में अतिरिक्त रैखिक समय। Reference...

Answer 3

आपका अनुमान ... 99.9% सच है। सभी वास्तविक कार्यान्वयन के आधार पर निर्भर करता है। मानक विनिर्देश दोनों कार्यान्वयनकर्ताओं के लिए न्यूनतम आवश्यकता क्या हैं (जो मानक होने का दावा नहीं कर सकते हैं यदि वे चश्मा फिट करते हैं) और उपयोगकर्ता (जो कार्यान्वयन स्वतंत्र कोड लिखने पर "बेहतर प्रदर्शन" की अपेक्षा नहीं करनी चाहिए)।

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

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

Answer 4

मुझे लगता है कि आपको एक आरेख द्वारा बेहतर सेवा दी जाएगी ... चलो एएससीआईआई कला के साथ खेलते हैं!

एक डेक आमतौर पर स्मृति भाग की एक सरणी होती है, लेकिन सामने और पीछे मेमोरी भाग के अलावा सभी अलग होते हैं।क्योंकि एक Deque एक RandomAccessContainer है, और हे (1) किसी भी कंटेनर तक पहुँच प्राप्त करने के लिए, आप जहाँ से आकार को पढ़ने के लिए कंटेनरों की एक असीम संख्या नहीं हो सकती यह आवश्यक है:

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; } 

T& operator[](size_t i) { 
    if (i < first.size) { return first[SIZE - i]; } 

    size_t const correctedIndex = i - first.size; 
    return buckets[correctedIndex/SIZE][correctedIndex % SIZE]; 
} 

उन संचालन हे हैं (1) गुणा/विभाजन की वजह से!

मेरे उदाहरण में, मुझे लगता है कि 8 तत्वों में एक मेमोरी खंड भरा हुआ है। अभ्यास में, किसी ने भी नहीं कहा कि आकार तय किया जाना चाहिए, बस सभी आंतरिक बाल्टी एक ही आकार के होंगे।

// Deque 
0:  ++ 
1: ++++++++ 
2: ++++++++ 
3: ++++++++ 
4: +++++ 

अब कहते हैं कि हमें सूचकांक 13 में सम्मिलित करना चाहते हैं यह बाल्टी लेबल 2 में कहीं गिर जाता है कई रणनीतियों के बारे में हम सोच सकते हैं कर रहे हैं:

• बाल्टी का विस्तार 2 (केवल)
• से पहले या 2 के बाद ही कुछ तत्वों

लेकिन उन दो रणनीतियों एक नया बाल्टी लागू करने और शफ़ल अपरिवर्तनीय है कि सभी "आंतरिक" बाल्टी में एक ही संख्या है का उल्लंघन होगा तत्वों का बियर

इसलिए हम,, चारों ओर तत्वों फेरबदल के साथ छोड़ दिया जाता है या तो शुरूआत या अंत (जो भी सस्ता है) की ओर हमारे मामले में:

// Deque 
0:  +++ 
1: ++++++++ 
2: +O++++++ 
3: ++++++++ 
4: +++++ 

नोट कैसे बाल्टी 0 की वृद्धि हुई।

यह शफल का अर्थ है कि, सबसे बुरे मामले में, आप आधे तत्वों को स्थानांतरित करेंगे: ओ (एन/2)।

deque ओ (1) या तो शुरुआत या अंत में सम्मिलित है, क्योंकि वहां केवल सही जगह पर तत्व जोड़ने या यदि बाल्टी भर जाती है तो एक नई बाल्टी बना रही है।

ऐसे अन्य कंटेनर हैं जो B+ Trees के आधार पर यादृच्छिक सूचकांक पर बेहतर डालने/मिटाए गए व्यवहार हैं। एक अनुक्रमित बी + ट्री में आप "कुंजी" (या समानांतर में) की बजाय, किसी निश्चित स्थिति से पहले तत्वों की गिनती को बनाए रख सकते हैं। इसे कुशलतापूर्वक करने के लिए विभिन्न तकनीशियन हैं। अंत में आप के साथ एक कंटेनर मिलती है:

• हे (1): खाली, आकार
• हे (लॉग एन): डालने पर, मिटाएं

आप में blist मॉड्यूल की जांच कर सकते हैं पायथन जो ऐसी संरचना द्वारा समर्थित पायथन सूची-जैसी तत्व लागू करता है।