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

109

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

AlexH
источник

Ответы:

113

Если вы используете .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);
    }
}
Hallgrim
источник
6
Эта структура также должна реализовывать IEquatable <Tuple <T, U, W >>. Таким образом, вы можете избежать упаковки при вызове Equals () в случае коллизии хэш-кода.
Дастин Кэмпбелл
16
@jerryjvl и все остальные, кто находит это в Google, как и я, .NET 4 Tuple реализует equals, поэтому его можно использовать в словаре.
Скотт Чемберлен
30
Ваша GetHashCodeреализация не очень хороша. Он инвариантен относительно перестановки полей.
CodesInChaos
2
Кортеж не должен быть структурой. Во фреймворке Tuple является ссылочным типом.
Michael Graczyk
5
@Thoraot - конечно ваш пример ложный ... так и должно быть. Почему бы new object()равняться другому new object()? Он не просто использует прямое сравнение ... попробуйте:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Майк Мариновски 05
35

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

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

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

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

    чем

    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 }, 
        ...
    };
    
Навфал
источник
В случае вложенных словарей не будет ли синтаксис индексатора более похожим на это string foo = dict[a][b][c]:?
Стивен Рэндс,
@StevenRands, да, будет.
nawfal
1
@nawfal Могу ли я выполнять поиск в словаре кортежей, если у меня есть только один ключ, а не все? или Могу я сделать вот так dict [a, b], а затем dict [a, c]?
Хан Инженер
@KhanEngineer Многое из этого зависит от того, для чего предназначен словарь или как вы собираетесь его использовать. Например, вы хотите вернуть значение с помощью части ключа a. Вы можете просто перебирать любой словарь, как и любую обычную коллекцию, и проверять ключевое свойство, если оно есть a. Если вы всегда хотите получить элемент в dict по первому свойству, тогда вы можете лучше разработать словарь как словарь словарей, как показано в моем ответе и запросе dict[a], что дает вам еще один словарь.
nawfal
Если под «поиском только по одному ключу» вы имеете в виду вернуть значение по любому из имеющихся у вас ключей, то вам лучше переделать свой словарь как своего рода «словарь с любым ключом». Например, если вы хотите получить значение 4для обоих ключей aи b, вы можете сделать его стандартным словарем и добавить такие значения, как dict[a] = 4и dict[b] = 4. Это может не иметь смысла, если по логике ваш aи bдолжен быть одной единицей. В таком случае вы можете определить обычай, IEqualityComparerкоторый приравнивает два ключевых объекта как равные, если какие-либо из их свойств равны. Все это в общем можно сделать с помощью refelction.
nawfal
30

Если вы используете 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();
Дуглас
источник
13

Хорошие, чистые, быстрые, простые и понятные способы:

  • генерировать элементы равенства (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, они все уже здесь
габба
источник
1
Теперь вы можете использовать члены с телом выражения, его даже чище, напримерpublic TypeA DataA => Item1;
andrewtatham
7

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

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

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

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

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

jerryjvl
источник
6
Я бы сказал, что это сильно зависит от контекста; если бы мне нужно было объединить три целочисленных типа, и производительность не была критичной, это работало бы отлично с минимальной вероятностью ошибки. Конечно, все это полностью избыточно, начиная с .NET 4, поскольку Microsoft будет предоставлять нам (предположительно правильные!) Типы кортежей из коробки.
jerryjvl 06
Вы даже можете использовать этот метод в сочетании с a JavaScriptSerializerдля объединения для вас массива строковых и / или целочисленных типов. Таким образом, вам не нужно самостоятельно придумывать символ-разделитель.
binki
3
Это может получить реальный Messy , если какие - либо из клавиша ( key1, key2, key3) были строки , содержащие deliminator ( "#")
Greg
4

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

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

Джон Гитцен
источник
1
IComparable не влияет на то, как ключи хранятся или расположены в Dictionary <TKey, TValue>. Все это делается с помощью GetHashCode () и IEqualityComparer <T>. Внедрение IEquatable <T> позволит достичь более высокой производительности, потому что это облегчает упаковку, вызванную значением EqualityComparer по умолчанию, которое возвращается к функции Equals (object).
Дастин Кэмпбелл
Я собирался упомянуть GetHashCode, но я подумал, что Словарь использует IComparable в случае, когда HashCodes были идентичными ... думаю, я ошибался.
Джон Гитцен
3

Вот кортеж .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;
        }
    } 
}
Майкл Грачик
источник
3
Получение хэш-кода реализовано как ((item1 ^ item2) * 33) ^ item3
Michael Graczyk
2

Если ваш код потребления может обойтись интерфейсом IDictionary <> вместо Dictionary, я бы инстинктивно использовал 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>());
грязное мясо
источник