High Runtime per Dictionary.Add per una grande quantità di elementi

Question

Ho un C# -Applicazione che memorizza i dati da un file di testo in un dizionario-oggetto. La quantità di dati da memorizzare può essere piuttosto grande, quindi ci vuole un sacco di tempo per inserire le voci. Con molti elementi nel dizionario, la situazione peggiora ulteriormente, a causa del ridimensionamento dell'array interno, che memorizza i dati per il dizionario. Così ho inizializzato il dizionario con la quantità di elementi che verranno aggiunti, ma questo non ha alcun impatto sulla velocità.

Qui è la mia funzione:

private Dictionary<IdPair, Edge> AddEdgesToExistingNodes(HashSet<NodeConnection> connections) 
{ 
    Dictionary<IdPair, Edge> resultSet = new Dictionary<IdPair, Edge>(connections.Count); 

    foreach (NodeConnection con in connections) 
    { 
    ... 
    resultSet.Add(nodeIdPair, newEdge); 
    } 

    return resultSet; 
} 

Nel mio test, inserisco ~ 300k articoli. Ho controllato il tempo di esecuzione con ANTS Performance Profiler e ho rilevato che il tempo medio per resultSet.Add (...) non cambia quando inizializzo il dizionario con la dimensione necessaria. È lo stesso di quando inizializzo il dizionario con il nuovo dizionario(); (circa 0,256 ms in media per ogni aggiunta). Questo è sicuramente causato dalla quantità di dati nel dizionario (anche se l'ho inizializzato con la dimensione desiderata). Per i primi 20k articoli, il tempo medio per Aggiungi è di 0,03 ms per ogni articolo.

Qualche idea, come rendere più rapida l'aggiunta?

Grazie in anticipo, Frank

Ecco il mio IdPair-Struct:

public struct IdPair 
{ 
    public int id1; 
    public int id2; 

    public IdPair(int oneId, int anotherId) 
    { 
    if (oneId > anotherId) 
    { 
     id1 = anotherId; 
     id2 = oneId; 
    } 
    else if (anotherId > oneId) 
    { 
     id1 = oneId; 
     id2 = anotherId; 
    } 
    else 
     throw new ArgumentException("The two Ids of the IdPair can't have the same value."); 
    } 
} 

Answer 1

Dal momento che si dispone di una struttura, si ottiene l'implementazione predefinita di Equals() e GetHashCode(). Come altri hanno sottolineato, questo non è molto efficiente dal momento che utilizza la riflessione, ma non penso che la riflessione sia il problema.

La mia ipotesi è che i codici hash vengano distribuiti in modo non uniforme dal GetHashCode() predefinito, che potrebbe accadere, ad esempio, se l'implementazione predefinita restituisce un semplice XOR di tutti i membri (nel qual caso hash (a, b) = = hash (b, a)). Non riesco a trovare alcuna documentazione di come viene implementato ValueType.GetHashCode(), ma prova ad aggiungere

public override int GetHashCode() { 
    return oneId << 16 | (anotherId & 0xffff); 
} 

che potrebbe essere migliore.

Answer 2

IdPair è un struct, e non è stato sovrascritto o EqualsGetHashCode. Ciò significa che verrà utilizzata l'implementazione predefinita di tali metodi.

Per i tipi di valore, l'implementazione predefinita di Equals e GetHashCode utilizza la riflessione, che potrebbe causare scarse prestazioni. Prova a fornire la tua implementazione dei metodi e vedi se questo aiuta.

mia implementazione suggerito, potrebbe non essere esattamente quello che ti serve/vuoi:

public struct IdPair : IEquatable<IdPair> 
{ 
    // ... 

    public override bool Equals(object obj) 
    { 
     if (obj is IdPair) 
      return Equals((IdPair)obj); 

     return false; 
    } 

    public bool Equals(IdPair other) 
    { 
     return id1.Equals(other.id1) 
      && id2.Equals(other.id2); 
    } 

    public override int GetHashCode() 
    { 
     unchecked 
     { 
      int hash = 269; 
      hash = (hash * 19) + id1.GetHashCode(); 
      hash = (hash * 19) + id2.GetHashCode(); 
      return hash; 
     } 
    } 
}