SortedDictionary<> or (Dictionary<> Manual Sort)

Question

Is there a performance hit when I use SortedDictionary<> rather than Dictionary<> taking into consideration that I need a sorted Dictionary, so if I used a Dictionary, I would have to manually sort it. Which would be faster? SortedDictionary<> or (Dictionary<> + Manual Sort).

Answer 1

Inserts into a SortedDictionary are O(log(n)), so inserting n items is O(n log(n)). In contrast, inserts into a Dictionary are O(1), so inserting n items is O(n), but you'll need to sort the items before use, which is O(n log(n)). Based on that, there isn't much difference, but Dictionary has the overhead of hashing, while the SortedDictionary might have worse memory locality since it is probably implemented as a linked structure.

SortedDictionary also places a limit on the key types you can use since it needs to sort by the key, while Dictionary does not since it uses hashing.

Really, which is better depends on your access patterns, so the best thing to do is to measure the performance of both for your use case.

Answer 2

There is a performance hit. Read the remarks at http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

Basically, SortedDictionary<T> is a binary search tree whereas Dictionary<T> is a hash table.

For inserting, removing, and random lookup, Dictionary<T> will be faster. SortedDictionary will be faster if you make infrequent modifications and frequent lists in order. Dictionary is faster if you make frequent modifications and random lookups, and infrequently have to sort then output.

Answer 3

it's really going to depend on how you are using the dictionary.

• Are you using a lot of items or not very many items.
• How frequently do you add new items in comparison to when you need them sorted.
• Do you do more lookups or insertions

Best thing to do is to do some performance tests on real-ish data with both approaches and see which fits your circumstances better.

Answer 4

That depends on whether you add data to the dictionary separate from getting the sorted result, or do it all at once.

If you add data over a longer time, you will get a small performance hit for each add using a SortedDictionary<>, but when you finally want the sorted result you get it instantly. This is ideal if you for example wait for user input to add items, because the small performance hits are not noticable.

If you create a dictionary, add data to it, and get the sorted result right away, a Dictionary<T> would be faster because it uses a faster sorting algorithm (as it can sort it all at once instead of maintaining a sorted result while items are added).