C# Similarities of two arrays

Question

There must be an better way to do this, I'm sure...

// Simplified code
var a = new List<int>() { 1, 2, 3, 4, 5, 6 };
var b = new List<int>() { 2, 3, 5, 7, 11 };
var z = new List<int>();
for (int i = 0; i < a.Count; i++)
    if (b.Contains(a[i]))
        z.Add(a[i]);
// (z) contains all of the numbers that are in BOTH (a) and (b), i.e. { 2, 3, 5 }

I don't mind using the above technique, but I want something fast and efficient (I need to compare very large Lists<> multiple times), and this appears to be neither! Any thoughts?

Edit: As it makes a difference - I'm using .NET 4.0, the initial arrays are already sorted and don't contain duplicates.

Answer 1

You could use IEnumerable.Intersect.

var z = a.Intersect(b);

which will probably be more efficient than your current solution.

note you left out one important piece of information - whether the lists happen to be ordered or not. If they are then a couple of nested loops that pass over each input array exactly once each may be faster - and a little more fun to write.

Edit In response to your comment on ordering:

first stab at looping - it will need a little tweaking on your behalf but works for your initial data.

    int j = 0;
    foreach (var i in a)
    {
        int x = b[j];
        while (x < i)
        {
            if (x == i)
            {
                z.Add(b[j]);
            }
            j++;
            x = b[j];
        }
    }

this is where you need to add some unit tests ;)

Edit final point - it may well be that Linq can use SortedList to perform this intersection very efficiently, if performance is a concern it is worth testing the various solutions. Dont forget to take the sorting into account if you load your data in an un-ordered manner.

One Final Edit because there has been some to and fro on this and people may be using the above without properly debugging it I am posting a later version here:

        int j = 0;
        int b1 = b[j];
        foreach (var a1 in a)
        {
            while (b1 <= a1)
            {
                if (b1 == a1)
                    z1.Add(b[j]);
                j++;
                if (j >= b.Count)
                    break;
                b1 = b[j];
            }
        }