का अमूर्त विश्लेषण हम std :: vector में पीछे (push_back) पर सम्मिलन का विश्लेषण कैसे करते हैं? यह अमूर्त समय है ओ (1) प्रति प्रविष्टि। विशेष रूप से video in channel9 by Stephan T Lavavej और in this (17:42 onwards) में वह कहता है कि इष्टतम प्रदर्शन के लिए माइक्रोसॉफ्ट के इस विधि के कार्यान्वयन में वेक्टर की क्षमता लगभग 1.5 तक बढ़ जाती है।std :: वेक्टर सम्मिलन
यह निरंतर निर्धारित कैसे किया जाता है?
मान लें कि आपका मतलब push_back है और सम्मिलन नहीं है, मेरा मानना है कि महत्वपूर्ण हिस्सा कुछ स्थिरांक (जैसे हर बार एन तत्वों को हथियाने के विरोध में) गुणा करता है और जब तक आप ऐसा करते हैं तो आपको निरंतर समय मिल जाएगा। कारक बदलने से औसत केस और सबसे खराब केस प्रदर्शन बदल जाता है।
कंक्रीटली: यदि आपका निरंतर कारक बहुत बड़ा है, तो आपके पास औसत औसत प्रदर्शन प्रदर्शन होगा, लेकिन खराब सबसे खराब केस प्रदर्शन विशेष रूप से सरणी बड़े हो जाते हैं। उदाहरण के लिए, एक 10000 आकार वेक्टर को दोगुनी (2x) की कल्पना करें क्योंकि आपके पास 10001 वें तत्व धक्का दिया गया है। संपादित करें: जैसा कि माइकल बोर अप्रत्यक्ष रूप से इंगित करते हैं, यहां वास्तविक लागत शायद यह है कि आप अपनी याददाश्त को जितना बड़ा होना चाहते हैं उससे कहीं अधिक बड़े हो जाएंगे। मैं इसमें जोड़ दूंगा कि कैश मुद्दे हैं जो गति को प्रभावित करते हैं यदि आपका कारक बहुत बड़ा है। यह कहने के लिए पर्याप्त है कि यदि आप की जरूरत से ज्यादा बड़ा हो तो वास्तविक लागत (स्मृति और गणना) हैं।
हालांकि यदि आपका निरंतर कारक बहुत छोटा है, तो कहें (1.1x) तो आपको सबसे खराब केस प्रदर्शन होगा, लेकिन खराब औसत प्रदर्शन होगा, क्योंकि आपको बहुत से लोगों को फिर से चलाने की लागत लगानी होगी बार।
Also, see Jon Skeet's answer to a similar question previously. (धन्यवाद @Bo पेरसन)
विश्लेषण के बारे में एक छोटे से अधिक: आप n आइटम तुम वापस दे रहे हैं और M के गुणन कारक है कहो। फिर पुनर्वितरण की संख्या n (log_M(n)) के लगभग M लॉग आधार होगी। और i वें पुनर्वितरण M^i (Mi वें शक्ति के अनुपात के समान आनुपातिक होगा)। फिर सभी pushbacks का कुल समय M^1 + M^2 + ... M^(log_M(n)) होगा। पुशबैक की संख्या n है, और इस प्रकार आपको यह श्रृंखला मिलती है (जो एक ज्यामितीय श्रृंखला है, और सीमा में लगभग (nM)/(M-1) तक कम हो जाती है) n द्वारा विभाजित। यह लगभग स्थिर है, M/(M-1)।
M के बड़े मूल्यों के लिए आप बहुत अधिक ओवरशूट करेंगे और आपको उचित रूप से अक्सर (जो मैंने ऊपर वर्णित किया है) से अधिक आवंटित करेंगे। M (1 के करीब) के छोटे मानों के लिए यह स्थिर M/(M-1) बड़ा हो जाता है। यह कारक सीधे औसत समय को प्रभावित करता है।
10000 तत्व वेक्टर के साथ आवंटन को दोगुना क्यों करना एक नया ब्लॉक आवंटित करने से भी बदतर है जो कुछ अन्य तत्वों (10000 से अधिक) रखेगा? –
हाँ का मतलब पीछे की ओर घुसपैठ था ... प्रश्न संपादित किया है .. – jemmanuel
तो आप कह रहे हैं कि कारक होने के साथ वास्तविक समस्या यह है कि आप बहुत अधिक स्मृति को हॉग करेंगे? या क्या मैं इस बिंदु को याद कर रहा हूं? आप सही हैं, वास्तविक लागत शायद प्रतिलिपि के बाद होती है जो प्रतिलिपि के बाद होती है। –
उम, विश्लेषण वास्तव में सरल है जब आप संख्या प्रणाली से परिचित हैं, जैसे कि हमारे सामान्य दशमलव एक।
सादगी के लिए, मान लीजिए कि प्रत्येक बार वर्तमान क्षमता तक पहुंचने पर, एक नया 10x बड़ा बफर आवंटित किया जाता है।
यदि मूल बफर आकार 1 है, तो पहला पुनर्विक्रय 1 तत्व प्रतिलिपि बनाता है, दूसरा (जहां अब बफर आकार 10 है) 10 तत्वों की प्रतिलिपि बनाता है, और इसी तरह। तो पांच पुनर्विक्रय के साथ, कहें, आपके पास 1 + 10 + 100 + 1000 + 10000 = 11111 तत्व प्रतियां हैं। 9 से गुणा करें, और आपको 99 999 मिलते हैं; अब 1 जोड़ें और आपके पास 100000 = 10^5 है। या दूसरे शब्दों में, पीछे की ओर, उन 5 पुनर्वितरणों का समर्थन करने के लिए किए गए तत्व प्रतियों की संख्या (10^5-1)/9 रही है।
और 5 पुनर्विक्रय के बाद बफर आकार, 10 गुणा 10, 10^5 है। जो तत्व प्रतिलिपि संचालन की संख्या से लगभग 9 का एक कारक है। जिसका अर्थ यह है कि प्रतिलिपि पर बिताए गए समय परिणामी बफर आकार में मोटे तौर पर रैखिक हैं।
10 के बजाय बेस 2 के साथ आपको (2^5-1)/1 = 2^5-1 मिलता है।
और अन्य अड्डों के लिए (या बफर आकार को बढ़ाने के लिए कारक) पर।
चीयर्स & एचएचटी।
आप इस तरह की चीज कैसे काम करते हैं यह समझने के लिए गणित कर सकते हैं।
एसिम्प्टोटिक विश्लेषण के साथ काम करने के लिए एक लोकप्रिय विधि बैंकर विधि है। आप जो भी करते हैं, वह आपके सभी परिचालनों को एक अतिरिक्त लागत के साथ मार्कअप करता है, बाद में एक महंगे ऑपरेशन के लिए भुगतान करने के लिए इसे "बचत" करता है।
चलो कुछ डंप मान्यताओं गणित आसान बनाने के लिए करते हैं:
1 में लेखन। (सरणी के बीच डालने और आगे बढ़ने के लिए)function insert(x){
if n_elements >= maximum array size:
move all elements to a new array that
is K times larger than the current size
add x to array
n_elements += 1
जाहिर है, "सबसे खराब स्थिति" होता है हम नई सरणी के तत्वों को स्थानांतरित करने के लिए है जब:
और हमारे एल्गोरिथ्म तरह दिखता है। आइए सम्मिलन लागत में d का निरंतर मार्कअप जोड़कर इसे संशोधित करने का प्रयास करें, इसे प्रति ऑपरेशन के कुल (1 + d) पर लाएं।
एक सरणी का आकार बदलने के बाद, हमारे पास (1/के) भर गया है और कोई पैसा बचाया नहीं गया है। जब तक हम सरणी को भरते हैं, हम सुनिश्चित कर सकते हैं कि कम से कम d * (1 - 1/K) * N सहेजा गया हो। चूंकि यह पैसा ले जाया जा रहा सब एन तत्वों के लिए भुगतान करने के लिए सक्षम होना चाहिए, हम K और d के बीच एक रिश्ता यह पता लगाने कर सकते हैं:
d*(1 - 1/K)*N = N
d*(K-1)/K = 1
d = K/(K-1)
एक सहायक तालिका:
k d 1+d(total insertion cost)
1.0 inf inf
1.1 11.0 12.0
1.5 3.0 4.0
2.0 2.0 3.0
3.0 1.5 2.5
4.0 1.3 2.3
inf 1.0 2.0
तो आप इस समस्या के लिए समय/मेमोरी ट्रेडऑफ कैसे काम करते हैं, इस बारे में एक मोटा गणितज्ञ का विचार प्राप्त कर सकते हैं। कुछ चेतावनी हैं, ज़ाहिर है: जब मैं कम तत्व प्राप्त करता हूं तो सरणी को कम करने पर नहीं जाता था, यह केवल सबसे बुरे मामले को कवर करता है जहां कोई तत्व कभी नहीं हटाया जाता है और अतिरिक्त मेमोरी आवंटित करने की समय लागत के लिए जिम्मेदार नहीं था।
वे संभवतः अंत में इसे समझने के लिए प्रयोगात्मक परीक्षणों का एक समूह चलाते हैं जो मैंने अप्रासंगिक लिखा है।
क्या आप वाकई * सम्मिलन * का मतलब रखते हैं? मुझे लगता है कि अंत में * प्रविष्टि *, या 'push_back', केवल am (1) amortized है; मनमाने ढंग से सम्मिलन उन तत्वों की संख्या में रैखिक है जिन्हें स्थानांतरित करने की आवश्यकता है। –
ओह, मुझे इसके बारे में संदेह था कि इसका उल्लेख करने के लिए धन्यवाद ... इसे संपादित करेगा – jemmanuel
पृथ्वी पर क्यों लोग "ऑफ-विषय" और "गैर-रचनात्मक" के रूप में बंद होने के लिए मतदान कर रहे हैं?"डुप्लिकेट" के रूप में बंद करने के लिए वोटिंग समझा जा सकता है, लेकिन दिए गए कारण नहीं। संभावित मतदाता: जब आप कोई प्रश्न नहीं समझते हैं, तो कृपया मतदान से बचें। –