CODEWITHSUNDEEP
c#dictionaryienumerableanytrygetvalue
Pawan Nogariya
Pawan Nogariya

Reputation: 8980

Which is more efficient Dictionary.TryGetValue or List.Any

I have a case where I have to find out if element belongs to a list or not in loop.

The straight forward way to do this is to call the Any method of the list, like this

public class Person
{
    public int Id { get; set;}
    public string Name { get; set;}
}

List<Person> persons = new List<Person>();

foreach(int personId in personIds)
{
    if(persons.Any(x => x.Id == personId))
    {
       // do something
    }
}

The other way I have seen developers using is by using Dictionary and calling its TryGetValue method, like this

Dictionary<int, Person> personLookup = new Dictionary<int, Person>();
foreach(int personId in personIds)
{
   if(personLookup.TryGetValue(personId, out var person))
   {
      // do something
   }
}

Which is more efficient in the two?

Upvotes: 0

Views: 279

Answers (3)

Marc Gravell
Marc Gravell

Reputation: 1063864

In the code shown, the dictionary is empty; so it will never find anything. I'm not just being silly here: dictionaries are cheap when fetching by key, but there are additional costs in constructing and populating the dictionary, so a key factor is the timing of that population. If you are going to create a dictionary just for this loop, then is is very complex to answer which is faster - it would depend on the population counts of the two sets of values, etc. Conversely, if you are constructing the lookup anyway, perhaps in a longer-term shared lookup that is used by multiple operations: the O(1) nature of reading the dictionary makes it almost certain to be faster to use the dictionary lookup - and the "almost" caveat in there is simply to guard against pathological "what if" scenarios with extremely silly semantics; basically in any real world scenario you can delete the "almost" with high confidence.

Upvotes: 2

JonasH
JonasH

Reputation: 36629

As with many things, it depends.

For small collections, say 10 items, a plain loop over an array or list is usually the fastest option. This is because the runtime will likely be dominated by the time to fetch items from memory, and a plain array is about as cache friendly as you can get. LINQ involves some overhead, so is usually best to avoid when trying to get the best performance.

For larger collections a dictionary will be faster since it will scale better. You may also want to consider using a hashSet, possibly with a custom equality comparer for comparing items. Both will have constant time to check if an item exist, compared to the linear time for a regular unsorted array/list.

But in the majority of cases performance is less important than other concerns, like readability. And classes like dictionary, HashSet, or .Intersect are often more convenient and readable.

If you worry about performance the first step is to measure and/or profile your application. If you run this code once a second and it takes 1us to run it is just not worth spending any time to optimize. Just make sure you have good test environment with representative data sets so you can discover potential scaling problems before they hit production.

Upvotes: 1

Michael Kokorin
Michael Kokorin

Reputation: 504

When you are using List.Any - it searches through the collection to find an element. So the complexity of such search is O(n). If you are using Dictionary, then it uses O(1) search and access time to each specific element - so it will be much faster.

Upvotes: 0

Related Questions