Geek asks and answers

Asymptotic behavior of IEnumerable.Intersect vs HashedSet.IntersectWith

I read a lot of posts and blogs about HashSet and LINQ Set Operations, and I get the impression that the linq intersection method internally uses the hashed set as the first set, and IEnumerable the second. Thus, the difference between them is equal to either O (n + m) for the intersection of linq, or O (n) for the hashed intersection of sets between two hashed sets. Can I get confirmation of this? Big O for LINQ intersection is not registered in MSDN.

+5
source share
1 answer

Well, this is implementation-specific, so theoretically this can change, but basically the difference is that with the help of HashSet.IntersectWithyou start with a hash set, so you only need to iterate over one collection.

“Obvious” implementations would mean the complexity of O (M + N) and O (N) for Intersectand IntersectWithrespectively - provided, of course, a decent hash code. I would be very surprised to see any other implementation, and of course I did not see any evidence that any version of .NET was sent with something else.

, Intersect HashSet<T>, , , . , , Intersect.

. Edulinq , MSDN. MSDN ( ), :

, , , Intersect , . , , . , , .

, :

  • It second, (, MoveNext() )
  • first - , " , ", MSDN
+3

More articles:


All Articles