Efficient data structure to find intersection of two lists

Question

I have two very large List<List<int>> A and B. I need to find intersection in between each element of those lists.

A[0] = { 1, 2, 3};
B[0] = {2, 3, 4};

Intersection = { 2, 3 };

My implementation:

List<int> intersection = A[0].Intersection(B[0]).ToList();

This solution takes very long time to execute. I am wondering if there are any better way to do this and any more efficient data structure I can use to perform it in better time.

Thanks!

Answer 1

You should use a Hashset for this, in C# HashSet<T>. Lookups in hashsets are O(1) (if decent hashing function and using an array underneath) as opposed to O(n) for lists.

Using Linq in C# you basically get this "built-in": Intersect() will use a hashset internally to compute the intersection in O(n) instead of O(n^2) if using two lists.

var intersection = a.Intersect(b).ToList();

Answer 2

Code sample using HashSet(T).IntersectWith:

HashSet<string> lst1 = new HashSet<string> 

     { "id1", "id2", "id3" };

HashSet<string> lst2 = new HashSet<string> 

     { "id2", "id3", "id4" };

// what happens is that, lst1 will be modified by only leaving the intersect items
lst1.IntersectWith(lst2);

PS: I used the sample for String, but you can utilize your own integer values.