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

Ответ 1

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

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

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

Ответ 2

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

С точки зрения удобства обслуживания,

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

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

  чем

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

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

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

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

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

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

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

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

На боковой ноте несколько косметических средств могут сделать словарь прохладным:

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

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

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

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

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

Ответ 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, IComparable, ITuple они все уже здесь

Ответ 4

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

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

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

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

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

Ответ 5

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

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

Ответ 6

Если вы используете С# 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();

Ответ 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;
        }
    } 
}

Ответ 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>());