Check if any item in a list matches any item in another list

Question

A coleague asked me to write a one-liner to replace the following method:

public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles)
{
    foreach (var userRole in userRoles)
        foreach (var resourceRole in resourceRoles)
            if (resourceRole == userRole)
                return true;
    return false;
}

Resharper and I came up with this:

public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles)
{
    return userRoles.Where(resourceRoles.Contains).Count() > 0;
}

Is there a better way?

Mindymine

Answer 1

You could write a generic extension method that would handle many cases. The meat of the function itself is one line.

/// <summary>
/// Compares both lists to see if any item in the enumerable 
/// equals any item in the other enumerable. 
/// </summary>
public static bool AnyItem<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    return (comparer == null ? source.Intersect(other) : source.Intersect(other, comparer)).Any();
}

Older, Less efficient answer

public static bool AnyItem<T>(this IEnumerable<T> source, IEnumerable<T> other)
{
    return source.Any(s => other.Any(o => EqualityComparer<T>.Default.Equals(s, o)));
}

I think this is also more efficient than the current answer (It's not). I would have to check if getting the EqualityComparer is expensive, but I'm willing to doubt it.

---

You could also extend this function to accept an Expression that would evaluate what properties to compare for enumerables that contain objects.

public static bool AnyItem<T, TResult>(
        this IEnumerable<T> source, 
        IEnumerable<T> other, 
        Expression<Func<T, TResult>> compareProperty = null)
{
    if (compareProperty == null)
    {
        return source.Any(s => other.Any(o => EqualityComparer<T>.Default.Equals(s, o)));
    }

    return source.Any(s => other.Any(o => 
                    EqualityComparer<TResult>.Default.Equals(
                    s.GetPropertyValue(compareProperty),
                    o.GetPropertyValue(compareProperty))));
}

public static TValue GetPropertyValue<TTarget, TValue>(
    this TTarget target, Expression<Func<TTarget, TValue>> memberLamda)
{
    var memberSelectorExpression = memberLamda.Body as MemberExpression;
    var property = memberSelectorExpression?.Member as PropertyInfo;
    return (TValue)property?.GetValue(target);
}

Bonds

No, this is significantly less efficient than my answer, at least in time. It's O(a*b) instead of O(a+b), where a is the number of items in source and b is the number of items in other. This is O(1) in space where mine is O(n) though. – Atomic

@JonSkeet I had to double check you and it's actually remarkable how much better Intersect is in this case, it's even close in some of the optimal cases for Any. I'll rework the answer for sure, but OP should probably mark yours the accepted answer – Bonds

Answer 2

Given LINQ, yes:

return userRoles.Intersect(resourceRoles).Any();

Note that aside from the use of Intersect to turn it into O(m) + O(n) instead O(m * n), using Any is more efficient than using Count() > 0 - you know the answer as soon as you've found the first match.

Atomic

This may not be the right place to ask, but since we are talking about it; where can I read& learn about the performance considerations of LINQ methods. – Cardon

Speaking out of interest as a non-C# person (I caught the "algorithm" tag), what guarantees that this is linear? Surely the collections need to be sorted for that: are they? – Menarche

@Steve: It uses a hash set, basically - building a hash set from userRoles should be amortized O(m), and looking up each item from resourceRoles within the hash set should be O(n) in total. – Atomic