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

Question

I am currently testing each integer element against each other to find which ones match. Arrays do not contain duplicates within their own set. In addition, arrays are not always equal in length. Are there any tricks to speed this up? I do this thousands of times, so it starts to become the neck of a bottle in my program, which is in C #.

Answer 1

You can use LINQ:

var query = firstArray.Intersect(secondArray);

Or, if the arrays are already sorted, you can iterate over two arrays:

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 2

Use hashset

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

, .

Answer 3

If such a comparison is a bottleneck in your program, you may be using the wrong data structure. The easiest way is to keep the data sorted. Then, to find out common entries, you will need to go through both arrays only once. Another option is to save the data in a HashSet.