Find number of common elements between two lists or hashsets with millions of elements

Question

What are some performant ways to determine the number of common elements between two lists or hashsets, which may have millions of values, in c#?

Maybe a solution involving LINQ? – Brandon Buck Mar 28 '13 at 19:57 — Brandon Buck, Mar 28 '13 at 19:57

score 7 · Accepted Answer · edited Mar 28 '13 at 20:31

The best performance is going to be available with HashSets. You can use the IntersectWith method.

// assuming HashSet<T> hashSetA
//     and an IEnumerable<T> collectionB
hashSetA.IntersectWith(collectionB);

The hashset-based solution gives O(n) performance which is pretty much as good as it gets.

The next best thing would be to sort the two lists and then iterate linearly in lock-step over the two lists, selecting the common elements, which yeilds O(nlogn) performance.

paparazzo · Answer 2 · 2013-03-28T20:12:54.147

1

HashSet IntersectWith

HashSet.IntersectWith Method

For comparing two List I would create HashSet of the larger

HashSet Constructor (IEnumerable)

edited Mar 28 '13 at 20:12

answered Mar 28 '13 at 19:58

paparazzo

44,497
23
105
176

score 0 · Answer 3 · edited May 23 '17 at 12:21

0

Using Except

Difference between two lists

edited May 23 '17 at 12:21

Community

1
1

answered Mar 28 '13 at 20:01

Ramesh Rajendran

37,412
45
153
234

I believe you have the functions confused with Java.. The question is about C#. – Mike Dinescu Mar 28 '13 at 20:02
But We can use retainAll and Except in c# – Ramesh Rajendran Mar 28 '13 at 20:05
I'm sorry. I'm just not following. The `retainAll` function is not defined on any BCL class in .NET.. – Mike Dinescu Mar 28 '13 at 20:12

Find number of common elements between two lists or hashsets with millions of elements

3 Answers3