Quel est le moyen le plus rapide pour trouver le nombre de correspondances entre les tableaux?

Question

Actuellement, je teste chaque élément entier l'un par rapport à l'autre pour trouver ceux qui correspondent. Les tableaux ne contiennent pas de doublons dans leur propre ensemble. En outre, les tableaux ne sont pas toujours des longueurs égales. Y a-t-il des astuces pour accélérer cela? Je le fais des milliers de fois, donc ça commence à devenir un goulot d'étranglement dans mon programme, qui est en C#.

Answer 1

Utilisez un HashSet

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

L'ensemble contient maintenant uniquement les valeurs qui existent dans les deux tableaux.

Answer 2

Vous pouvez utiliser LINQ:

var query = firstArray.Intersect(secondArray); 

Ou si les tableaux sont déjà triés, vous pouvez itérer sur les deux tableaux vous:

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

Si une telle comparaison est un goulot d'étranglement dans votre programme, vous utilisez peut-être une structure de données inappropriée. Le moyen le plus simple pourrait être de garder vos données triées. Ensuite, pour trouver les entrées communes, vous devrez traverser les deux tableaux une seule fois. Une autre option consisterait à conserver les données dans un HashSet.