2013-04-17 12 views
6

शीर्षक में। मुझे पता है कि यह हटाए गए सामानों से पहले और बाद में 2 उपन्यासियों को विलीन कर देता है, लेकिन आखिरी तत्वों को हटाते समय यह विधि कैसे व्यवहार करती है? दूसरे शब्दों में: क्या यह किसी भी तरह इंडेक्स को हटाने से पहले स्थित सभी तत्वों की प्रति बना देता है? मैं सिर्फ एक विशाल सूची (निकालें 5000 तत्वों) पर निकालेंगे का उपयोग करने के perfomance के बारे में उत्सुक हूँ f.e. को हटाने के लिए। उनमें से केवल अंतिम 2।RemoveRange() विधि सूची <> में कैसे काम करता है?

यदि यह एक प्रतिलिपि बनाता है, तो क्या कुछ आंतरिक चर बदलने के लिए एक तरीका है जो सूची का आकार निर्धारित करता है (और बाकी आवंटित तत्वों को कचरा के रूप में मानता है)?

मुझे केवल एक जानकारी मिल गई, यह एक ओ (एन) जटिलता एल्गोरिदम है, लेकिन मुझे यकीन नहीं है कि उस मामले में "एन" एक सूची आकार है, या हटाने के लिए कई आइटम हैं।

किसी भी संकेत के लिए खुश होंगे।

+0

http://msdn.microsoft.com/en-gb/library/y33yd2b5.aspx "यह विधि एक ओ (एन) ऑपरेशन है, जहां एन गणना है।" "आइटम हटा दिए गए हैं और सूची में उनके बाद के सभी तत्वों की गणना उनकी इंडेक्स गिनती से कम हो गई है।" http://geekswithblogs.net/BlackRabbitCoder/archive/2012/02/23/c.net-little-wondersndashthe-listlttgt-range-methods.aspx "जागरूक रहें कि इससे शेष सूची को स्थानांतरित करने की आवश्यकता होती है अंतर को भरें, जो गैर-तुच्छ हो सकता है।हालांकि, इसे सूची के पुनर्वितरण की आवश्यकता नहीं होगी क्योंकि आकार संभावित रूप से घट रहा है, बढ़ रहा है। " –

+1

आपको लगता है कि गिनती को हटाने की संख्या है। दस की सूची से 2 को हटाने से वही समय लगेगा एक लाख से 2 को हटा रहा है। यदि आप प्रलेखन में गिनती पर क्लिक करते हैं तो यह सूची गणना को लिंक करता है। – Paparazzi

+1

@Blam यह सच नहीं है, जब तक आप सूची के अंत से हटा नहीं रहे हैं। अगर आप सूची की शुरुआत से हटा रहे हैं तो यह दो वस्तुओं द्वारा स्मृति में 8 आइटमों को स्थानांतरित करने के बीच अंतर है, दो वस्तुओं द्वारा स्मृति में 1, 999,998 आइटमों को स्थानांतरित कर रहा है। वे दोनों बराबर नहीं होंगे। – Servy

उत्तर

10

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

उदाहरण के लिए, निम्न सूची पर विचार करें:

index - value 

0 - A 
1 - B 
2 - C 
3 - D 
4 - E 
5 - F 
6 - G

अगर हम RemoveRange(2, 2) फिर हम सूचकांक 2 से शुरू दो आइटम निकाल रहे हैं फोन, इसलिए हम सी निकाल रहे हैं और डी

यह मतलब ई को इंडेक्स 2 में कॉपी करने की जरूरत है, फिर एफ को इंडेक्स 3 में कॉपी करने की जरूरत है, और जी को इंडेक्स 4 में कॉपी करने की जरूरत है। अंतिम आइटम को हटाए जाने के बाद प्रत्येक आइटम के लिए एक कॉपी ऑपरेशन है।

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

+0

वही है जो मैं जानना चाहता था, धन्यवाद। – Tarec

13

List<T> नीचे दिए गए कोड में _items नामक एक सरणी के चारों ओर एक रैपर है। सूची में आइटमों की तुलना में सरणी में अधिक स्लॉट हो सकते हैं, इसलिए _size का उपयोग यह ट्रैक रखने के लिए किया जाता है कि वास्तव में कितने मान्य हैं। आप अब खाली अंतरिक्ष में सीमा अतीत से एक RemoveRange(index, count) ...

_size -= count; 
if (index < _size) 
    Array.Copy(_items, index + count, _items, index, _size - index); 
Array.Clear(_items, _size, count); 

... यह प्रतियां आइटम करते हैं, और पुराने आइटम हटाती है।

यदि आप बड़ी सूची की शुरुआत के करीब एक सीमा को हटा रहे हैं तो लागत सूची के आकार के समान है, क्योंकि बहुत सारी चीज़ें नीचे लेनी होंगी।

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

+1

क्या आप कृपया थोड़ा गहराई से जा सकते हैं कि क्यों दूसरे मामले में समाशोधन महंगा है? जैसा कि मैंने समझा है कि हमें सरणी के केवल प्रभावित तत्वों को साफ़ करना होगा, जो बड़ी सूची के मामले में '_size' या' _items.Length' जितनी बड़ी नहीं है। उदाहरण के लिए यदि आप शुरुआत के करीब या अंत के पास बड़ी सूची में छोटी सी सीमा को हटा रहे हैं। –

+0

क्या इसका मतलब है कि मुझे 'लिंक्डलिस्ट ' का उपयोग करना चाहिए यदि मुझे पता है कि सूची बड़ी होगी और मैं बाद में आइटम को हटाना चाहूंगा? – Jodrell

+2

@ जोड्रेल शायद नहीं। एक लिंक्ड सूची का उपयोग करते समय स्मृति इलाके के नुकसान का परिणाम बहुत खराब प्रदर्शन में होता है, यहां तक ​​कि लिंक किए गए सूची को पुन: सक्रिय करने जैसे सरल कार्यों के लिए भी। हालांकि इसके कई संचालन के बिग ओ मूल्य कम हैं, लेकिन अधिकांश व्यावहारिक मामलों में लिंक्ड सूचियों के लिए यह असामान्य है। – Servy

संबंधित मुद्दे