Home
Map
SortedDictionaryUse and benchmark the SortedDictionary collection. Understand the performance of SortedDictionary.
C#
This page was last reviewed on Apr 4, 2023.
SortedDictionary. This C# type keeps its keys always sorted. It allows you to avoid sorting the keys on your own. Its lookup performance is slower than Dictionary.
Some notes. SortedDictionary has advantages if you require a sorted lookup table in memory. Usually, a default Dictionary type is simpler and faster.
Dictionary
SortedList
An example. Here we see the SortedDictionary collection from System.Collections.Generic being used. We add 5 keys in any order, being careful not to add duplicates.
Generic
Info We use the TryGetValue method on the SortedDictionary, which is excellent for avoiding another key lookup.
And If the key exists, the TryGetValue method returns true and it fills the out parameter.
out
Then We use foreach on the SortedDictionary. This invokes the custom enumerator, which returns a sequence of KeyValuePairs.
foreach
using System; using System.Collections.Generic; var sort = new SortedDictionary<string, int>(); // Add strings and int keys. sort.Add("zebra", 5); sort.Add("cat", 2); sort.Add("dog", 9); sort.Add("mouse", 4); sort.Add("programmer", 100); // See if it doesn't contain "dog." if (sort.ContainsKey("dog")) { Console.WriteLine(true); } // See if it contains "zebra." if (sort.ContainsKey("zebra")) { Console.WriteLine(true); } // See if it contains "ape." Console.WriteLine(sort.ContainsKey("ape")); // See if it contains "programmer", and if so get the value. int v; if (sort.TryGetValue("programmer", out v)) { Console.WriteLine(v); } // Print SortedDictionary in alphabetic order. foreach (KeyValuePair<string, int> p in sort) { Console.WriteLine("{0} = {1}", p.Key, p.Value); }
True True False 100 cat = 2 dog = 9 mouse = 4 programmer = 100 zebra = 5
Some research. Here we review the difference between Dictionary and SortedDictionary. The difference is stated in terms of performance.
Dictionary lookup time: Close to O(1) SortedDictionary lookup time: O(log n)
Performance. I devised a benchmark that looped through various element counts. I tested how long it took to add that many keys, and how long it took to find a key.
Note The first row has 10 elements. And then each following row has 10 times more. The times are in milliseconds.
Result Performance was awful and it degraded when there were more than 10000 elements to the point of failure.
5, 0 0, 0 1, 0 22, 2 310, 33 3769, 521
73, 5 132, 6 188, 8 255, 9 340, 9 419, 10
Usage notes. In one of my programs, I needed to maintain a frequency table of various string keys. Instead of Dictionary, I decided to use SortedDictionary.
So When I needed to print the SortedDictionary to a file, I wouldn't need to sort it again.
A summary. We used the SortedDictionary collection. SortedDictionary can rapidly degrade performance as the number of elements grows.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Apr 4, 2023 (simplify).
Home
Changes
© 2007-2024 Sam Allen.