Krotki (lub tablice) jako klucze słownika w języku C #

Próbuję utworzyć tabelę wyszukiwania słownika w języku C #. Muszę przekształcić 3 krotki wartości w jeden ciąg. Próbowałem używać tablic jako kluczy, ale to nie zadziałało i nie wiem, co jeszcze zrobić. W tym momencie rozważam utworzenie Dictionary of Dictionaries of Dictionaries, ale prawdopodobnie nie byłby to zbyt ładny widok, chociaż tak bym to zrobił w javascript.

Jeśli korzystasz z .NET 4.0, użyj krotki:

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

Jeśli nie, możesz zdefiniować a Tuplei użyć go jako klucza. Krotki musi zastąpić GetHashCode, Equalsi IEquatable:

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

Pomiędzy podejściami opartymi na krotkach a zagnieżdżonymi słownikami prawie zawsze lepiej jest wybrać krotkę.

Z punktu widzenia konserwacji ,

• znacznie łatwiej jest zaimplementować funkcjonalność, która wygląda następująco:

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

  niż

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

  od strony callee. W drugim przypadku każde dodawanie, wyszukiwanie, usuwanie itp. Wymaga działania na więcej niż jednym słowniku.

• Ponadto, jeśli twój klucz złożony będzie wymagał w przyszłości jednego więcej (lub mniej) pola, będziesz musiał znacznie zmienić kod w drugim przypadku (słownik zagnieżdżony), ponieważ musisz dodać kolejne zagnieżdżone słowniki i kolejne sprawdzenia.

Z punktu widzenia wydajności najlepszym wnioskiem, jaki można wyciągnąć, jest samodzielne zmierzenie. Ale istnieje kilka teoretycznych ograniczeń, które możesz rozważyć wcześniej:

• W przypadku zagnieżdżonego słownika, posiadanie dodatkowego słownika dla każdego klucza (zewnętrznego i wewnętrznego) będzie wiązało się z pewnym narzutem pamięci (większym niż to, co wiązałoby się z utworzeniem krotki).

• W przypadku zagnieżdżonego słownika każda podstawowa czynność, taka jak dodawanie, aktualizacja, wyszukiwanie, usuwanie itp. Musi być wykonywana w dwóch słownikach. Teraz istnieje przypadek, w którym zagnieżdżone podejście słownikowe może być szybsze, tj. Gdy szukane dane są nieobecne, ponieważ słowniki pośrednie mogą ominąć pełne obliczanie i porównywanie kodu skrótu, ale z drugiej strony należy to sprawdzić w czasie, aby mieć pewność. W przypadku obecności danych powinno być wolniejsze, ponieważ wyszukiwania powinny być wykonywane dwukrotnie (lub trzykrotnie w zależności od zagnieżdżenia).

• Jeśli chodzi o podejście do krotek, krotki .NET nie są najbardziej wydajne, gdy mają być używane jako klucze w zestawach, ponieważ ich Equalsi GetHashCodeimplementacja powoduje pakowanie typów wartości .

Wybrałbym słownik oparty na krotkach, ale jeśli chciałbym uzyskać większą wydajność, użyłbym własnej krotki z lepszą implementacją.

Na marginesie, kilka kosmetyków może sprawić, że słownik będzie fajny:

1. Wywołania w stylu indeksatora mogą być dużo bardziej przejrzyste i intuicyjne. Np.

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

   Dlatego ujawnij niezbędne indeksatory w swojej klasie słownika, która wewnętrznie obsługuje wstawianie i wyszukiwanie.

2. Zaimplementuj również odpowiedni IEnumerableinterfejs i zapewnij Add(TypeA, TypeB, TypeC, string)metodę, która zapewni składnię inicjatora kolekcji, na przykład:

   new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
   { 
       { a, b, c, null }, 
       ...
   };

Jeśli korzystasz z języka C # 7, należy rozważyć użycie krotek wartości jako klucza złożonego. Krotki wartości zwykle oferują lepszą wydajność niż tradycyjne krotki referencyjne ( Tuple<T1, …>), ponieważ krotki wartości są typami wartości (strukturami), a nie typami odwołań, dzięki czemu unikają alokacji pamięci i kosztów wyrzucania elementów bezużytecznych. Ponadto oferują zwięzłą i bardziej intuicyjną składnię, umożliwiając nazywanie ich pól, jeśli sobie tego życzysz. Implementują również IEquatable<T>interfejs potrzebny dla słownika.

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();

Dobre, czyste, szybkie, łatwe i czytelne sposoby to:

• generowanie elementów członkowskich równości (Equals () i GetHashCode ()) dla bieżącego typu. Narzędzia takie jak ReSharper nie tylko tworzą metody, ale także generują kod niezbędny do sprawdzenia równości i / lub obliczenia kodu skrótu. Wygenerowany kod będzie bardziej optymalny niż realizacja krotki.
• po prostu utwórz prostą klasę klucza pochodzącą z krotki .

dodaj coś podobnego:

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

Możesz więc używać go ze słownikiem:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};

• Możesz go również używać w kontraktach
• jako klucz do łączenia się lub grupowania w linq
• idąc w ten sposób, nigdy nie pomylisz się z kolejnością Item1, Item2, Item3 ...
• nie musisz pamiętać ani zaglądać do kodu, aby zrozumieć, gdzie się udać, aby coś zdobyć
• nie ma potrzeby nadpisywania IStructuralEquatable, IStructuralComparable, IComparable, ITuple wszystkie one już tutaj

Jeśli z jakiegoś powodu naprawdę chcesz uniknąć tworzenia własnej klasy Tuple lub używania wbudowanej w .NET 4.0, istnieje jeszcze jedno możliwe podejście; możesz połączyć trzy kluczowe wartości razem w jedną wartość.

Na przykład, jeśli te trzy wartości są typami całkowitymi, które razem nie zajmują więcej niż 64 bity, można je połączyć w plik ulong.

W najgorszym przypadku zawsze możesz użyć łańcucha, o ile upewnisz się, że trzy składowe w nim zawarte są oddzielone jakimś znakiem lub sekwencją, która nie występuje wewnątrz składników klucza, na przykład z trzema liczbami, które możesz wypróbować:

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

Oczywiście takie podejście wiąże się z pewnym narzutem na kompozycję, ale w zależności od tego, do czego go używasz, może to być na tyle trywialne, że nie przejmuje się tym.

Zastąpiłbym twój Tuple odpowiednim GetHashCode i użył go jako klucza.

Dopóki przeciążasz odpowiednie metody, powinieneś zobaczyć przyzwoitą wydajność.

Oto krotka .NET w celach informacyjnych:

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

Jeśli twój konsumujący kod może poradzić sobie z interfejsem IDictionary <>, zamiast Dictionary, moim odruchem byłoby użycie SortedDictionary <> z niestandardową funkcją porównującą tablice, tj .:

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

I stwórzmy w ten sposób (używając int [] tylko dla konkretnego przykładu):

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