c# - Linq Intersect bool 查询和性能

Question

我想根据特定属性检查 2 个列表中的任何元素是否相同，然后只返回 true、false。

现在我有:

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

但我猜这是如何工作的，它会创建一个新列表，然后检查列表中是否有任何内容。有没有一种方法可以只在第一个匹配的元素上返回 true ？最坏的情况是没有匹配的元素，它会在内部循环遍历整个列表。

Answer 1

Linq 的 Intersect() 方法将在内部为一个列表创建和使用一个 HashTable，然后遍历另一个列表以查看是否有任何交集，然后产生那些确实相交的元素 - 所以在大 O 术语中，如果完整列表被迭代，你有 O(m) + O(n) - 但迭代将在第一个产生的元素之后停止，因为 Any() 运算符 - 在最坏的情况下(没有交集)，这仍然需要在哈希表上进行 m 次查找，每次查找的时间复杂度为 O(1)，因此您的时间复杂度为 O(n) + O(m)。

这是非常有效的(至少在 Big O 方面你不能做得更好)并且当然试图做得更好你会牺牲很多可读性 - 直到你通过测量证明这种性能对你来说是一个问题我会去使用 Linq。