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?
问题:
回答1:
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.
回答2:
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.
回答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.
