Implementing case-insensitive lookup tables (Dictionary) with string keys

The Dictionary type in .Net takes in a comparer as a constructor parameter. So you could pass in StringComparer.OrdinalIgnoreCase and you're done.
I used to upper-case keys while adding it to the lookup table earlier and again when performing a lookup - to achieve case-insensitive string lookups. I remember reading some article about String.ToUpper() being optimized for such scenarios. Now I was unsure - which one is better ?

So I ran a small experiment.

//void Main()
var keys_for_lookup = new List<string> { "abc", "dEF", "123", "655", "pQr" };
for (int i = 0; i < 3; i++)
{
var dict1 = new Dictionary<string, object>();
AddSomeKeys(dict1, new List<string> { "ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "XYZ", "123" });
TimeIt(delegate { RunTest_Upper(dict1, keys_for_lookup); });

dict1 = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);
AddSomeKeys(dict1, new List<string> { "abc", "def", "ghi", "jkl", "mno", "pqr", "XYZ", "123" });
TimeIt(delegate { RunTest(dict1, keys_for_lookup); });
}

// end of main



And this is what the results looked like :
It looks like using a Dictionary with a comparer injected is
  1. faster
  2. less hassle. You specify it once and forget it. You do not have remember to do UpperCase each time you lookup the map. (e.g. from the p.o.v. of future programmers)
  3. less memory pressure. ToUpper() would create a new String instance per lookup.


From My conversations with gullible machines...

(Setup: .Net 3.5, VS2008, WinXP SP2, Intel T7400 Core 2, 2GB RAM on a normal work afternoon, lots of apps open)

The rest of the code for scrutiny:


private static void AddSomeKeys(Dictionary<string, object> dict1, List<string> keys)
{
foreach (var key in keys)
dict1.Add(key, new Object());
}

private static void RunTest_Upper(Dictionary<string, object> dict1, List<string> keys)
{
for (int i = 0; i < 1000000; i++)
foreach (var key in keys)
{ var v = dict1.ContainsKey(key.ToUpper()); }

}
private static void RunTest(Dictionary<string, object> dict1, List<string> keys)
{
for (int i = 0; i < 1000000; i++)
foreach (var key in keys)
{ var v = dict1.ContainsKey(key); }
}

private static void TimeIt(Action action)
{
var s = System.Diagnostics.Stopwatch.StartNew();
action.Invoke();
s.Stop();
Console.WriteLine("Elapsed msecs = {0}", s.ElapsedMilliseconds);
}

No comments:

Post a Comment