Кортежи (или массивы) как словарные ключи в C #

Question

Я пытаюсь создать таблицу поиска по словарю в C #. Мне нужно разрешить 3 кортежа значений в одну строку. Я пытался использовать массивы в качестве ключей, но это не сработало, и я не знаю, что еще делать. На данный момент я рассматриваю возможность создания словаря словарей словарей, но это, вероятно, будет не очень красиво смотреться, хотя я так и сделал бы в javascript.

Answer 1

Если вы используете .NET 4.0, используйте кортеж:

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

Если нет, вы можете определить кортеж и использовать его в качестве ключа. Кортежу необходимо переопределить GetHashCode, Equals и 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);
    }
}

Answer 2

Между подходами на основе кортежей и вложенных словарей почти всегда лучше выбирать кортежи на основе.

С точки зрения ремонтопригодности ,

• гораздо проще реализовать функциональность, которая выглядит следующим образом:

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

  1012 * чем *

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

  со стороны абонента. Во втором случае каждое добавление, поиск, удаление и т. Д. Требуют действий для более чем одного словаря.

• Кроме того, если вашему составному ключу в будущем потребуется еще одно (или меньшее) поле, вам потребуется изменить значительный лот во втором случае (вложенный словарь), поскольку вам нужно добавить дополнительные вложенные словари и последующие чеки.

С точки зрения производительности лучший вывод, который вы можете сделать, это измерить его самостоятельно. Но есть несколько теоретических ограничений, которые вы можете рассмотреть заранее:

• В случае вложенного словаря наличие дополнительного словаря для каждого ключа (внешнего и внутреннего) будет иметь некоторые накладные расходы памяти (больше, чем было бы при создании кортежа).

• В случае вложенного словаря все основные действия, такие как добавление, обновление, поиск, удаление и т. Д., Должны выполняться в двух словарях. Теперь существует случай, когда подход с использованием вложенного словаря может быть более быстрым, то есть когда ищащиеся данные отсутствуют, поскольку промежуточные словари могут обходить вычисление и сравнение полного хеш-кода, но опять же, это должно быть рассчитано по времени, чтобы быть уверенным. При наличии данных это должно быть медленнее, так как поиск должен выполняться дважды (или трижды в зависимости от вложенности).

• Что касается подхода с кортежем, то кортежи .NET не являются наиболее производительными, когда они предназначены для использования в качестве ключей в наборах, поскольку его реализация Equals и GetHashCode вызывает бокс для типов значений .

Я бы использовал словарь на основе кортежей, но если я хочу большей производительности, я бы использовал свой собственный кортеж с лучшей реализацией.

---

На заметку, немного косметики могут сделать словарь крутым:

1. Вызовы в стиле индексатора могут быть намного понятнее и понятнее. Например,

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

   Итак, предоставьте необходимые индексаторы в вашем классе словаря, который внутренне обрабатывает вставки и поиск.

2. Кроме того, реализуйте подходящий интерфейс IEnumerable и предоставьте метод Add(TypeA, TypeB, TypeC, string), который даст вам синтаксис инициализатора коллекции, например:

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

Answer 3

Хорошие, чистые, быстрые, легкие и читаемые способы это:

• генерирует элементы равенства (Equals () и GetHashCode ()) метод для текущего типа. Такие инструменты, как ReSharper не только создают методы, но и генерируют необходимый код для проверки на равенство и / или для вычисления хеш-кода. Сгенерированный код будет более оптимальным, чем реализация Tuple.
• просто создайте простой класс ключей, полученный из кортежа .

добавить что-то похожее на это:

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

Так что вы можете использовать его со словарем:

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

• Вы также можете использовать его в контрактах
• как ключ для объединения или группировки в linq
• идя таким образом, вы никогда не ошибетесь в порядке Item1, Item2, Item3 ...
• вам не нужно помнить или изучать код, чтобы понять, куда идти, чтобы получить что-то
• нет необходимости переопределять IStructuralEquatable, IStructuralComparable, Сравнимо, все они уже здесь

Answer 4

Если по какой-то причине вы действительно хотите избежать создания собственного класса Tuple или использования встроенного в .NET 4.0, возможен еще один подход; Вы можете объединить три ключевых значения в одно значение.

Например, если три значения представляют собой целочисленные типы, не занимающие более 64 бит, вы можете объединить их в ulong.

В худшем случае вы всегда можете использовать строку, если убедитесь, что все три компонента в ней разделены каким-либо символом или последовательностью, которая не встречается внутри компонентов ключа, например, тремя числами, которые вы могли бы использовать. попробовать:

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

Очевидно, что в этом подходе есть некоторые накладные расходы на композицию, но в зависимости от того, что вы используете для этого, может быть достаточно тривиально, чтобы не заботиться об этом.

Answer 5

Если вы на C # 7, вам следует рассмотреть возможность использования кортежей значений в качестве составного ключа. Кортежи значений обычно предлагают лучшую производительность, чем традиционные эталонные кортежи (Tuple<T1, …>), поскольку кортежи значений являются типами значений (структурами), а не ссылочными типами, поэтому они позволяют избежать затрат на выделение памяти и сбор мусора. Кроме того, они предлагают краткий и более интуитивно понятный синтаксис, позволяющий именовать их поля, если вы того пожелаете. Они также реализуют интерфейс IEquatable<T>, необходимый для словаря.

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

Answer 6

Я бы переопределил ваш кортеж правильным GetHashCode и просто использовал бы его в качестве ключа.

Пока вы перегружаете правильные методы, вы должны видеть приличную производительность.

Answer 7

Вот кортеж .NET для справки:

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

Answer 8

Если ваш потребляющий код может обойтись с интерфейсом IDictionary <> вместо словаря, мой инстинкт должен был бы использовать SortedDictionary <> с пользовательским компаратором массива, то есть:

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

И создать таким образом (используя int [] только для конкретного примера):

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