सूची है। क्या कोई प्रदर्शन जुर्माना है?</p> <pre><code>List<object> SomeList = new List<object>(); </code></pre> <p>कर करता है:</p> <pre><code>SomeList.Insert(i, val); </code></pre> <p>बनाम

Question

एक सूची को देखते हुए

SomeList.Add(val); 

क्या कोई प्रदर्शन जुर्माना है? यदि ऐसा है, यह कैसे पर निर्भर करता है:
- i - प्रविष्टि सूचकांक
- SomeList.Count - सूची

Answer 1

सूची वर्ग के आकार ArrayList वर्ग के सामान्य बराबर है। यह एक सरणी का उपयोग करके आईएलआईएस जेनेरिक इंटरफ़ेस लागू करता है जिसका आकार आवश्यकतानुसार गतिशील रूप से बढ़ाया जाता है।

(source)

मतलब है कि आंतरिक डेटा किसी सरणी के रूप में संग्रहीत किया जाता है, और इसलिए यह है, इस प्रकार इसकी जटिलता संभावना है कि insert यह जगह बनाने के लिए सभी तत्वों पर ले जाने की आवश्यकता होगी प्रदर्शन करने के लिए है ओ (एन) है, जबकि add एक (amortized) निरंतर समय ओ (1) ऑपरेशन है, इसलिए हाँ।

सारांश - हाँ, यह लगभग हमेशा धीमा हो जाएगा, और यह आपकी सूची जितनी बड़ी होगी उतनी धीमी हो जाएगी।

Answer 2

संदेह होने पर, एक अनुभवजन्य प्रयोग करते हैं:

List<object> SomeList = new List<object>(); 

     Stopwatch sw = new Stopwatch(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Insert(0, String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 
     sw.Reset(); 

     SomeList = new List<object>(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Add(String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 

सम्मिलित मेरी मशीन पर 2800ms लेता है; जोड़ 0.8ms लेता है। तो हाँ, सम्मिलन बहुत कम प्रदर्शनकारी है।

Answer 3

बेशक यह करता है।

चूंकि List<T> किसी सरणी द्वारा समर्थित है, सूची की शुरुआत में सम्मिलित करने के लिए किसी भी ऑपरेशन को सरणी के अन्य सभी तत्वों को स्थानांतरित करना (या प्रतिलिपि) करना चाहिए। एक ऑपरेशन जो सूची के अंत में जोड़ता है, सूची में वस्तुओं की संख्या के बावजूद निरंतर समय में होगा।

Answer 4

मेरा पहला विचार था "हाँ, एक प्रदर्शन जुर्माना है क्योंकि Insert को सूची में सभी वस्तुओं को नए आइटम के लिए जगह बनाने के लिए एक स्लॉट स्थानांतरित करने की आवश्यकता है" - लेकिन फिर मैंने सवाल को और सावधानी से पढ़ा। तो:

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

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

बेशक यह सब है क्योंकि आप अपने आशय है क्या जब तक आप एक दस्तावेज प्रदर्शन मुद्दा है पर आधारित विधियों का चयन करना चाहिए तरह का विवादास्पद है।

Answer 5

एक खाली सूची के लिए, यह कोई अलग नहीं है।

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

* जहां AddCapacity को बढ़ाने के लिए कारण बताता है।

Answer 6

मुझे एहसास है कि इसका पहले से ही उत्तर दिया जा चुका है, लेकिन मैं यह इंगित करना चाहता हूं कि यह जानकारी एमएसडीएन दस्तावेज़ीकरण में आसानी से उपलब्ध है।

The documentation for List<T>.Insert() कहता है:

इस विधि एक हे (एन) आपरेशन, जहां n गणना है।

The documentation for List<T>.Add() कहता है:

तो गणना क्षमता से कम है, इस विधि एक हे (1) ऑपरेशन है। यदि नए तत्व को समायोजित करने के लिए क्षमता को बढ़ाने की आवश्यकता है, तो यह विधि ओ (एन) ऑपरेशन बन जाती है, जहां एन गणना होती है।

यदि आप ऐसा इस प्रश्न पूछ सकता है, क्योंकि आप एक स्थिति है जहाँ आप को करने के लिए बार-बार एक सूची के सामने और वापस करने के लिए कहते हैं, तो उपयोग करने के लिए उपयुक्त डेटा संरचना एक Deque है चाहते हैं।

Stephen Cleary एक अच्छा Deque कार्यान्वयन यहां प्रदान की गई है: http://nitodeque.codeplex.com/