Tupel (oder Arrays) als Wörterbuchschlüssel in C #

109

Ich versuche, eine Wörterbuch-Nachschlagetabelle in C # zu erstellen. Ich muss ein 3-Tupel von Werten in eine Zeichenfolge auflösen. Ich habe versucht, Arrays als Schlüssel zu verwenden, aber das hat nicht funktioniert, und ich weiß nicht, was ich sonst tun soll. An dieser Stelle denke ich darüber nach, ein Wörterbuch mit Wörterbüchern zu erstellen, aber das wäre wahrscheinlich nicht sehr hübsch anzusehen, obwohl ich es so in Javascript machen würde.

AlexH
quelle

Antworten:

114

Wenn Sie mit .NET 4.0 arbeiten, verwenden Sie ein Tupel:

lookup = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();

Wenn nicht, können Sie ein Tupel definieren und dieses als Schlüssel verwenden. Das Tupel muss GetHashCode, Equals und IEquatable überschreiben:

struct Tuple<T, U, W> : IEquatable<Tuple<T,U,W>>
{
    readonly T first;
    readonly U second;
    readonly W third;

    public Tuple(T first, U second, W third)
    {
        this.first = first;
        this.second = second;
        this.third = third;
    }

    public T First { get { return first; } }
    public U Second { get { return second; } }
    public W Third { get { return third; } }

    public override int GetHashCode()
    {
        return first.GetHashCode() ^ second.GetHashCode() ^ third.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }
        return Equals((Tuple<T, U, W>)obj);
    }

    public bool Equals(Tuple<T, U, W> other)
    {
        return other.first.Equals(first) && other.second.Equals(second) && other.third.Equals(third);
    }
}
Hallgrim
quelle
6
Diese Struktur sollte auch IEquatable <Tuple <T, U, W >> implementieren. Auf diese Weise können Sie das Boxen vermeiden, wenn Equals () bei Hash-Code-Kollisionen aufgerufen wird.
Dustin Campbell
16
@jerryjvl und alle anderen, die dies von Google wie ich finden, implementiert das Tuple von .NET 4 gleich, damit es in einem Wörterbuch verwendet werden kann.
Scott Chamberlain
30
Ihre GetHashCodeImplementierung ist nicht sehr gut. Es ist unter Permutation der Felder unveränderlich.
CodesInChaos
2
Tupel sollte keine Struktur sein. Im Framework ist Tuple ein Referenztyp.
Michael Graczyk
5
@Thoraot - natürlich ist dein Beispiel falsch ... es sollte sein. Warum new object()sollte ein anderer gleich sein new object()? Es wird nicht nur ein direkter Referenzvergleich verwendet ... versuchen Sie:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Mike Marynowski
35

Zwischen auf Tupeln und verschachtelten Wörterbüchern basierenden Ansätzen ist es fast immer besser, sich für Tupel zu entscheiden.

Von Wartbarkeit Sicht ,

  • Es ist viel einfacher, eine Funktionalität zu implementieren, die wie folgt aussieht:

    var myDict = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();

    als

    var myDict = new Dictionary<TypeA, Dictionary<TypeB, Dictionary<TypeC, string>>>();

    von der Angerufenen Seite. Im zweiten Fall erfordert jede Hinzufügung, Suche, Entfernung usw. eine Aktion für mehr als ein Wörterbuch.

  • Wenn Ihr zusammengesetzter Schlüssel in Zukunft ein weiteres (oder weniger) Feld benötigt, müssen Sie im zweiten Fall (verschachteltes Wörterbuch) den Code erheblich ändern, da Sie weitere verschachtelte Wörterbücher und nachfolgende Überprüfungen hinzufügen müssen.

Aus Sicht der Leistung ist die beste Schlussfolgerung, die Sie erzielen können, die Messung selbst. Es gibt jedoch einige theoretische Einschränkungen, die Sie im Voraus berücksichtigen können:

  • Im Fall eines verschachtelten Wörterbuchs hat ein zusätzliches Wörterbuch für jeden Schlüssel (außen und innen) einen gewissen Speicheraufwand (mehr als das Erstellen eines Tupels).

  • Im Fall eines verschachtelten Wörterbuchs muss jede grundlegende Aktion wie Hinzufügen, Aktualisieren, Nachschlagen, Entfernen usw. in zwei Wörterbüchern ausgeführt werden. Jetzt gibt es einen Fall, in dem der Ansatz eines verschachtelten Wörterbuchs schneller sein kann, dh wenn die nachgeschlagenen Daten nicht vorhanden sind, da die Zwischenwörterbücher die vollständige Berechnung und den Vergleich des Hashcodes umgehen können. Andererseits sollte dies zeitlich festgelegt werden, um sicherzugehen. Bei Vorhandensein von Daten sollte diese langsamer sein, da die Suche zweimal (oder je nach Verschachtelung dreimal) durchgeführt werden sollte.

  • In Bezug auf den Tupel-Ansatz sind .NET-Tupel nicht die leistungsstärksten, wenn sie als Schlüssel in Mengen verwendet werden sollen, da ihre Implementierung Equalsund GetHashCodedas Boxen ein Boxen für Werttypen verursacht .

Ich würde mich für ein Tupel-basiertes Wörterbuch entscheiden, aber wenn ich mehr Leistung möchte, würde ich mein eigenes Tupel mit besserer Implementierung verwenden.


Nebenbei bemerkt, nur wenige Kosmetika können das Wörterbuch cool machen:

  1. Aufrufe im Indexer-Stil können viel sauberer und intuitiver sein. Zum Beispiel

    string foo = dict[a, b, c]; //lookup
    dict[a, b, c] = ""; //update/insertion
    

    Stellen Sie daher die erforderlichen Indexer in Ihrer Wörterbuchklasse bereit, die die Einfügungen und Suchvorgänge intern verarbeiten.

  2. Implementieren Sie außerdem eine geeignete IEnumerableSchnittstelle und stellen Sie eine Add(TypeA, TypeB, TypeC, string)Methode bereit , mit der Sie die Syntax für die Initialisierung von Sammlungen erhalten, z.

    new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
    { 
        { a, b, c, null }, 
        ...
    };
    
nawfal
quelle
Wäre die Indexersyntax bei verschachtelten Wörterbüchern nicht eher so : string foo = dict[a][b][c]?
Steven Rands
@StevenRands ja es wird sein.
Nawfal
1
@nawfal Kann ich das Tupelwörterbuch durchsuchen, wenn ich nur einen der Schlüssel habe, nicht alle? oder Kann ich dieses Diktat [a, b] mögen und dann [a, c] diktieren?
Khan Engineer
@ KhanEngineer Vieles davon hängt davon ab, was der beabsichtigte Zweck des Wörterbuchs ist oder wie Sie es verwenden möchten. Zum Beispiel möchten Sie durch einen Teil des Schlüssels einen Wert zurückerhalten a. Sie können einfach jedes Wörterbuch wie jede normale Sammlung iterieren und nach Schlüsseleigenschaften suchen, falls dies der Fall ist a. Wenn Sie das Element immer durch die erste Eigenschaft in diktieren möchten, können Sie das Wörterbuch besser als Wörterbuch der Wörterbücher entwerfen, wie in meiner Antwort und Abfrage wie gezeigt dict[a], wodurch Sie ein anderes Wörterbuch erhalten.
Nawfal
Wenn Sie mit "Suche nach nur einem Schlüssel" den Wert durch einen der Schlüssel zurückerhalten möchten, sollten Sie Ihr Wörterbuch besser als eine Art "beliebiges Schlüsselwörterbuch" umgestalten. Wenn Sie beispielsweise einen Wert 4für beide Schlüssel aund erhalten möchten b, können Sie ihn zu einem Standardwörterbuch machen und Werte wie dict[a] = 4und hinzufügen dict[b] = 4. Es ist möglicherweise nicht sinnvoll, wenn logischerweise Ihre aund beine Einheit sein sollte. In einem solchen Fall können Sie einen Benutzer definieren, IEqualityComparerder zwei Schlüsselinstanzen als gleich gleichsetzt, wenn eine ihrer Eigenschaften gleich ist. All dies kann generisch mit Reflexion erfolgen.
Nawfal
30

Wenn Sie sich in C # 7 befinden, sollten Sie Wertetupel als zusammengesetzten Schlüssel verwenden. Wertetupel bieten normalerweise eine bessere Leistung als die herkömmlichen Referenztupel ( Tuple<T1, …>), da Wertetupel Werttypen (Strukturen) und keine Referenztypen sind, sodass die Kosten für die Speicherzuweisung und die Speicherbereinigung vermieden werden. Außerdem bieten sie eine übersichtlichere und intuitivere Syntax, sodass ihre Felder auf Wunsch benannt werden können. Sie implementieren auch die IEquatable<T>für das Wörterbuch erforderliche Schnittstelle.

var dict = new Dictionary<(int PersonId, int LocationId, int SubjectId), string>();
dict.Add((3, 6, 9), "ABC");
dict.Add((PersonId: 4, LocationId: 9, SubjectId: 10), "XYZ");
var personIds = dict.Keys.Select(k => k.PersonId).Distinct().ToList();
Douglas
quelle
13

Die guten, sauberen, schnellen, einfachen und lesbaren Wege sind:

  • Generieren Sie Gleichheitsmitglieder (Equals () und GetHashCode ()) für den aktuellen Typ. Tools wie ReSharper erstellen nicht nur die Methoden, sondern generieren auch den erforderlichen Code für eine Gleichheitsprüfung und / oder zur Berechnung von Hash-Code. Der generierte Code ist optimaler als die Tupelrealisierung.
  • Erstellen Sie einfach eine einfache Schlüsselklasse, die von einem Tupel abgeleitet ist .

füge so etwas hinzu:

public sealed class myKey : Tuple<TypeA, TypeB, TypeC>
{
    public myKey(TypeA dataA, TypeB dataB, TypeC dataC) : base (dataA, dataB, dataC) { }

    public TypeA DataA => Item1; 

    public TypeB DataB => Item2;

    public TypeC DataC => Item3;
}

So können Sie es mit Wörterbuch verwenden:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};
  • Sie können es auch in Verträgen verwenden
  • als Schlüssel für Verknüpfungen oder Gruppierungen in linq
  • Auf diese Weise geben Sie niemals die Reihenfolge von Artikel1, Artikel2, Artikel3 ...
  • Sie müssen sich nicht an Code erinnern oder ihn untersuchen, um zu verstehen, wohin Sie gehen müssen, um etwas zu erhalten
  • IStructuralEquatable, IStructuralComparable, IComparable, ITuple müssen nicht alle hier überschrieben werden
gabba
quelle
1
Jetzt können Sie Ausdruck Körper Mitglieder verwenden, die noch sauberer sind, zBpublic TypeA DataA => Item1;
andrewtatham
7

Wenn Sie aus irgendeinem Grund wirklich vermeiden möchten, eine eigene Tuple-Klasse zu erstellen oder in .NET 4.0 zu verwenden, ist ein anderer Ansatz möglich. Sie können die drei Schlüsselwerte zu einem einzigen Wert zusammenfassen.

Wenn die drei Werte beispielsweise ganzzahlige Typen sind, die zusammen nicht mehr als 64 Bit benötigen, können Sie sie zu einem kombinieren ulong.

Im schlimmsten Fall können Sie immer eine Zeichenfolge verwenden, solange Sie sicherstellen, dass die drei darin enthaltenen Komponenten durch ein Zeichen oder eine Sequenz begrenzt sind, die nicht in den Komponenten des Schlüssels vorkommen, z. B. mit drei Zahlen, die Sie versuchen könnten:

string.Format("{0}#{1}#{2}", key1, key2, key3)

Dieser Ansatz ist offensichtlich mit einem gewissen Kompositionsaufwand verbunden, aber je nachdem, wofür Sie ihn verwenden, kann dies trivial genug sein, um sich nicht darum zu kümmern.

jerryjvl
quelle
6
Ich würde sagen, dass es stark vom Kontext abhängt; Wenn ich drei Ganzzahltypen kombinieren musste und die Leistung nicht kritisch war, funktioniert dies einwandfrei mit minimaler Wahrscheinlichkeit, einen Fehler zu machen. All dies ist ab .NET 4 natürlich völlig redundant, da Microsoft uns sofort (vermutlich korrekt!) Tupeltypen zur Verfügung stellen wird.
Jerryjvl
Sie können diese Methode sogar in Kombination mit a verwenden, JavaScriptSerializerum ein Array von Zeichenfolgen- und / oder Ganzzahltypen für Sie zu verketten . Auf diese Weise müssen Sie sich kein Trennzeichen selbst einfallen lassen.
Binki
3
Dies könnte echte chaotisch , wenn eine der Tasten ( key1, key2, key3) waren Saiten die deliminator (mit "#")
Greg
4

Ich würde Ihr Tupel mit einem richtigen GetHashCode überschreiben und es einfach als Schlüssel verwenden.

Solange Sie die richtigen Methoden überladen, sollten Sie eine anständige Leistung sehen.

John Gietzen
quelle
1
IComparable hat keinen Einfluss darauf, wie Schlüssel in einem Wörterbuch <TKey, TValue> gespeichert oder gespeichert werden. Dies geschieht alles über GetHashCode () und einen IEqualityComparer <T>. Durch die Implementierung von IEquatable <T> wird eine bessere Leistung erzielt, da das durch den Standard-EqualityComparer verursachte Boxen verringert wird, das auf die Funktion Equals (Objekt) zurückgreift.
Dustin Campbell
Ich wollte GetHashCode erwähnen, aber ich dachte, dass das Wörterbuch IComparable verwendet, falls die HashCodes identisch sind ... ich glaube, ich habe mich geirrt.
John Gietzen
3

Hier ist das .NET-Tupel als Referenz:

[Serializable] 
public class Tuple<T1, T2, T3> : IStructuralEquatable, IStructuralComparable, IComparable, ITuple {

    private readonly T1 m_Item1; 
    private readonly T2 m_Item2;
    private readonly T3 m_Item3; 

    public T1 Item1 { get { return m_Item1; } }
    public T2 Item2 { get { return m_Item2; } }
    public T3 Item3 { get { return m_Item3; } } 

    public Tuple(T1 item1, T2 item2, T3 item3) { 
        m_Item1 = item1; 
        m_Item2 = item2;
        m_Item3 = item3; 
    }

    public override Boolean Equals(Object obj) {
        return ((IStructuralEquatable) this).Equals(obj, EqualityComparer<Object>.Default);; 
    }

    Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer) { 
        if (other == null) return false;

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            return false; 
        }

        return comparer.Equals(m_Item1, objTuple.m_Item1) && comparer.Equals(m_Item2, objTuple.m_Item2) && comparer.Equals(m_Item3, objTuple.m_Item3); 
    }

    Int32 IComparable.CompareTo(Object obj) {
        return ((IStructuralComparable) this).CompareTo(obj, Comparer<Object>.Default);
    }

    Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer) {
        if (other == null) return 1; 

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            throw new ArgumentException(Environment.GetResourceString("ArgumentException_TupleIncorrectType", this.GetType().ToString()), "other");
        }

        int c = 0;

        c = comparer.Compare(m_Item1, objTuple.m_Item1); 

        if (c != 0) return c; 

        c = comparer.Compare(m_Item2, objTuple.m_Item2);

        if (c != 0) return c; 

        return comparer.Compare(m_Item3, objTuple.m_Item3); 
    } 

    public override int GetHashCode() { 
        return ((IStructuralEquatable) this).GetHashCode(EqualityComparer<Object>.Default);
    }

    Int32 IStructuralEquatable.GetHashCode(IEqualityComparer comparer) { 
        return Tuple.CombineHashCodes(comparer.GetHashCode(m_Item1), comparer.GetHashCode(m_Item2), comparer.GetHashCode(m_Item3));
    } 

    Int32 ITuple.GetHashCode(IEqualityComparer comparer) {
        return ((IStructuralEquatable) this).GetHashCode(comparer); 
    }
    public override string ToString() {
        StringBuilder sb = new StringBuilder();
        sb.Append("("); 
        return ((ITuple)this).ToString(sb);
    } 

    string ITuple.ToString(StringBuilder sb) {
        sb.Append(m_Item1); 
        sb.Append(", ");
        sb.Append(m_Item2);
        sb.Append(", ");
        sb.Append(m_Item3); 
        sb.Append(")");
        return sb.ToString(); 
    } 

    int ITuple.Size { 
        get {
            return 3;
        }
    } 
}
Michael Graczyk
quelle
3
Get Hash Code ist implementiert als ((item1 ^ item2) * 33) ^ item3
Michael Graczyk
2

Wenn Ihr konsumierender Code mit einer IDictionary <> -Schnittstelle anstelle von Dictionary auskommen kann, wäre mein Instinkt gewesen, ein SortedDictionary <> mit einem benutzerdefinierten Array-Vergleicher zu verwenden, dh:

class ArrayComparer<T> : IComparer<IList<T>>
    where T : IComparable<T>
{
    public int Compare(IList<T> x, IList<T> y)
    {
        int compare = 0;
        for (int n = 0; n < x.Count && n < y.Count; ++n)
        {
            compare = x[n].CompareTo(y[n]);
        }
        return compare;
    }
}

Und erstellen Sie so (mit int [] nur als konkretes Beispiel):

var dictionary = new SortedDictionary<int[], string>(new ArrayComparer<int>());
Mungfleisch
quelle