When to use a SortedList over a SortedDictionary?

by

I’m not sure how accurate the MSDN documentation is on SortedList and SortedDictionary. It seems to be saying both are implemented using a binary search tree. But if the SortedList uses a binary search tree, why would it be much slower on additions than SortedDictionary?

Anyway, here are some performance test results.

Each test operates on a SortedList / SortedDictionary containing 10,000 int32 keys. Each test is repeated 1,000 times (Release build, Start without Debugging).

The first group of tests add keys in sequence from 0 to 9,999. The second group of tests add random shuffled keys between 0 to 9,999 (every number is added exactly once).

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

As with any profiling, the important thing is the relative performance, not the actual numbers.

As you can see, on sorted data the sorted list is faster than the SortedDictionary. On unsorted data the SortedList is slightly quicker on retrieval, but about 9 times slower on adding.

If both are using binary trees internally, it is quite surprising that the Add operation on unsorted data is so much slower for SortedList. It is possible that sorted list may also be adding items to a sorted linear data structure at the same time, which would slow it down.

However, you would expect the memory usage of a SortedList to be equal or greater than or at least equal to a SortedDictionary. But this contradicts what the MSDN documentation says.

More Related Contents:

  1. What’s the difference between SortedList and SortedDictionary?
  2. Is there a Lower Bound function on a SortedList?
  3. C# Sortable collection which allows duplicate keys
  4. SortedList, SortedDictionary and Dictionary
  5. How to provide user name and password when connecting to a network share
  6. How do you sort a dictionary by value?
  7. Make an Installation program for C# applications and include .NET Framework installer into the setup
  8. AddBusinessDays and GetBusinessDays
  9. Is there an alternative to string.Replace that is case-insensitive?
  10. How can a Label control display Japanese characters properly when the Font used doesn’t support this language?
  11. Why DateTime.AddHours doesn’t seem to work?
  12. .NET – WindowStyle = hidden vs. CreateNoWindow = true?
  13. How do I do a SHA1 File Checksum in C#?
  14. How to check whether an object has certain method/property?
  15. Can I optionally turn off the JsonIgnore attribute at runtime?
  16. WPF: How do I loop through the all controls in a window?
  17. Is String a primitive type?
  18. Is there any connection string parser in C#?
  19. why does DateTime.ToString(“dd/MM/yyyy”) give me dd-MM-yyyy?
  20. BinaryWriter Endian issue
  21. Invalid URI: The format of the URI could not be determined
  22. C#: How to add subitems in ListView
  23. How to check the Internet connection with .NET, C#, and WPF
  24. Converting String To Float in C#
  25. How to compare only Date without Time in DateTime types?
  26. When or if to Dispose HttpResponseMessage when calling ReadAsStreamAsync?
  27. Use the XmlInclude or SoapInclude attribute to specify types that are not known statically
  28. Days, hours, minutes, seconds between two dates
  29. Selenium WebDriver throws Timeout exceptions sporadically
  30. Use convolution to find a reference audio sample in a continuous stream of sound

Leave a Comment