SortedList<>, SortedDictionary<> and Dictionary<>
C#GenericsDictionarySortedlistSorteddictionaryC# Problem Overview
I find that SortedList<TKey, TValue>
SortedDictionary<TKey, TValue>
and Dictionary<TKey, TValue>
implement the same interfaces.
- When should we opt for
SortedList
andSortedDictionary
overDictionary
? - What is the difference between
SortedList
andSortedDictionary
in terms of application?
C# Solutions
Solution 1 - C#
-
When iterating over the elements in either of the two, the elements will be sorted. Not so with
Dictionary<T,V>
. -
MSDN addresses the difference between
SortedList<T,V>
andSortedDictionary<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).
Solution 2 - C#
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.
Solution 3 - C#
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>
Solution 4 - C#
I can see the proposed answers focus on performance. The article provided below does not provide anything new regarding performance, but it explains the underlying mechanisms. Also note it does not focus on the three Collection
Types mentioned in the question, but addresses all the Types of the System.Collections.Generic
namespace.
Extracts:
Dictionary<>
> The Dictionary
SortedDictionary<>
>The SortedDictionary
SortedList<>
>The SortedList
Tentative Summary of underlying Procedures
Feedback is very welcome as I am sure I did not get everything right.
- All arrays are of size
n
. - Non-sorted array = .Add/.Remove is O(1), but .Item(i) is O(n).
- Sorted array = .Add/.Remove is O(n), but .Item(i) is O(log n).
Dictionary
Memory
KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>
Add
- Add
HashArray(n) = Key.GetHash
# O(1) - Add
KeyArray(n) = PointerToKey
# O(1) - Add
ItemArray(n) = PointerToItem
# O(1)
Remove
For i = 0 to n
, findi
whereHashArray(i) = Key.GetHash
# O(log n) (sorted array)- Remove
HashArray(i)
# O(n) (sorted array) - Remove
KeyArray(i)
# O(1) - Remove
ItemArray(i)
# O(1)
Get Item
For i = 0 to n
, findi
whereHashArray(i) = Key.GetHash
# O(log n) (sorted array)- Return
ItemArray(i)
Loop Through
For i = 0 to n
, returnItemArray(i)
SortedDictionary
Memory
KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>
Add
- Add
KeyArray(n) = PointerToKey
# O(1) - Add
ItemArray(n) = PointerToItem
# O(1) For i = 0 to n
, findi
whereKeyArray(i-1) < Key < KeyArray(i)
(usingICompare
) # O(n)- Add
OrderArray(i) = n
# O(n) (sorted array)
Remove
For i = 0 to n
, findi
whereKeyArray(i).GetHash = Key.GetHash
# O(n)- Remove
KeyArray(SortArray(i))
# O(n) - Remove
ItemArray(SortArray(i))
# O(n) - Remove
OrderArray(i)
# O(n) (sorted array)
Get Item
For i = 0 to n
, findi
whereKeyArray(i).GetHash = Key.GetHash
# O(n)- Return
ItemArray(i)
Loop Through
For i = 0 to n
, returnItemArray(OrderArray(i))
SortedList
Memory
KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>
Add
For i = 0 to n
, findi
whereKeyArray(i-1) < Key < KeyArray(i)
(usingICompare
) # O(log n)- Add
KeyArray(i) = PointerToKey
# O(n) - Add
ItemArray(i) = PointerToItem
# O(n)
Remove
For i = 0 to n
, findi
whereKeyArray(i).GetHash = Key.GetHash
# O(log n)- Remove
KeyArray(i)
# O(n) - Remove
ItemArray(i)
# O(n)
Get Item
For i = 0 to n
, findi
whereKeyArray(i).GetHash = Key.GetHash
# O(log n)- Return
ItemArray(i)
Loop Through
For i = 0 to n
, returnItemArray(i)
Solution 5 - C#
-
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.
-
SortedList and SortedDictionary pretty much do the same thing, but are implemented differently, thus have different strengths and weaknesses explained here.
Solution 6 - C#
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.