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在内部创建并使用一个列表,然后迭代另一个列表以查看是否存在任何交集,然后生成那些相交的元素 - 因此在Big O术语中,您有O(m)+ O(n)如果遍历完整列表 - 但由于Any()运算符,迭代将在第一个产生的元素之后停止- 仍然在最坏的情况下(没有交集),这仍然需要在Hashtable上查找每个O(1),因此你有O( n)+ O(m).

这非常有效(并且至少在Big O方面你不能做得更好)并且肯定会做得更好,你会牺牲很多可读性 - 直到你通过测量这个性能对你来说是一个问题来证明我会选择Linq.

Answer 2

它不仅不会计算完整的交集,它还会将第二个输入列表(不是this扩展方法的参数)转换为哈希表,以实现非常快速的重复查找.(rolesThanCanEdit.Intersect(roles)vs 之间可能存在性能差异roles.Intersect(rolesThatCanEdit))