What is fastest way to find number of matches between arrays?

Question

Currently, I am testing every integer element against each other to find which ones match. The arrays do not contain duplicates within their own set. Also, the arrays are not always equal lengths. Are there any tricks to speed this up? I am doing this thousands of times, so it's starting to become a bottle neck in my program, which is in C#.

Answer 1

Use a HashSet

var set = new HashSet<int>(firstArray);
set.IntersectWith(secondArray);

The set now contains only the values that exist in both arrays.

Answer 2

You could use LINQ:

var query = firstArray.Intersect(secondArray);

Or if the arrays are already sorted you could iterate over the two arrays yourself:

int[] a = { 1, 3, 5 };
int[] b = { 2, 3, 4, 5 };

List<int> result = new List<int>();
int ia = 0;
int ib = 0;
while (ia < a.Length && ib < b.Length)
{
    if (a[ia] == b[ib])
    {
        result.Add(a[ia]);
        ib++;
        ia++;
    }
    else if (a[ia] < b[ib])
    {
        ia++;
    }
    else
    {
        ib++;
    }
}

Answer 3

If such a comparison is a bottleneck in your program, you are perhaps using an inappropriate data structure. The simplest way might be to keep your data sorted. Then for finding out the common entries, you would need to traverse both arrays only once. Another option would be to keep the data in a HashSet.