检查列表中的任何项是否与另一个列表中的任何项匹配

Question

我的一个同事让我写一个一行代码来替换以下方法：

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想到了这个：

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

有更好的方法吗？

- grenade

Answer 1

考虑到LINQ，是的：

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

注意，除了使用Intersect将其转换为O(m)+O(n)而不是O(m*n)之外，使用Any比使用Count() > 0更有效 - 一旦找到第一个匹配项，您就知道答案了。

- Jon Skeet

---

这可能不是询问的正确场所，但既然我们正在谈论它，那么我在哪里可以阅读和学习有关LINQ方法性能考虑的内容呢？ - tafa

作为一个非C#人（我注意到了“算法”标签），出于兴趣而言，有什么保证这是线性的？毫无疑问，集合需要排序才能实现线性：它们已经排好序了吗？ - Steve Jessop

@Steve：它基本上使用了哈希集合——从userRoles构建哈希集合的摊销复杂度应该为O(m)，在哈希集合中查找resourceRoles中的每个项的复杂度总共应该为O(n)。 - Jon Skeet

哎呀，非在线算法也是存在的；-) 谢谢。 - Steve Jessop

Answer 2

你可以编写一个通用的扩展方法来处理许多情况。函数本身的实质只有一行代码。

/// <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();
}

较旧、效率较低的解决方案

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

我认为这也比当前答案更有效率（其实不是）。我需要检查获取EqualityComparer是否昂贵，但我愿意怀疑它。

---

您还可以扩展此函数以接受一个表达式，该表达式将评估要比较的属性，对于包含对象的可枚举对象。

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

- Zachary Dow

---

不，这比我的答案明显不高效，至少在时间上是这样的。它的时间复杂度是O(a*b)，而不是O(a+b)，其中a是源中项目的数量，b是其他项目的数量。尽管如此，这个算法的空间复杂度是O(1)，而我的算法是O(n)。 - Jon Skeet

@JonSkeet 我不得不再次确认一下，Intersect 在这种情况下确实好得多，甚至在某些最优情况下与 Any 相当。我肯定会重新修改答案，但 OP 应该将您的答案标记为已接受的答案。 - Zachary Dow