Słownik kluczy złożonych

Mam kilka obiektów na liście, powiedzmy, List<MyClass>a MyClass ma kilka właściwości. Chciałbym utworzyć indeks listy w oparciu o 3 właściwości MyClass. W tym przypadku 2 właściwości to int, a jedna właściwość to data i godzina.

Zasadniczo chciałbym móc zrobić coś takiego:

Dictionary< CompositeKey , MyClass > MyClassListIndex = Dictionary< CompositeKey , MyClass >();
//Populate dictionary with items from the List<MyClass> MyClassList
MyClass aMyClass = Dicitonary[(keyTripletHere)];

Czasami tworzę wiele słowników na liście, aby indeksować różne właściwości klas, które posiada. Nie jestem jednak pewien, jak najlepiej obsługiwać klucze kompozytowe. Rozważałem zrobienie sumy kontrolnej trzech wartości, ale grozi to kolizjami.

Powinieneś używać krotek. Są one odpowiednikiem klasy CompositeKey, ale Equals () i GetHashCode () zostały już zaimplementowane.

var myClassIndex = new Dictionary<Tuple<int, bool, string>, MyClass>();
//Populate dictionary with items from the List<MyClass> MyClassList
foreach (var myObj in myClassList)
    myClassIndex.Add(Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString), myObj);
MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];

Lub za pomocą System.Linq

var myClassIndex = myClassList.ToDictionary(myObj => Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString));
MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];

Jeśli nie musisz dostosowywać obliczania skrótu, łatwiej jest używać krotek.

Jeśli istnieje wiele właściwości, które chcesz uwzględnić w kluczu złożonym, nazwa typu krotki może stać się dość długa, ale możesz ją skrócić, tworząc własną klasę wywodzącą się z klasy Tuple <...>.

** wydano w 2017 r. **

Jest nowa opcja zaczynająca się od C # 7: krotki wartości . Pomysł jest ten sam, ale składnia jest inna, lżejsza:

Typ Tuple<int, bool, string>staje się (int, bool, string), a wartość Tuple.Create(4, true, "t")staje się (4, true, "t").

W przypadku krotek wartości możliwe jest również nazwanie elementów. Zwróć uwagę, że wyniki są nieco inne, więc możesz chcieć wykonać pewne testy porównawcze, jeśli mają dla Ciebie znaczenie.

Najlepszym sposobem, jaki mogłem wymyślić, jest utworzenie struktury CompositeKey i upewnienie się, że nadpisujesz metody GetHashCode () i Equals (), aby zapewnić szybkość i dokładność podczas pracy z kolekcją:

class Program
{
    static void Main(string[] args)
    {
        DateTime firstTimestamp = DateTime.Now;
        DateTime secondTimestamp = firstTimestamp.AddDays(1);

        /* begin composite key dictionary populate */
        Dictionary<CompositeKey, string> compositeKeyDictionary = new Dictionary<CompositeKey, string>();

        CompositeKey compositeKey1 = new CompositeKey();
        compositeKey1.Int1 = 11;
        compositeKey1.Int2 = 304;
        compositeKey1.DateTime = firstTimestamp;

        compositeKeyDictionary[compositeKey1] = "FirstObject";

        CompositeKey compositeKey2 = new CompositeKey();
        compositeKey2.Int1 = 12;
        compositeKey2.Int2 = 9852;
        compositeKey2.DateTime = secondTimestamp;

        compositeKeyDictionary[compositeKey2] = "SecondObject";
        /* end composite key dictionary populate */

        /* begin composite key dictionary lookup */
        CompositeKey compositeKeyLookup1 = new CompositeKey();
        compositeKeyLookup1.Int1 = 11;
        compositeKeyLookup1.Int2 = 304;
        compositeKeyLookup1.DateTime = firstTimestamp;

        Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup1]);

        CompositeKey compositeKeyLookup2 = new CompositeKey();
        compositeKeyLookup2.Int1 = 12;
        compositeKeyLookup2.Int2 = 9852;
        compositeKeyLookup2.DateTime = secondTimestamp;

        Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup2]);
        /* end composite key dictionary lookup */
    }

    struct CompositeKey
    {
        public int Int1 { get; set; }
        public int Int2 { get; set; }
        public DateTime DateTime { get; set; }

        public override int GetHashCode()
        {
            return Int1.GetHashCode() ^ Int2.GetHashCode() ^ DateTime.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            if (obj is CompositeKey)
            {
                CompositeKey compositeKey = (CompositeKey)obj;

                return ((this.Int1 == compositeKey.Int1) &&
                        (this.Int2 == compositeKey.Int2) &&
                        (this.DateTime == compositeKey.DateTime));
            }

            return false;
        }
    }
}

Artykuł MSDN na temat GetHashCode ():

http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

A co powiesz Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Umożliwiłoby to:

MyClass item = MyData[8][23923][date];

Możesz przechowywać je w strukturze i używać tego jako klucza:

struct CompositeKey
{
  public int value1;
  public int value2;
  public DateTime value3;
}

Link do kodu skrótu: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Teraz, gdy pojawił się VS2017 / C # 7, najlepszą odpowiedzią jest użycie ValueTuple:

// declare:
Dictionary<(string, string, int), MyClass> index;

// populate:
foreach (var m in myClassList) {
  index[(m.Name, m.Path, m.JobId)] = m;
}

// retrieve:
var aMyClass = index[("foo", "bar", 15)];

Zdecydowałem się zadeklarować słownik za pomocą anonimowej ValueTuple (string, string, int). Ale mogłem nadać im imiona (string name, string path, int id).

Perfekcyjnie, nowa ValueTuple jest szybsza niż Tuple w, GetHashCodeale wolniejsza w Equals. Myślę, że musiałbyś przeprowadzić kompletne eksperymenty od końca do końca, aby dowiedzieć się, który jest naprawdę najszybszy w Twoim scenariuszu. Ale kompleksowa wygoda i składnia języka dla ValueTuple sprawiają, że wygrywa.

// Perf from https://gist.github.com/ljw1004/61bc96700d0b03c17cf83dbb51437a69
//
//              Tuple ValueTuple KeyValuePair
//  Allocation:  160   100        110
//    Argument:   75    80         80    
//      Return:   75   210        210
//        Load:  160   170        320
// GetHashCode:  820   420       2700
//      Equals:  280   470       6800

Natychmiast przychodzą na myśl dwa podejścia:

1. Zrób tak, jak zasugerował Kevin i napisz strukturę, która będzie służyć jako twój klucz. Upewnij się, że ta struktura została zaimplementowana IEquatable<TKey>i nadpisano jej Equalsi GetHashCodemetody *.

2. Napisz klasę, która wewnętrznie korzysta z zagnieżdżonych słowników. Coś jak: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... ta klasa będzie mieć wewnętrznie członek rodzaju Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>i naraziłoby metod, takich jak this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3)itp

* Słowo o tym, czy nadpisywanie Equalsmetody jest konieczne: podczas gdy prawdą jest, żeEquals metoda dla struktury domyślnie porównuje wartość każdego elementu członkowskiego, robi to przy użyciu refleksji - która z natury wiąże się z kosztami wydajności - i dlatego nie jest bardzo odpowiednia implementacja czegoś, co ma być używane jako klucz w słowniku (w każdym razie moim zdaniem). Zgodnie z dokumentacją MSDN dotyczącą ValueType.Equals:

Domyślna implementacja metody Equals używa odbicia do porównania odpowiednich pól obj i tego wystąpienia. Zastąp metodę Equals dla określonego typu, aby poprawić wydajność metody i dokładniej reprezentować koncepcję równości dla typu.

Jeśli klucz jest częścią klasy, użyj KeyedCollection.
Jest to miejsce, w Dictionaryktórym klucz pochodzi z obiektu.
Pod okładkami jest słownik.
Nie trzeba powtarzać klucza w Keyi Value.
Po co ryzykować, klucz nie jest taki sam Keyjak w Value.
Nie musisz kopiować tych samych informacji w pamięci.

KeyedCollection Class

Indeksator, aby uwidocznić klucz złożony

    using System.Collections.ObjectModel;

    namespace IntIntKeyedCollection
    {
        class Program
        {
            static void Main(string[] args)
            {
                Int32Int32DateO iid1 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52));
                Int32Int32DateO iid2 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52));
                if (iid1 == iid2) Console.WriteLine("same");
                if (iid1.Equals(iid2)) Console.WriteLine("equals");
                // that are equal but not the same I don't override = so I have both features

                Int32Int32DateCollection int32Int32DateCollection = new Int32Int32DateCollection();
                // dont't have to repeat the key like Dictionary
                int32Int32DateCollection.Add(new Int32Int32DateO(0, 0, new DateTime(2008, 5, 1, 8, 30, 52)));
                int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52)));
                int32Int32DateCollection.Add(iid1);
                //this would thow a duplicate key error
                //int32Int32DateCollection.Add(iid2);
                //this would thow a duplicate key error
                //int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52)));
                Console.WriteLine("count");
                Console.WriteLine(int32Int32DateCollection.Count.ToString());
                // reference by ordinal postion (note the is not the long key)
                Console.WriteLine("oridinal");
                Console.WriteLine(int32Int32DateCollection[0].GetHashCode().ToString());
                // reference by index
                Console.WriteLine("index");
                Console.WriteLine(int32Int32DateCollection[0, 1, new DateTime(2008, 6, 1, 8, 30, 52)].GetHashCode().ToString());
                Console.WriteLine("foreach");
                foreach (Int32Int32DateO iio in int32Int32DateCollection)
                {
                    Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1));
                }
                Console.WriteLine("sorted by date");
                foreach (Int32Int32DateO iio in int32Int32DateCollection.OrderBy(x => x.Date1).ThenBy(x => x.Int1).ThenBy(x => x.Int2))
                {
                    Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1));
                }
                Console.ReadLine();
            }
            public class Int32Int32DateCollection : KeyedCollection<Int32Int32DateS, Int32Int32DateO>
            {
                // This parameterless constructor calls the base class constructor 
                // that specifies a dictionary threshold of 0, so that the internal 
                // dictionary is created as soon as an item is added to the  
                // collection. 
                // 
                public Int32Int32DateCollection() : base(null, 0) { }

                // This is the only method that absolutely must be overridden, 
                // because without it the KeyedCollection cannot extract the 
                // keys from the items.  
                // 
                protected override Int32Int32DateS GetKeyForItem(Int32Int32DateO item)
                {
                    // In this example, the key is the part number. 
                    return item.Int32Int32Date;
                }

                //  indexer 
                public Int32Int32DateO this[Int32 Int1, Int32 Int2, DateTime Date1]
                {
                    get { return this[new Int32Int32DateS(Int1, Int2, Date1)]; }
                }
            }

            public struct Int32Int32DateS
            {   // required as KeyCollection Key must be a single item
                // but you don't really need to interact with Int32Int32DateS directly
                public readonly Int32 Int1, Int2;
                public readonly DateTime Date1;
                public Int32Int32DateS(Int32 int1, Int32 int2, DateTime date1)
                { this.Int1 = int1; this.Int2 = int2; this.Date1 = date1; }
            }
            public class Int32Int32DateO : Object
            {
                // implement other properties
                public Int32Int32DateS Int32Int32Date { get; private set; }
                public Int32 Int1 { get { return Int32Int32Date.Int1; } }
                public Int32 Int2 { get { return Int32Int32Date.Int2; } }
                public DateTime Date1 { get { return Int32Int32Date.Date1; } }

                public override bool Equals(Object obj)
                {
                    //Check for null and compare run-time types.
                    if (obj == null || !(obj is Int32Int32DateO)) return false;
                    Int32Int32DateO item = (Int32Int32DateO)obj;
                    return (this.Int32Int32Date.Int1 == item.Int32Int32Date.Int1 &&
                            this.Int32Int32Date.Int2 == item.Int32Int32Date.Int2 &&
                            this.Int32Int32Date.Date1 == item.Int32Int32Date.Date1);
                }
                public override int GetHashCode()
                {
                    return (((Int64)Int32Int32Date.Int1 << 32) + Int32Int32Date.Int2).GetHashCode() ^ Int32Int32Date.GetHashCode();
                }
                public Int32Int32DateO(Int32 Int1, Int32 Int2, DateTime Date1)
                {
                    Int32Int32DateS int32Int32Date = new Int32Int32DateS(Int1, Int2, Date1);
                    this.Int32Int32Date = int32Int32Date;
                }
            }
        }
    }

Jeśli chodzi o używanie typu wartości fpr, klucz, który Microsoft wyraźnie odradza.

ValueType.GetHashCode

Tuple z technicznego punktu widzenia nie jest typem wartości, ale cierpi na ten sam objaw (kolizje skrótów) i nie jest dobrym kandydatem na klucz.

Czy mogę zasugerować alternatywę - anonimowy przedmiot. To jest to samo, którego używamy w metodzie GroupBy LINQ z wieloma kluczami.

var dictionary = new Dictionary<object, string> ();
dictionary[new { a = 1, b = 2 }] = "value";

Może to wyglądać dziwnie, ale przetestowałem Tuple.GetHashCode i nowe metody {a = 1, b = 2} .GetHashCode, a anonimowe obiekty wygrywają na moim komputerze w .NET 4.5.1:

Obiekt - 89,1732 ms dla 10000 wywołań w 1000 cykli

Tuple - 738,4475 ms dla 10000 wywołań w 1000 cykli

Innym rozwiązaniem do tych już wymienionych byłoby przechowywanie jakiejś listy wszystkich kluczy wygenerowanych do tej pory, a gdy generowany jest nowy obiekt, generujesz jego hashcode (jako punkt wyjścia), sprawdź, czy jest już na liście, czy tak jest, następnie dodaj do niego jakąś losową wartość itp., aż uzyskasz unikalny klucz, a następnie przechowuj ten klucz w samym obiekcie i na liście i zwracaj go jako klucz przez cały czas.