Qual è il modo più veloce per trovare il numero di corrispondenze tra gli array?

Question

Attualmente, sto testando ogni elemento intero l'uno contro l'altro per trovare quelli corrispondenti. Gli array non contengono duplicati all'interno del proprio set. Inoltre, gli array non sono sempre di uguale lunghezza. Ci sono trucchi per accelerare? Lo sto facendo migliaia di volte, quindi sta iniziando a diventare un collo di bottiglia nel mio programma, che è in C#.

Answer 1

Utilizzare un HashSet

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

Il set contiene ora solo i valori che esistono in entrambi gli array.

Answer 2

Si potrebbe usare LINQ:

var query = firstArray.Intersect(secondArray); 

O se gli array sono già ordinati si potrebbe iterare i due array da soli:

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

Se tale confronto è un collo di bottiglia nel vostro programma, stai forse usando una struttura di dati inappropriata. Il modo più semplice potrebbe essere quello di mantenere ordinati i tuoi dati. Quindi, per trovare le voci comuni, è necessario attraversare entrambi gli array una sola volta. Un'altra opzione sarebbe mantenere i dati in un HashSet.