[ACCEPTED]-When using a LINQ Where clause on a Dictionary, how can I return a dictionary of the same type?-optimization

Accepted answer

Score: 10

Pretty sure you could just call ToDictionary 1 on the result of the Where call:

Dictionary<string, string> GetValidIds(Dictionary<string, string> salesPersons,
    IList<string> ids)
{
    return salesPersons
        .Where(p => ids.Contains(p.Key))
        .ToDictionary(p => p.Key, p => p.Value);
}

Score: 6

Interestingly, if you enumerate over the 18 dictionary (length N) first and check the list 17 (length M) for inclusion, then you get O(NM) performance.

You 16 could build a HashSet<> of the ids, but that seems 15 redundant since we already have a (pre-hashed) dictionary 14 available.

I would instead iterate over the 13 ids first; since dictionary lookup (by key) is 12 O(1), this gives O(M) performance - this 11 might, however, mean that you don't use 10 LINQ (since TryGetValue won't love LINQ (and introducing 9 a tuple is too much like hard work)...

    Dictionary<string, string> getValidIds(
            IDictionary<string, string> salesPersons,
            IEnumerable<string> ids) {
        var result = new Dictionary<string, string>();
        string value;
        foreach (string key in ids) {
            if (salesPersons.TryGetValue(key, out value)) {
                result.Add(key, value);
            }
        }
        return result;
    }

It 8 doesn't overly concern me that this is more 7 lines than the LINQ version; it removes 6 an O(N) of complexity...

Edit; the following 5 might work (I haven't tested it), but I think 4 it is an abuse of LINQ, and certainly won't 3 scale to PLINQ etc... use with extreme caution!! I 2 also believe the foreach approach simply has fewer 1 overheads, so will be quicker... anyway:

    Dictionary<string, string> getValidIds(
        IDictionary<string, string> salesPersons,
        IEnumerable<string> ids)
    {
        string value = null;
        return  (from key in ids
                where salesPersons.TryGetValue(key, out value) // HACK: v. dodgy
                select new { key, value })
                .ToDictionary(x=>x.key, x=>x.value);
    }

Score: 6

Seems to be a lot of fussing about looking 5 things up in the List. If the list only 4 contains a few elements, then no big deal. If 3 the List contains thousands of elements, you're 2 going to want O(1) lookups into it. HashSet 1 can provide this.

Dictionary<string, string> getValidIds(
  Dictionary<string, string> SalesPersons,
  List<string> ids
)
{
  HashSet<string> idsFast = new HashSet<string>(ids);
  Dictionary<string, string> result = SalesPersons
    .Where(kvp => idsFast.Contains(kvp.Key))
    .ToDictionary(kvp => kvp.Key, kvp => kvp.Value)
  return result;
}

Source: stackoverflow.com

[ACCEPTED]-When using a LINQ Where clause on a Dictionary, how can I return a dictionary of the same type?-optimization

Should I be concerned about .NET dictionary speed?

Draw Rectangle with XNA

Fastest way to fill an array with a single value

How can I unit test performance optimisations in C#?

Fast integer ABS function

Fastest method to remove Empty rows and Columns From Excel Files using Interop

Ok(null) vs NoContent() in ASP.NET Core - which is more efficient?

My Bezier curve code is too slow. How can I fix it?

How to choose and optimize oracle indexes?

GCC C++ "Hello World" program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?