Increasing performance when comparing two lists

c#, list, performance

Solution

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)

Problem

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?

Original source