2010-05-05 11 views
5

Ich habe eine C# -Application, die Daten aus einer Textdatei in einem Dictionary-Objekt speichert. Die Menge der zu speichernden Daten kann ziemlich groß sein, so dass es viel Zeit kostet, die Einträge einzufügen. Bei vielen Elementen im Dictionary wird es aufgrund der Größenanpassung des internen Arrays, das die Daten für das Dictionary speichert, noch schlimmer. Also initialisierte ich das Dictionary mit der Anzahl der Items, die hinzugefügt werden, aber das hat keinen Einfluss auf die Geschwindigkeit.Hohe Laufzeit für Dictionary.Add für eine große Anzahl von Elementen

Hier ist meine Funktion:

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

In meinen Tests, ich einfügen ~ 300k Artikel. Ich habe die Laufzeit mit ANTS Performance Profiler überprüft und festgestellt, dass sich die durchschnittliche Zeit für resultSet.Add (...) nicht ändert, wenn ich das Dictionary mit der benötigten Größe initialisiere. Es ist das gleiche wie wenn ich das Dictionary mit neuem Dictionary() initialisiere; (ungefähr 0,256 ms im Durchschnitt für jeden Add). Dies wird definitiv durch die Menge der Daten im Dictionary verursacht (ALTHOUGH ich initialisierte es mit der gewünschten Größe). Für die ersten 20 k Elemente beträgt die durchschnittliche Zeit für Add 0,03 ms für jedes Element.

Irgendeine Idee, wie man die Add-Operation schneller macht?

Vielen Dank im Voraus, Frank

ist hier mein 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."); 
    } 
} 
+6

Überschreiben Sie 'Equals' und' GetHashCode' in Ihrer 'IdPair' Klasse? Wenn ja, erzeugt Ihr 'GetHashCode'-Algorithmus eine ordentliche Verteilung der Hashes? – LukeH

+0

IdPair ist nur eine Struktur mit einem Konstruktor. Ich habe es meiner Frage hinzugefügt – Aaginor

Antwort

9

Da Sie eine Struktur haben, erhalten Sie die Standardimplementierung von Equals() und GetHashCode(). Wie andere darauf hingewiesen haben, ist dies nicht sehr effizient, da es Reflektion verwendet, aber ich denke nicht, dass die Reflexion das Problem ist.

Meine Vermutung ist, dass Ihr Hash-Codes ungleichmäßig durch den Standard verteilt bekommen GetHashCode(), die zum Beispiel passieren könnte, wenn die Standardimplementierung einen einfachen XOR aller Mitglieder zurückzugibt (in diesem Fall Hash (a, b) = = Hash (b, a)). Ich kann keine Dokumentation finden, wie ValueType.GetHashCode() implementiert ist, aber versuchen

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

Zugabe, die besser sein könnten.

+0

Perfect rate! Ihre kleine Hash-Funktion reduziert die Zeit für den Vorgang auf ~ 0.02 ms im Durchschnitt für jeden Add. – Aaginor

7

IdPair ein struct ist, und Sie haben nicht Equals oder GetHashCode außer Kraft gesetzt. Dies bedeutet, dass die Standardimplementierung dieser Methoden verwendet wird.

Bei Werttypen verwendet die Standardimplementierung Equals und GetHashCode Reflektion, was wahrscheinlich zu schlechter Leistung führt. Versuchen Sie, Ihre eigene Implementierung der Methoden zur Verfügung zu stellen und sehen Sie, ob das hilft.

Meine vorgeschlagene Implementierung, könnte es nicht genau das, was Sie brauchen/wollen:

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

Vielen Dank, Luke. Die (Standard) Hashfunktion war das Problem. Mit Ihrer Lösung habe ich die Betriebszeit im Durchschnitt für jeden Add auf ~ 0,03 ms verkürzt. Dies ist ein wenig langsamer als Erikkallens Lösung, aber viel besser als vorher. Bemerkenswert ist, dass das Einstellen der Dictionary-Größe im Voraus keinen (Zeit-) Effekt hat. – Aaginor

Verwandte Themen