Increasing performance when comparing two lists

Question

What options do I have when it comes to comparing items in two lists? I'm having some performance issues, and I would like to know if there are any faster alternatives:

int[] foo = { 1, 2, 3, 4, 5 };
int[] bar = { 6, 7, 8, 9, 1 };

var result = foo.Any(x => bar.Contains(x));

Regardless if I use the lambda methods or use a foreach on my own, I assume that the performance loss will still be O(N^2). Can I do anything to affect that?

Answer 1

You can use Enumerable.Intersect:

var result = foo.Intersect(bar).Any();

That creates Set<T> from bar items and then enumerates foo until first match found. Internally that looks like:

Set<int> set = new Set<int>();

foreach (int local in bar) // M times
    set.Add(local); // O(1)

foreach (int value in foo) // N times max
{
    if (!set.Remove(value)) // O(1)
        continue;

    yield return value;
}

As Patryk Ćwiek correctly pointed, that gives you O(N+M) instead of O(N*M)

Answer 2

You can use a Hashset:

int[] foo = { 1, 2, 3, 4, 5 };
int[] bar = { 6, 7, 8, 9, 1 };
var hashSet = new Hashset<int>(bar);
var result = foo.Any(x => hashSet.Contains(x));

Or you can use Except with Any like this:

var result =  !foo.Except(bar).Any();

I bet that is race with the Sergey's solution :p