SortedList<>, SortedDictionary<> and Diction

问题:

I find that SortedList<TKey, TValue> SortedDictionary<TKey, TValue> and Dictionary<TKey, TValue> implement the same interfaces.

1. When should we opt for SortedList and SortedDictionary over Dictionary?
2. What is the difference between SortedList and SortedDictionary in terms of application?

回答1:

1. When iterating over the elements in either of the two, the elements will be sorted. Not so with Dictionary<T,V>.

2. MSDN addresses the difference between SortedList<T,V> and SortedDictionary<T,V>:

The SortedDictionary(TKey, TValue) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList(TKey, TValue) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey, TValue).

SortedDictionary(TKey, TValue) has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList(TKey, TValue).

If the list is populated all at once from sorted data, SortedList(TKey, TValue) is faster than SortedDictionary(TKey, TValue).

回答2:

I'd mention difference between dictionaries.

Above picture shows that Dictionary<K,V> is equal or faster in every case than Sorted analog, but if order of elements is required, e.g. to print them, Sorted one is chosen.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

回答3:

To summarize the results of a Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, the results from best to worst for different scenarios:

Memory Usage:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Insertions:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Search Operations:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

foreach loop operations

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

回答4:

1. When you want the collection to be sorted by key when you iterate over it. If you don't need your data to be sorted, you're better off with just a Dictionary, it'll have better performance.

2. SortedList and SortedDictionary pretty much do the same thing, but are implemented differently, thus have different strengths and weaknesses explained here.

回答5:

Trying to assign a performance score to each case presented by @Lev, I used the following values:

• O(1) = 3
• O(log n) = 2
• O(n) = 1
• O(1) or O(n) = 2
• O(log n) or O(n) = 1.5

The results are (higher = better):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Of course, every use-case will give more weight to certain operations.