What's the Difference Between Sortedlist and Sorteddictionary

What's the difference between SortedList and SortedDictionary?

Yes - their performance characteristics differ significantly. It would probably be better to call them SortedList and SortedTree as that reflects the implementation more closely.

Look at the MSDN docs for each of them (SortedList, SortedDictionary) for details of the performance for different operations in different situtations. Here's a nice summary (from the SortedDictionary docs):

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, 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>.

(SortedList actually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)

SortedList , SortedDictionary and Dictionary

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).

Dictionary vs SortedList for data storage and processing

Use SortedDictionary<TKey, TValue> Class.

SortedDictionary<DateTime, Class2> dict = new SortedDictionary<DateTime, Class2>();

Following from the documentation explains well about the difference between using a SortedList vs SortedDictionary

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>.

For your question:

What's the best practice for creating the list (of Value1)?

List<decimal> list = dict.Values.Select(r=> r.Value1).ToList();

For your comment:

how to form a list consisting of Values1, say, for the last 3 days

List<decimal> listOfValue1 = dict.Where(r=> r.Key >= DateTime.Today.AddDays(-3) 
                                            &&  r.Key <= DateTime.Today)
                                 .Select(r=> r.Value.Value1)
                                 .ToList();

SortedList vs. SortedDictionary vs. Sort()

Well, it's an easy win on SortedList. Inserting an item requires a binary search (O(log(n)) to find the insertion point, then a List.Insert (O(n)) to insert the item. The Insert() dominates, populating the list requires O(n^2). If the input items are already sorted then the Insert collapses to O(1) but doesn't affect the search. Populating is now O(nlog(n)). You don't worry how big the Oh is, sorting first is always more efficient. Assuming you can afford the doubled storage requirement.

SortedDictionary is different, it uses a red-black tree. Finding the insertion point requires O(log(n)). Rebalancing the tree might be required afterwards, that also takes O(log(n)). Populating the dictionary thus takes O(nlog(n)). Using sorted input does not change the effort to find the insertion point or rebalancing, it is still O(nlog(n)). Now the Oh matters though, inserting sorted input requires the tree to constant rebalance itself. It works better if the input is random, you don't want sorted input.

So populating SortedList with sorted input and populating SortedDictionary with unsorted input is both O(nlog(n)). Ignoring the cost of providing sorted input, the Oh of SortedList is smaller than the Oh of SortedDictionary. That's an implementation detail due to the way List allocates memory. It only has to do so O(log(n)) times, a red-black tree has to allocate O(n) times. Very small Oh btw.

Notable is that neither one compares favorably over simply populating a List, then calling Sort(). That's also O(nlog(n)). In fact, if input is already accidentally sorted you can bypass the Sort() call, this collapses to O(n). The cost analysis now needs to move to the effort it takes to get the input sorted. It is hard to bypass the fundamental complexity of Sort(), O(nlog(n)). It might not be readily visible, you might get the input sorted by, say, a SQL query. It will just take longer to complete.

The point of using either SortedList or SortedDictonary is to keep the collection sorted after inserts. If you only worry about populating but not mutating then you shouldn't use those collections.

Can a SortedList /SortedDictionary with a properly implemented comparer be used to guarantee insertion order?

A comparer must obey the law

Compare(a, b) == -Compare(b, a) //assuming only possible values are -1, 0, 1

This is the symmetry property. Your sample code does not obey it. Therefore the BCL collections do not give you any guarantee at all. You have violated the documented contract.

You can't do this.

Instead, you could add a new field to M where you store the insertion order as an int. You can then use that field in the comparer.

when should I use a sorteddictionary instead of a dictionary

A SortedDictionary is implemented as a binary search tree. Therefore, accessing an element is O(lg(n)). A Dictionary is a hash table, and has a complexity of O(1) for access.

A SortedDictionary is quite useful when you need the data to be sorted (a Dictionary has no defined order). Dictionary is appropriate for most cases.

SortedList/SortedDictionary weird behavior

Dim Data As New SortedList(StringComparer.InvariantCultureIgnoreCase)

I think the problem is with the sort rules specified.

Changing InvariantCultureIgnoreCase to Ordinal or OrdinalIgnoreCase solves the problem

Dim Data As New SortedList(StringComparer.OrdinalIgnoreCase)

Here is the Demo

.Net Data structures: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary -- Speed, memory, and when to use each?

Off the top of my head:

• Array* - represents an old-school memory array - kind of like a alias for a normal type[] array. Can enumerate. Can't grow automatically. I would assume very fast insert and retrival speed.

• ArrayList - automatically growing array. Adds more overhead. Can enum., probably slower than a normal array but still pretty fast. These are used a lot in .NET

• List - one of my favs - can be used with generics, so you can have a strongly typed array, e.g. List<string>. Other than that, acts very much like ArrayList

• Hashtable - plain old hashtable. O(1) to O(n) worst case. Can enumerate the value and keys properties, and do key/val pairs

• Dictionary - same as above only strongly typed via generics, such as Dictionary<string, string>

• SortedList - a sorted generic list. Slowed on insertion since it has to figure out where to put things. Can enum., probably the same on retrieval since it doesn't have to resort, but deletion will be slower than a plain old list.

I tend to use List and Dictionary all the time - once you start using them strongly typed with generics, its really hard to go back to the standard non-generic ones.

There are lots of other data structures too - there's KeyValuePair which you can use to do some interesting things, there's a SortedDictionary which can be useful as well.

---

Related Topics