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


109

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.

Odpowiedzi:


113

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

6
Ta struktura powinna również implementować IEquatable <Tuple <T, U, W >>. W ten sposób można uniknąć pudełkowania, gdy Equals () jest wywoływana w przypadku kolizji kodu skrótu.
Dustin Campbell

16
@jerryjvl i wszyscy inni, którzy znajdą to przez Google, tak jak ja, Tuple .NET 4 implementuje równa się, więc może być używany w słowniku.
Scott Chamberlain

30
Twoja GetHashCodeimplementacja nie jest zbyt dobra. Jest niezmienna w przypadku permutacji pól.
CodesInChaos

2
Krotka nie powinna być strukturą. We frameworku Tuple jest typem referencyjnym.
Michael Graczyk

5
@Thoraot - oczywiście twój przykład jest fałszywy ... tak powinno być. Dlaczego miałby new object()być równy drugiemu new object()? To nie tylko proste porównanie referencyjne ... spróbuj:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Mike Marynowski

35

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

W przypadku zagnieżdżonych słowników, nie miałby indekser składnia być bardziej tak: string foo = dict[a][b][c]?
Steven Rands

@StevenRands tak będzie.
nawfal

1
@nawfal Czy mogę przeszukiwać słownik krotek, jeśli mam tylko jeden klucz, a nie wszystkie? lub Czy mogę zrobić jak to dict [a, b], a następnie dict [a, c]?
Khan Engineer

@KhanEngineer Wiele zależy od tego, jaki jest cel słownika lub jak zamierzasz go używać. Dla np, chcesz uzyskać wartości powrotem przez część klucza a. Możesz po prostu iterować dowolny słownik, tak jak każdą normalną kolekcję i sprawdzić właściwość klucza, jeśli tak jest a. Jeśli zawsze chcesz uzyskać pozycję w dictwie według pierwszej właściwości, możesz lepiej zaprojektować słownik jako słownik słowników, jak pokazano w mojej odpowiedzi i zapytaniu, na przykład dict[a], co daje inny słownik.
nawfal

Jeśli przez „szukaj tylko jednym kluczem” masz na myśli odzyskanie wartości za pomocą któregokolwiek z posiadanych kluczy, lepiej przeprojektuj swój słownik jako coś w rodzaju „dowolnego słownika kluczy”. Na przykład, jeśli chcesz uzyskać wartość 4dla obu kluczy ai b, możesz uczynić go standardowym słownikiem i dodać wartości takie jak dict[a] = 4i dict[b] = 4. Może to nie mieć sensu, jeśli logicznie twoja ai bpowinna być jedna jednostka. W takim przypadku można zdefiniować niestandardowy, IEqualityComparerktóry zrównuje dwa wystąpienia kluczy, jeśli którakolwiek z ich właściwości jest równa. Wszystko to można ogólnie zrobić z refelkcją.
nawfal

30

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

13

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

1
Teraz możesz używać wyrazistych członków, nawet czyściejszych, np.public TypeA DataA => Item1;
andrewtatham

7

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.


6
Powiedziałbym jednak, że zależy to silnie od kontekstu; Gdybym miał do połączenia trzy typy liczb całkowitych, a wydajność nie byłaby krytyczna, działa to doskonale z minimalną szansą na popełnienie błędu. Oczywiście wszystko to jest całkowicie zbędne od .NET 4, ponieważ Microsoft będzie dostarczał nam (prawdopodobnie poprawne!) Typy krotek po wyjęciu z pudełka.
jerryjvl

Możesz nawet użyć tej metody w połączeniu z a, JavaScriptSerializeraby połączyć za siebie tablicę typów ciągów i / lub liczb całkowitych. W ten sposób nie musisz samodzielnie wymyślać znaku separatora.
binki

3
To może dostać prawdziwe Messy jeśli jeden z klawiszy ( key1, key2, key3) były ciągi zawierające deliminator ( "#")
Greg

4

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

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


1
IComparable nie ma wpływu na sposób przechowywania lub umieszczania kluczy w Dictionary <TKey, TValue>. Wszystko to odbywa się za pomocą GetHashCode () i IEqualityComparer <T>. Implementacja IEquatable <T> zapewni lepszą wydajność, ponieważ złagodzi opakowanie spowodowane przez domyślną EqualityComparer, która powraca do funkcji Equals (obiekt).
Dustin Campbell

Miałem wspomnieć o GetHashCode, ale pomyślałem, że Słownik użył IComparable w przypadku, gdy HashCodes są Identyczne ... chyba się myliłem.
John Gietzen

3

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

3
Pobierz kod skrótu jest zaimplementowany jako ((item1 ^ item2) * 33) ^ item3
Michael Graczyk

2

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>());
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.