CODEWITHSUNDEEP
c#linq
Shawn Mclean
Shawn Mclean

Reputation: 57469

Linq Intersect bool query and performance

I want to check if any elements in 2 lists are the same based on a specific property, then just return true, false.

Right now I have:

public bool CanEdit(List<RoleType> roles)
{
    var rolesThatCanEdit = new List<RoleType>{
                                   RoleType.Administrator, 
                                   RoleType.Editor
                           };
    //check if the roles can edit.
    return rolesThatCanEdit.Intersect(roles).Any();
}

But my guess how this works is that it will make a new list then just check if anything is in the list. Is there a way I can just return true on the first matched element? worst case is there is no matching elements and it will loop through the entire list internally.

Upvotes: 9

Views: 3211

Answers (4)

Ben Voigt
Ben Voigt

Reputation: 283624

Not only will it not compute the complete intersection, it will turn the second input list (the one that's not a this parameter on the extension method) into a hashtable to enable very fast repeated lookups. (There may be a performance difference between rolesThanCanEdit.Intersect(roles) vs roles.Intersect(rolesThatCanEdit))

Upvotes: 6

BrokenGlass
BrokenGlass

Reputation: 160862

Linq's Intersect() method will create and use a HashTable for one list internally, then iterate over the other list to see if there is any intersection, then yield those elements that do intersect - so in Big O terms you have O(m) + O(n) if the full list is iterated over - but iteration will stop after the first yielded element because of the Any() operator - still in the worst case (no intersection) this still requires m lookups on the Hashtable each of O(1) so you have O(n) + O(m).

This is pretty efficient (and you cannot do better at least in Big O terms) and certainly trying to do better you would sacrifice a lot readability - until you have proven by measuring that this performance is a problem for you I would go with Linq.

Upvotes: 11

Petar Ivanov
Petar Ivanov

Reputation: 93030

Use sets (HashSet<>) instead of lists and Linq.

Just put all the elements in a set and then iterate the other list and compare. This is O(n+m).

Upvotes: 0

sehe
sehe

Reputation: 392921

It is already optimal: the last chained extension will Early-Out and all the enumerators will get disposed without running to completion

Upvotes: 0

Related Questions