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

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#.

Answers


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++;
    }
}

Use a HashSet

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

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


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.


Need Your Help

How to create pretty URL's with a custom MVC Framework in PHP?

php model-view-controller frameworks pretty-urls

So, I am beginning the process of coding a PHP application website, which will be coded in the MVC architecture,but would like to implement the method of using Pretty URL's with it. Since I have n...

After Effect - Triangle Wave (JavaScript)

javascript geometry expression

I'm trying to control a parameter with AE expressions and I need a triangle wave. I've got this so far: