26

As I wrote in some of my last posts I am still quite new to the c# world so it comes that I wrote small benchmark to compare Dictionary, Hashtable, SortedList and SortedDictionary against each other. The test runs with 8000 iterations and from 50 to 100000 elements. I tested adding of new elements, search for elements and looping through some elements all random. The results was as I expected them to be except the result of the SortedDictionary which was much confusing for me... It was just slow in all results. So did I missing sometging about the concept of a sorted dictionary. I already asked google but All that I found out was that others had come to the same test result. Slightly different based on their implementation of the test. Again my question: why is the SortedDicrionary so much slower than all the others?

sra
  • 23,820
  • 7
  • 55
  • 89

3 Answers3

34

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.

Andrew
  • 7,848
  • 1
  • 26
  • 24
Etienne de Martel
  • 34,692
  • 8
  • 91
  • 111
  • 8
    In direct response to the question, "why is the SortedDictionary so much slower than all the others": It's a tradeoff between CPU-usage and RAM-usage. Dictionary is faster than SortedDictionary because it is implemented as a hash-table, an algorithm that is designed to use excess memory in order to use as few operations as possible. SortedDictionary is a binary-search-tree, an algorithm that is designed to use as many operations as necessary to use as little RAM as possible. – M-Pixel Apr 17 '19 at 23:08
  • INB4: Yes, those were grossly oversimplified representations of the motivations behind hashtable and BST. – M-Pixel Apr 17 '19 at 23:09
  • There is much more to performance than just Big oh. The O(1) operation could be longer than 25 operations of tree search. I don't think that's the case, but this answer doesn't tell you in what cases you should use them. – Justin Meiners Aug 29 '19 at 01:08
  • 1
    A Dictionary is still appropriate for most use cases, when you don't need the data to be ordered according to the key. Of course, you should always profile, but an initial implementation should probably stick to Dictionary unless ordering is needed or profiling reveals that it's more efficient to use the SortedDictionary. – Etienne de Martel Aug 29 '19 at 15:56
  • One example of how a sorted dictionary would be useful is if you need to loop through all of the elements in sorted order by key. The standard dictionary will not loop through the keys in sorted order. Another benefit is if you need to look at the values in sorted order when debugging, which was personally useful to me to see which keys were missing from my dictionary, but you'll probably want to change back to dictionary for your production code. If you only need to lookup a value by known key, a sorted dictionary provides little or no additional value. – user3308241 Sep 16 '22 at 21:26
5

The answer is simply that you would use the SortedDictionary if you need a dictionary that is sorted.

Remember that eventhough it ended up as slowest in your tests, it's still not slow. If you need exactly what the SortedDictionary does, it's the best solution. To do the same using a Dictionary or a SortedList would be very much slower.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • 4
    This answer basically answers the question: "When do I need a SortedDictionary?" saying: "When you need one!" This is not helpful at all. Give at least one example when using a `SortedDictionary` would be a good idea. – Jack Miller Jul 01 '20 at 10:40
  • @JackMiller: Why do you think that a specific example is required? The accepted answer doesn't give any example. – Guffa Aug 06 '20 at 09:10
  • The accepted answer tackles the performance question (no example needed). This answer concerns the question in the title: "when should I use a sorteddictionary instead of a dictionary[?]" To answer such a question one could either define (universally applicable) rules (which would be quite difficult) or give some concrete examples. – Jack Miller Aug 06 '20 at 10:40
3

Again my question: why is the SortedDicrionary so much slower than all the others?

Etienne already gave the technical answer before, but to add a more 'plain' remark: I'd guess that the "Sorted" bit part of a SortedDictionary puts some overhead on inserts and even retrieving items as it seems from Etienne's answer.

However, in a real app a SortedDictionary can probably provide considerable performance or 'perceived performance' increase if you need an "already sorted dictionary" at some time in your app.

Hope that helps.

Jeroen
  • 60,696
  • 40
  • 206
  • 339
  • I think "retrieving items" is much faster with a sorteddictionary - in most cases – Grantly Apr 17 '19 at 21:10
  • "In most cases" = depending on how big the dictionary is. A 3-item SortedDictionary might be faster to read than a 3-item Dictionary, while a 15-item SortedDictionary ends up being slower. – M-Pixel Apr 17 '19 at 22:57