Is it possible to optimize large switch on strings?

Question

I'm looking through a friend of mine's library because he asked about optimization and I came across a section of code like this:

long digit = 0;

switch (word) {
    case "zero":
        digit = 0;
        break;
    case "a":
    case "one":
        digit = 1;
        break;
    case "two":
        digit = 2;
        break;
    case "three":
        digit = 3;
        break;
    case "four":
        digit = 4;
        break;
    case "five":
        digit = 5;
        break;
    case "six":
        digit = 6;
        break;
    case "seven":
        digit = 7;
        break;
    case "eight":
        digit = 8;
        break;
    case "nine":
        digit = 9;
        break;
    case "ten":
        digit = 10;
        break;
    case "eleven":
        digit = 11;
        break;
    case "twelve":
        digit = 12;
        break;
    case "thirteen":
        digit = 13;
        break;
    case "fourteen":
        digit = 14;
        break;
    case "fifteen":
        digit = 15;
        break;
    case "sixteen":
        digit = 16;
        break;
    case "seventeen":
        digit = 17;
        break;
    case "eighteen":
        digit = 18;
        break;
    case "nineteen":
        digit = 19;
        break;
    case "twenty":
        digit = 20;
        break;
    case "thirty":
        digit = 30;
        break;
    case "fourty":
        digit = 40;
        break;
    case "fifty":
        digit = 50;
        break;
    case "sixty":
        digit = 60;
        break;
    case "seventy":
        digit = 70;
        break;
    case "eighty":
        digit = 80;
        break;
    case "ninety":
        digit = 90;
        break;
}

return digit;

I've seen a few questions on here about exactly how a switch might work, but they conveniently don't mention cases with strings. Can a switch statement like the one above be optimized in any way?

I'm willing to bet a dollar that somewhere in this program there is a bug whereby the string "twenty-a" is parsed as 21. Also, "forty" is misspelled. — Eric Lippert, Aug 23 '11 at 15:08
Mitch Wheat - No, but in my book you don't optimize bad code into good code, you optimize good code into better code. — Corey Ogburn, Aug 23 '11 at 15:10
possible duplicate of [How would you make this switch statement as fast as possible?](http://stackoverflow.com/questions/1837546/how-would-you-make-this-switch-statement-as-fast-as-possible) — H H, Aug 23 '11 at 15:15
@Corey: In my book, you don't waste shareholder money by spending time and money "optimizing" code that is (1) already good enough, and (2) probably not the slowest thing in the program. Spend your time getting the code *correct* before you spend time getting it fast. I've found two bugs already just by glancing at it; spend your time getting the bugs out. — Eric Lippert, Aug 23 '11 at 15:18
@Eric There are no shareholders, this is a personal project. "twenty-a" does not get converted to 21, other checks elsewhere prevent this, and the spelling check (albeit I'm glad you found it) is a fix outside of the focus of the question. We already have unit tests set up and are iteratively switching between debugging, optimizing and then debugging those optimizations. — Corey Ogburn, Aug 23 '11 at 15:24
@Corey Ogburn: There are always shareholders, just maybe not what you traditionally think of as shareholders. Perhaps "stakeholders" is a more appropriate term, but the point remains that someone somewhere (it might only be you) has an interest or concern in this project. — jason, Aug 23 '11 at 17:20

score 11 · Accepted Answer · answered Aug 23 '11 at 15:05

11

As Oded said, you can put them in a Dictionary. But in fact, the .NET compiler already does this for you: it builds a jump table (via a Dictionary<string, SomeDelegate>) that allows to switch on the value in O(1).

That said, I actually find using a Dictionary<string, int> more readable than a switch here.

answered Aug 23 '11 at 15:05

Konrad Rudolph

530,221
131
937
1,214

1

It does? Cool, didn't know that, could you link to a source? – mafu Aug 23 '11 at 15:07
1

That's an interesting bit of knowledge. Can you provide a link with more info? – Michael Brown Aug 23 '11 at 15:07
I did not know that as well, I'd be curious to read more about that. – James Michael Hare Aug 23 '11 at 15:08
2

@mafutrct I don’t have a source handy but you can just see for yourself by using Reflector or a disassembled .NET executable. – Konrad Rudolph Aug 23 '11 at 15:08
@James - one more for your "Little Wonders"? – Oded Aug 23 '11 at 15:09
@Konrad: I do agree on the readability comment. If it's just looking up a value and returning the result, the Dictionary directly will have far less vertical bloat size than a switch (especially since you can use a collection initializer). – James Michael Hare Aug 23 '11 at 15:10
Also, using a dictionary provides further conveniences like reverse lookups, ie: ContainsValue(). – Jack Aug 23 '11 at 15:23

Oded · Answer 2 · 2011-08-23T15:10:52.047

9

You can put these in a Dictionary<string,int> and return the int for the string key.

var wordsToNumbers = new Dictionary<string,int>();
wordsToNumbers.Add("one", 1);
...
wordsToNumbers.Add("ninety", 90);


// elsewhere
return wordsToNumbers[word];

Note:

As others have noted in the comments - the idea is to build the dictionary once and reuse it. One way would be to use a field and populate it in a constructor, then use it in other methods.

edited Aug 23 '11 at 15:10

answered Aug 23 '11 at 15:04

Oded

489,969
99
883
1,009

beat me to it! Just make sure the process is cached some how. This way it's not building the Dictionary more than once. – Brian Aug 23 '11 at 15:07
Just a note: this can only be a good idea if you keep the dictionary around and reuse it every time you call this weird month-digit function. It would be *not* be a good idea to build a dictionary every time and search it. – Rag Aug 23 '11 at 15:09
I seem to remember the compiler will use a Dictionary too when that's profitable. – H H Aug 23 '11 at 15:12
@Henk - This is what Konrad is also saying. Do you have a link to documentation to that effect? – Oded Aug 23 '11 at 15:15

score 2 · Answer 3 · answered Aug 23 '11 at 15:06

In this case, a better optimization might be to have a static Dictionary:

private static readonly Dictionary<string, long> _lookup = new Dictionary<string, long>
   {
       { "one", 1 },
       { "two", 2 },
       { "three", 3 },
       // etc...
   }

Then just access to use:

var number = "one";
var result = _lookup[number];

score 1 · Answer 4 · answered Aug 23 '11 at 15:16

1

You could use a dictionary instead of a massive switch. As far as timings, time the switch versus the dictionary. The dictionary would be cleaner I think, but may perform the same.

answered Aug 23 '11 at 15:16

Jon Raynor

3,804
6
29
43

I didn't get the load new answers warning dialog, so this answer is redundant. – Jon Raynor Aug 23 '11 at 15:19

score 0 · Answer 5 · answered Aug 23 '11 at 15:06

0

Measure if it is required. Use a profiler.
The easiest way is a Dictionary. It would be very fitting for your use case, too.

answered Aug 23 '11 at 15:06

mafu

31,798
42
154
247

score 0 · Answer 6 · answered Aug 23 '11 at 15:08

0

Switch on string will switch to using a hashtable when the number of strings gets to be large enough that a hashtable is quicker than a series of comparisons.

You can verify this using Reflector.

answered Aug 23 '11 at 15:08

Mitch Wheat

295,962
43
465
541

Is it possible to optimize large switch on strings?

6 Answers6