High Runtime for Dictionary.Add para una gran cantidad de elementos

Question

Tengo una aplicación C# que almacena datos de un archivo de texto en un objeto de diccionario. La cantidad de datos que se almacenan puede ser bastante grande, por lo que lleva mucho tiempo insertar las entradas. Con muchos elementos en el Diccionario, empeora aún más, debido al cambio de tamaño de la matriz interna, que almacena los datos para el Diccionario. Así que inicié el diccionario con la cantidad de elementos que se agregarán, pero esto no tiene ningún impacto en la velocidad.

Aquí es mi función:

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; 
} 

En mis pruebas, inserto ~ 300k artículos. Comprobé el tiempo de ejecución con ANTS Performance Profiler y encontré que el tiempo promedio para resultSet.Add (...) no cambia cuando inicializo el diccionario con el tamaño necesario. Es lo mismo que cuando inicializo el Diccionario con el nuevo Diccionario(); (aproximadamente 0.256 ms en promedio para cada Add). Esto es definitivamente causado por la cantidad de datos en el Diccionario (AUNQUE lo inicialicé con el tamaño deseado). Para los primeros 20k artículos, el tiempo promedio para Add es de 0.03 ms para cada artículo.

¿Alguna idea de cómo hacer que la operación adicional sea más rápida?

Gracias de antemano, Frank

Aquí está mi 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

Puesto que usted tiene una estructura, se obtiene la implementación predeterminada de Iguales() y GetHashCode(). Como han señalado otros, esto no es muy eficiente ya que utiliza la reflexión, pero no creo que el reflejo sea el problema.

Supongo que sus códigos hash se distribuyen de forma desigual por GetHashCode() predeterminado, lo que podría suceder, por ejemplo, si la implementación predeterminada devuelve un XOR simple de todos los miembros (en cuyo caso hash (a, b) = = hash (b, a)). No puedo encontrar ninguna documentación de cómo se implementa ValueType.GetHashCode(), pero trate de añadir

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

que podría ser mejor.

Answer 2

IdPair es una struct, y no se ha anulado o EqualsGetHashCode. Esto significa que se usará la implementación predeterminada de esos métodos.

Para los tipos de valor, la implementación predeterminada de Equals y GetHashCode usa la reflexión, lo que puede dar como resultado un bajo rendimiento. Intente proporcionar su propia implementación de los métodos y vea si eso ayuda.

Mi aplicación sugerida, puede que no sea exactamente lo que necesita/quiere:

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; 
     } 
    } 
}