1

I have a list of about 500 strings "joe" "john" "jack" ... "jan"

I only need to find the ordinal.

In my example, the list will never be changed.

One could just put them in a list and IndexOf

ll.Add("joe")
ll.Add("john")
...
ll.Add("jan")
ll.IndexOf("jib") is 315

or you can put them in a dictionary, using the ordinal integers as the values,

dd.Add("joe", 1)
dd.Add("john", 2)
dd.Add("jack", 3)
...
dd.Add("jan", 571)
dd["jib"] is 315

FTR the strings are 3 to 8 characters long. FTR this is in a Unity, hence Mono, milieu.

  1. Purely for performance, is one approach generally preferable?

1b) Indeed, I found a number of analysis of this nature: http://www.dotnetperls.com/dictionary-time (google for a number of similar analyses). Does this apply to the situation I describe or am I off here?

  1. It's a shame there isn't a "HashSetLikeThingWithOrdinality" type of facility - if I'm missing an obvious please let us know. Indeed, this seems like a fairly common, basic, collections use case - "get the ordinal of some strings" - perhaps I am completely missing something obvious.
9
  • Write test code and profile it. Jan 22, 2016 at 18:58
  • Hi @DanielMann yeah I did that (in my specific case). Can you answer my question (1) or question (2)? Thanks. (Willaien already gave a spectacularly useful tip I had no idea about List<T>.BinarySearch
    – Fattie
    Jan 22, 2016 at 19:01
  • 2
    List.IndexOf traverses the entire list until it finds a match, whereas the dictionary is a hash lookup. From a strictly performance perspective the dictionary lookups will be much faster. (as your linked article also shows).
    – Dave Zych
    Jan 22, 2016 at 19:02
  • 3
    I strongly suspect that, even with BinarySearch() being a thing that the performance of a Dictionary will be much greater. In a few micro-benchmarks, no matter the number of elements (at least beyond 2 or 3), indexing on a Dictionary is significantly faster than a BinarySearch(), however, constructing said dictionary isn't cheap in and of itself.
    – willaien
    Jan 22, 2016 at 19:12
  • 1
    @JoeBlow: phew. Done.
    – willaien
    Jan 22, 2016 at 22:32

3 Answers 3

6

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.

5
  • If the point of using a list is that finding its index effectively finds a value for the string as a key, then sorting it means you now get the wrong value. As such you have to do the linear O(n) search, not a binary search.
    – Jon Hanna
    Jan 22, 2016 at 23:09
  • 1
    @JonHanna He specifically mentions that the data is already sorted. He wants to find the index of the item in the sorted data. My answer is with that context.
    – willaien
    Jan 22, 2016 at 23:15
  • They said it was ordered, not the criteria for the ordering. Most algorithmic orders of the sort one can use with a sort would put "jack" before "joe".
    – Jon Hanna
    Jan 22, 2016 at 23:17
  • hi @willaien you know, sorry I had a typo, the list is NOT ordered: they are typical partcodes, just a long seemingly random list of "zb13" "nb22" type codes. Nevertheless this information is great, awesome. (Indeed, they could easily be sorted, as part of a best approach, so this is to be considered.)
    – Fattie
    Jan 22, 2016 at 23:24
  • If it's unordered data, then IndexOf is all you'd be able to do with it, unless you sort the List, which obviously changes the order. There are other ways to store the data (eg. SortedDictionary that would make use of binary searches under the hood, but they're likely worse than plain old Dictionary in performance.)
    – willaien
    Jan 22, 2016 at 23:46
3

I suspect that there might be a twist somewhere, as such a simple question has no answer for 2 hours. I'll risk being down-voted, but here is my answers:

1) Dictionary (hash table-based) is clearly a better choice for a fast lookup. List, on the other hand, is the worst choice.

1.b) Yes, it applies here. Search in the List has linear complexity, while Dictionary provides constant time lookup.

2) You are trying to map a string to an ordinal; any kind of map will be natural here (while any kind of list is awkward).

2

Dictionary is the natural approach for a lookup.

A list would be an optimisation for less memory use at the cost of decreased speed. An array would do better still (same time, but slightly less memory again).

If you already had a list or array for some other reason then the memory saving would be greater still, because no more memory was used that would be used anyway, and so a better optimisation for space at the same cost to speed. (If the order of the keys was the same as a sort then it could be O(log n) but otherwise it's O(n)).

Creating the dictionary itself takes time, so while it's the fastest approach if the number of times it is looked up is small then it might cost as much as it saves and so not be worth it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.