Linq Intersect bool query and performance

Question

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.

Answer 1

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.

Answer 2

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))