सॉर्टेडलिस्ट और सॉर्टेड डिक्शनरी के बीच क्या अंतर है?

Question

क्या SortedList<TKey,TValue> और SortedDictionary<TKey,TValue> के बीच कोई वास्तविक व्यावहारिक अंतर है? क्या ऐसी कोई परिस्थितियां हैं जहां आप विशेष रूप से एक का उपयोग करेंगे, न कि दूसरे?

Answer 1

हां - उनकी प्रदर्शन विशेषताओं में काफी भिन्नता है। शायद उन्हें SortedList और SortedTree पर कॉल करना बेहतर होगा क्योंकि यह कार्यान्वयन को अधिक बारीकी से दर्शाता है।

विभिन्न बैठकों में विभिन्न संचालन के प्रदर्शन के विवरण के लिए उनमें से प्रत्येक के लिए एमएसडीएन दस्तावेज़ (SortedList, SortedDictionary) देखें। यहाँ एक अच्छा सारांश (SortedDictionary डॉक्स से) है:

SortedDictionary<TKey, TValue> सामान्य वर्ग हे (लॉग एन) पुनः प्राप्ति, जहां n शब्दकोश में तत्वों की संख्या है के साथ एक द्विआधारी खोज वृक्ष है। इसमें, यह SortedList<TKey, TValue> जेनेरिक कक्षा के समान है। दोनों वर्गों में ऑब्जेक्ट मॉडल समान हैं, और दोनों में ओ (लॉग एन) पुनर्प्राप्ति है। कहाँ दो वर्गों अलग स्मृति उपयोग में है और प्रविष्टि की गति और हटाने:

• SortedList<TKey, TValue>SortedDictionary<TKey, TValue> से कम स्मृति का उपयोग करता है।

• SortedDictionary<TKey, TValue> तेजी से प्रविष्टि और हटाने अवर्गीकृत डेटा के लिए कार्य किया है, हे (लॉग एन) रूप SortedList<TKey, TValue> के लिए हे (एन) के लिए विरोध किया।

• सूची क्रमबद्ध डेटा से सभी को एक बार से भर जाता है, तो SortedList<TKey, TValue> तेजी से SortedDictionary<TKey, TValue> है।

(SortedList वास्तव में नहीं बल्कि एक पेड़ का उपयोग करने से, एक क्रमबद्ध सरणी का कहना है यह अभी भी तत्व को खोजने के लिए द्विआधारी खोज का उपयोग करता है।।)

Answer 2

बाहर चेक MSDN page for SortedList:

टिप्पणी अनुभाग से:

SortedList<(Of <(TKey, TValue>)>) सामान्य वर्ग, O(log n) पुनः प्राप्ति के साथ एक द्विआधारी खोज वृक्ष है जहां n शब्दकोश में तत्वों की संख्या है। इसमें, यह SortedDictionary<(Of <(TKey, TValue>)>) जेनेरिक वर्ग के समान है। दोनों वर्गों में समान ऑब्जेक्ट मॉडल होते हैं, और दोनों में O(log n) पुनर्प्राप्ति होती है। कहाँ दो वर्गों अलग स्मृति का उपयोग करें और प्रविष्टि और हटाने की गति में है:

• SortedList<(Of <(TKey, TValue>)>)SortedDictionary<(Of <(TKey, TValue>)>) से कम स्मृति का उपयोग करता है।

• SortedDictionary<(Of <(TKey, TValue>)>) के लिए O(n) के विपरीत, O(log n) के बिना निरंतर डेटा, O(log n) के लिए तेजी से सम्मिलन और निष्कासन संचालन है।

• यदि सूची क्रमबद्ध डेटा से एक बार में पॉप्युलेट की जाती है, तो SortedList<(Of <(TKey, TValue>)>)SortedDictionary<(Of <(TKey, TValue>)>) से तेज़ है।

Answer 3

मैं खुले परावर्तक फटा के रूप में वहाँ SortedList के बारे में भ्रम का एक सा प्रतीत हो रहा है इस पर एक नज़र है करने के लिए। यह वास्तव में एक द्विआधारी खोज पेड़ नहीं है, यह कुंजी-मूल्य जोड़े की एक क्रमबद्ध (कुंजी द्वारा) सरणी है। TKey[] keys वैरिएबल भी है जो कुंजी-मूल्य जोड़े के साथ सिंक में क्रमबद्ध है और बाइनरी खोज के लिए उपयोग किया जाता है।

यहाँ कुछ स्रोत मेरी दावों बैकअप के लिए (.NET 4.5 को लक्षित करना) है।

निजी सदस्यों

// Fields 
private const int _defaultCapacity = 4; 
private int _size; 
[NonSerialized] 
private object _syncRoot; 
private IComparer<TKey> comparer; 
private static TKey[] emptyKeys; 
private static TValue[] emptyValues; 
private KeyList<TKey, TValue> keyList; 
private TKey[] keys; 
private const int MaxArrayLength = 0x7fefffff; 
private ValueList<TKey, TValue> valueList; 
private TValue[] values; 
private int version; 

SortedList.ctor (IDictionary, IComparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer) 
{ 
    if (dictionary == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 
    } 
    dictionary.Keys.CopyTo(this.keys, 0); 
    dictionary.Values.CopyTo(this.values, 0); 
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer); 
    this._size = dictionary.Count; 
} 

SortedList.Add (TKey, TValue): शून्य

public void Add(TKey key, TValue value) 
{ 
    if (key == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 
    } 
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer); 
    if (num >= 0) 
    { 
     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); 
    } 
    this.Insert(~num, key, value); 
} 

SortedList.RemoveAt (int): शून्य

public void RemoveAt(int index) 
{ 
    if ((index < 0) || (index >= this._size)) 
    { 
     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); 
    } 
    this._size--; 
    if (index < this._size) 
    { 
     Array.Copy(this.keys, index + 1, this.keys, index, this._size - index); 
     Array.Copy(this.values, index + 1, this.values, index, this._size - index); 
    } 
    this.keys[this._size] = default(TKey); 
    this.values[this._size] = default(TValue); 
    this.version++; 
} 

Answer 4

यहाँ एक सारणीबद्ध दृश्य है अगर यह मदद करता है ...

एक प्रदर्शन परिप्रेक्ष्य से:

+------------------+---------+----------+--------+----------+----------+---------+ 
| Collection  | Indexed | Keyed | Value | Addition | Removal | Memory | 
|     | lookup | lookup | lookup |   |   |   | 
+------------------+---------+----------+--------+----------+----------+---------+ 
| SortedList  | O(1) | O(log n) | O(n) | O(n)* | O(n)  | Lesser | 
| SortedDictionary | n/a  | O(log n) | O(n) | O(log n) | O(log n) | Greater | 
+------------------+---------+----------+--------+----------+----------+---------+ 

* Insertion is O(1) for data that are already in sort order, so that each 
    element is added to the end of the list (assuming no resize is required). 

एक से कार्यान्वयन परिप्रेक्ष्य:

+------------+---------------+----------+------------+------------+------------------+ 
| Underlying | Lookup  | Ordering | Contiguous | Data  | Exposes Key & | 
| structure | strategy  |   | storage | access  | Value collection | 
+------------+---------------+----------+------------+------------+------------------+ 
| 2 arrays | Binary search | Sorted | Yes  | Key, Index | Yes    | 
| BST  | Binary search | Sorted | No   | Key  | Yes    | 
+------------+---------------+----------+------------+------------+------------------+ 

लगभग पैराफ्रेज, यदि आपको कच्चे प्रदर्शन की आवश्यकता है SortedDictionary बेहतर विकल्प हो सकता है। यदि आपको कम मेमोरी ओवरहेड और अनुक्रमित पुनर्प्राप्ति की आवश्यकता है SortedList बेहतर फिट बैठता है। See this question for more on when to use which.

आप अधिक here, here, here, here और here पढ़ सकते हैं।

Answer 5

यह कैसे प्रदर्शन दूसरे से तुलना के दृश्य प्रतिनिधित्व है।

Answer 6

सूचकांक एक्सेस (यहाँ उल्लेख) व्यावहारिक अंतर है। यदि आपको उत्तराधिकारी या पूर्ववर्ती तक पहुंचने की आवश्यकता है, तो आपको सॉर्टेडलिस्ट की आवश्यकता है। SortedDictionary ऐसा नहीं कर सकता है ताकि आप सॉर्टिंग (प्रथम/foreach) का उपयोग कैसे कर सकें।

Answer 7

पर्याप्त रूप से इस विषय पर पर्याप्त कहा जाता है, हालांकि इसे सरल रखना, यहां मेरा लेना है।

छाँटे शब्दकोश इस्तेमाल किया जाना चाहिए when-

• अधिक आवेषण और संचालन हटाना आवश्यक हैं।
• अन-आदेश में डेटा।
• कुंजी का उपयोग करने के लिए पर्याप्त है और सूचकांक का उपयोग की आवश्यकता नहीं है।
• मेमोरी अड़चन नहीं है।

दूसरी ओर, सॉर्ट की गई सूची इस्तेमाल किया जाना चाहिए when-

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

आशा इस मदद करता है !!