Performance Dictionary<string,int> versus List<string>

Here's a small overview on the difference between using a Dictionary<string,int> and a (sorted)List<string> for this:

Observations: 1) In my micro benchmarks, once the dictionary is created, the dictionary is much faster. (Explanations as to why will follow shortly) 2) In my opinion, mapping in some way (eg. a Dictionary or HashTable) will be significantly less awkward.

Performance:

For the List<string>, to do a binary search, the system will start in the 'middle', then walk each direction (stepping into the 'middle' in the now halved search space, in a typical divide and conquer pattern) depending on if the value is greater or smaller than the value at the index it's looking at. This is O(log n) growth. This assumes that data is already sorted in some manner (also applies to stuff like SortedDictionary, which uses data structures that allow for binary searching)

Alternately, you'd do IndexOf, which is O(n) complexity because you have to walk every element.

For the Dictionary<string,int>, it uses a hash lookup (generates a hash of the object by calling .GetHashCode() on the TKey (string in this case), then uses that to look up in a hash table (then does a compare to ensure it is an exact match), and gets the value out. This is roughly O(1) growth (ie. the complexity doesn't grow meaningfully with the number of elements) [Not including worst case scenarios involving hash collisions here]

Because of this, Dictionary<string,int> takes a (relatively) constant amount of time to do lookups, while List<string> grows according to the number of elements (albeit at a logarithmic (slow) rate).

Testing: I did a few micro benchmarks, where I took the top 500 female names and did lookups against them. The lookups looked something like this:

var searchItems = new[] { "Maci", "Daria", "Michelle", "Amber", "Henrietta"}; foreach (var item in searchItems) { sortedList.BinarySearch(item); //You'd store the output here. Just looking at performance } 

And compared it to a dictionary lookup:

 foreach (var item in searchItems) { var output = dictionary.ContainsKey(item) ? dictionary[item] : -1; //Presumably, output would be declared outside of this, just getting rid of a compiler error } 

So, here's the thing: even for a small number of elements, with short strings as lookup keys, a sorted List<string> isn't any faster (on my machine, in my admittedly simplistic tests) than a Dictionary<string,int>. Once again, this is a microbenchmark, but, for 500 elements, the 5 lookups are roughly 3x faster with the dictionary.

Keep in mind, however, that the list was 6.3 microseconds, and the dictionary was 1.8 microseconds.

Syntax: Using a list as a lookup to find indexes is slightly awkward. A mapping type (like Dictionary) implies intent much better than your lookup list does, which should make for more maintainable code in the end.

That said, with my syntax and performance considerations, I'd say go with the Dictionary. However, if you don't like Dictionaries for whatever reason, the performance considerations are on such a small scale that it's a pointless thing to worry about anyways.

Edit: Bonus points, you will probably want to use a case-insensitive comparer for either method. You can pass a comparer as an argument for Dictionary and BinarySearch() should support a comparer as well.