Functional Flow

StaticStringDictionary - Fast Switching With LINQ Revisited

| Comments

Expression trees are one of the more powerful features of C#. They let you manipulate code in ways that almost remind you of LISP macros (but at runtime instead of compile time). Since I discovered them, I managed to eliminate almost completely the usage of reflection in my code, replacing it with much faster code using techniques similar to what Roger Alsing described in Linq Expressions - Creating objects. Expression trees also made possible something that I find myself using a lot these days: what Jomo Fisher described in Fast Switching with LINQ. It's a great example of the powerful things C# allows you to do with a little creativity. As I used it more and more, I collected a few modifications to the original code, so I though in sharing them here. I named it StaticStringDictionary.

The main difference of this version from the original code is that I don't assume that the key being looked up is in the dictionary. That forces me to call string.Equals at the end to check if the key is the correct one. If string.Equals returns false, a fallback function is used. This also invalidates the optimization in the original code that took advantage of different keys with the same value. I also made StaticStringDictionary<T> implement IDictionary<string, T> so it would be easier to adapt existing code.

Unfortunately I also stumbled over some problems with certain dictionaries, similar to the ones that Raptor-75 wrote about in the comments of the original article. After a few hours of debugging together with Rui Eugénio (and also with the help of Expression Tree Visualizer and StructsViz DebuggerVisualizer), we managed to fix all the problems we found. The comparer was changed to ensure the characters of indices already tested are ignored for the ordering, and in some situations the algorithm has to some backtracking.

Without further due, here's the code:

And here's the test case for Raptor-75's problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void Main() {

   var dict = StaticStringDictionary.Create(
       new Dictionary<string, int> {
           {"Ado", 0},
           {"A2o", 1},
           {"A2i", 2},
           {"B2o", 3},
           {"AdoX", 4},
           {"AdPX", 5}
       },
       key => -1);

    Test("Ado", dict);
    Test("A2o", dict);
    Test("A2i", dict);
    Test("B2o", dict);
    Test("AdoX", dict);
    Test("AdPX", dict);
    Test("xpto", dict);
}

private static void Test(string key, IDictionary<string, int> dict) {
    Console.WriteLine(key + ": " + dict[key]);
}

It should produce this output when run:

1
2
3
4
5
6
7
Ado: 0
A2o: 1
A2i: 2
B2o: 3
AdoX: 4
AdPX: 5
xpto: -1

I also found useful to define this variation when I also need to do reverse lookups:

Comments