Какой самый быстрый способ найти количество совпадений между массивами?

Question

В настоящее время я тестирую каждый целочисленный элемент друг против друга, чтобы найти, какие из них совпадают. Массивы не содержат дубликатов в пределах их собственного набора. Кроме того, массивы не всегда равны длинам. Есть ли уловки, чтобы ускорить это? Я делаю это тысячи раз, поэтому он начинает превращаться в шею бутылки в моей программе, которая находится на C#.

Answer 1

Используйте HashSet

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

Набор теперь содержит только те значения, которые существуют в обоих массивах.

Answer 2

Вы можете использовать LINQ:

var query = firstArray.Intersect(secondArray); 

Или если массивы уже отсортированы можно перебирать двух массивов себя:

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

Если такое сравнение является узким местом в вашей программе, возможно, вы используете неподходящую структуру данных. Самый простой способ - сохранить сортировку данных. Затем, чтобы узнать общие записи, вам нужно будет проходить оба массива только один раз. Другой вариант - сохранить данные в HashSet.