C# SortedDictionary

Use and benchmark the SortedDictionary collection. Understand the performance of SortedDictionary.

SortedDictionary. This 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

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 Class, Method

Steps: In part 6, 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.

C# program that uses SortedDictionary using System; using System.Collections.Generic; class Program { static void Main() { // 1 // New SortedDictionary SortedDictionary<string, int> sort = new SortedDictionary<string, int>(); // 2 // 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); // 3 // Example: see if it doesn't contain "dog" if (sort.ContainsKey("dog")) { Console.WriteLine(true); } // 4 // Example: see if it contains "zebra" if (sort.ContainsKey("zebra")) { Console.WriteLine(true); } // 5 // Example: see if it contains "ape" Console.WriteLine(sort.ContainsKey("ape")); // 6 // Example: see if it contains "programmer", // and if so get the value for "programmer" int v; if (sort.TryGetValue("programmer", out v)) { Console.WriteLine(v); } // 7 // Example: print SortedDictionary in alphabetic order foreach (KeyValuePair<string, int> p in sort) { Console.WriteLine("{0} = {1}", p.Key, p.Value); } } } Output 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.

Quote: The SortedDictionary(TKey, TValue) generic class is a binary search tree with O(log n) retrieval, where N is the number of elements in the dictionary (Microsoft Docs).

Benchmark results: Dictionary lookup time: Close to O(1) SortedDictionary lookup time: O(log n)

Notes, usage. 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.

Tip: By using SortedDictionary instead of custom Dictionary sorting code, you can reduce the footprint of your .NET program.

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.

Add element benchmark: SortedDictionary, Dictionary 5, 0 0, 0 1, 0 22, 2 310, 33 3769, 521 ContainsKey benchmark: SortedDictionary, Dictionary 73, 5 132, 6 188, 8 255, 9 340, 9 419, 10

SortedList. There is also a SortedList collection. This provides essentially the same functionality as the SortedDictionary but with a different implementation.

Note: The SortedList has different performance characteristics, particularly when inserting or removing elements from the collection.

SortedList

A summary. We used the SortedDictionary collection. SortedDictionary can rapidly degrade performance as the number of elements grows.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# SortedDictionary

Related Links:

.Net

Java

Related Links