查找数组之间匹配数的最快方法是什么？

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

目前,我正在测试每个整数元素,以找出哪些匹配。数组在其自己的集合中不包含重复项。此外,阵列并不总是相等的长度。有什么技巧可以加速吗?我这样做了数千次,所以它开始成为我的程序的瓶颈,这是在C#中。

3 个解决方案

#1

You could use LINQ:

您可以使用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++;
    }
}

#2

Use a HashSet

使用HashSet

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

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

该集现在仅包含两个数组中存在的值。

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

如果这样的比较是程序中的瓶颈,那么您可能正在使用不适当的数据结构。最简单的方法可能是保持数据的排序。然后,为了找出公共条目,您只需要遍历两个数组。另一种选择是将数据保存在HashSet中。

#1