I had a situation at work today where I need to sort a Dictionary with string as key.
The keys in the Dictionary are in this order: “Title 1”, “Title 2”, “Title 3” etc.
I cannot use the normal framework SortedDictionary because if you sort by key as string, the items in the SortedDictionary will be sorted according to the unicode value…
e.g. you will get something like “Title 1”, “Title 10”, “Title 2” etc… totally undesirable…
Since I will need to write my own IComparer to do the custom comparison, I wonder if using Linq will provide a better solution.
So I spent probably an hour as work trying to create the query but I realized again that I am not that familiar with Linq (mostly about how to use lambda expression properly with Orderby. s I dropped the work, but then when I came back to work on the code later at home, it all became clear:
Here is the code:
static SortedList<string, double> FrameworkListSort(
Dictionary<string, double> columnWidthDictionary)
{
return new SortedList<string, double>(columnWidthDictionary, new TitleComparer());
}
static SortedDictionary<string, double> FrameworkDictionarySort(
Dictionary<string, double> columnWidthDictionary)
{
return new SortedDictionary<string, double>(columnWidthDictionary, new TitleComparer());
}
static IOrderedEnumerable<KeyValuePair<string, double>> LinqListSort(
Dictionary<string, double> columnWidthDictionary)
{
return columnWidthDictionary.OrderBy(
column => /*column.Key);*/
{
int rank;
Int32.TryParse(column.Key.Substring(sTitle.Length).Trim(), out rank);
return rank;
});
}
static IOrderedEnumerable<KeyValuePair<string, double>> LinqListSort(
IEnumerable<KeyValuePair<string, double>> columnWidthDictionary,
string criteria)
{
return columnWidthDictionary.Where(targetColumn => targetColumn.Key != criteria).OrderBy(
column =>
{
int rank;
Int32.TryParse(column.Key.Substring(sTitle.Length).Trim(), out rank);
return rank;
});
}
Although the Linq code is not as simple as a constructor, the I know that using Linq is superior performance-wise compared to SortedDictionary.
However, there’s only one way to test it out, so I created a 100,000 items Dictionary with “Title x” as string key, and then compared the time it takes to sort created a sorted list using the three algorithms. There is the result:
While it isn’t too surprising that using Linq yield a “faster” solution, I was surprised that element removal using Linq (since it requires looping via the whole IEnumberable structure) is not worse than SortedDictionary. But SortedList is still faster – probably because it only needs to remove the one element in a linked-list, instead of reorganizing the whole b-tree in SortedDictionary case.
So for sorting: IOrderedEnumerable >> SortedList > SortedDictionary
For element removal: SortedList > IOrderedEnumerable > SortedDictionary.
Here is the test code, so you may try it at home :)
static void Main(string[] args)
{
const int numItems = 100000;
Random rand = new Random();
Dictionary<string, double> columnWidthDictionary = new Dictionary<string, double>();
for (int index = 1; index <= numItems; index++)
{
columnWidthDictionary.Add(String.Format("{0} {1}", sTitle, index), rand.NextDouble());
}
Stopwatch watch = new Stopwatch();
watch.Reset();
watch.Start();
SortedList<string, double> sortedColumnWidthDictionary =
FrameworkListSort(columnWidthDictionary);
watch.Stop();
Console.WriteLine(String.Format("Time elasped (FrameworkListSort) : {0} ms",
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
SortedDictionary<string, double> sortedColumnWidthDictionary2 =
FrameworkDictionarySort(columnWidthDictionary);
watch.Stop();
Console.WriteLine(String.Format("Time elasped (FrameworkDictionarySort) : {0} ms",
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
IOrderedEnumerable<KeyValuePair<string, double>> sortedEumerableColumns =
LinqListSort(columnWidthDictionary);
watch.Stop();
Console.WriteLine(String.Format("Time elasped (LinqListSort) : {0} ms",
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
//sortedColumnWidthDictionary.Remove(sortedColumnWidthDictionary.Keys.Last());
sortedColumnWidthDictionary.RemoveAt(sortedColumnWidthDictionary.Count-1);
watch.Stop();
Console.WriteLine(String.Format("Time elasped (SortedList + Remove last item) : {0} ms",
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
//sortedColumnWidthDictionary2.Remove(sortedColumnWidthDictionary.Keys.Last());
sortedColumnWidthDictionary2.Remove("Title 1");
watch.Stop();
Console.WriteLine(String.Format("Time elasped (SortedDictionary - Remove last item) : {0} ms",
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
sortedEumerableColumns = LinqListSort(sortedEumerableColumns, "Title 1");
watch.Stop();
Console.WriteLine(String.Format("Time elasped (LinqListSort with criteria for removing last item) : {0} ms",
watch.ElapsedMilliseconds));
Console.ReadLine();
}
