Tuplas (ou matrizes) como chaves de dicionário em C #

109

Estou tentando fazer uma tabela de pesquisa de dicionário em C #. Eu preciso resolver uma 3-tupla de valores para uma string. Tentei usar arrays como chaves, mas não funcionou e não sei mais o que fazer. Neste ponto, estou pensando em fazer um Dicionário de Dicionários de Dicionários, mas provavelmente não seria muito bonito de se ver, embora seja como eu faria em javascript.

AlexH
fonte

Respostas:

113

Se você estiver no .NET 4.0, use uma tupla:

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

Caso contrário, você pode definir um Tuplee usá-lo como a chave. O Tuple precisa substituir GetHashCode, Equalse 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
fonte
6
Essa estrutura também deve implementar IEquatable <Tuple <T, U, W >>. Dessa forma, você pode evitar boxing quando Equals () é chamado no caso de colisões de código hash.
Dustin Campbell
16
@jerryjvl e todos os outros que encontrarem isso no Google como eu, o Tuple do .NET 4 implementa igual para que possa ser usado em um dicionário.
Scott Chamberlain
30
Sua GetHashCodeimplementação não é muito boa. É invariante sob a permutação dos campos.
CodesInChaos
2
A tupla não deve ser uma estrutura. Na estrutura, Tupla é um tipo de referência.
Michael Graczyk
5
@Thoraot - é claro que seu exemplo é falso ... deveria ser. Por que new object()seria igual a outro new object()? Ele não usa apenas referência direta comarison ... tente:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Mike Marynowski
35

Entre abordagens baseadas em tupla e dicionários aninhados, quase sempre é melhor ir para tupla.

Do ponto de vista da sustentabilidade ,

  • é muito mais fácil implementar uma funcionalidade semelhante a:

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

    do que

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

    do lado do receptor. No segundo caso, cada adição, pesquisa, remoção etc. requer ação em mais de um dicionário.

  • Além disso, se sua chave composta exigir um campo a mais (ou menos) no futuro, você precisará alterar muito o código no segundo caso (dicionário aninhado), uma vez que terá de adicionar outros dicionários aninhados e verificações subsequentes.

Do ponto de vista do desempenho , a melhor conclusão que você pode chegar é medindo você mesmo. Mas existem algumas limitações teóricas que você pode considerar de antemão:

  • No caso do dicionário aninhado, ter um dicionário adicional para cada chave (externa e interna) terá alguma sobrecarga de memória (mais do que a criação de uma tupla teria).

  • No caso do dicionário aninhado, todas as ações básicas como adição, atualização, pesquisa, remoção, etc., precisam ser realizadas em dois dicionários. Agora, há um caso em que a abordagem de dicionário aninhado pode ser mais rápida, ou seja, quando os dados pesquisados ​​estão ausentes, uma vez que os dicionários intermediários podem ignorar o cálculo e comparação do código hash completo, mas, novamente, deve ser cronometrado para ter certeza. Na presença de dados, deve ser mais lento, pois as pesquisas devem ser realizadas duas vezes (ou três, dependendo do aninhamento).

  • Em relação à abordagem tupla, tuplas .NET não são os mais performance quando eles foram feitos para ser usado como chaves em conjuntos desde a sua Equalse GetHashCodecausas de implementação boxe para tipos de valor .

Eu escolheria um dicionário baseado em tupla, mas se eu quiser mais desempenho, eu usaria minha própria tupla com melhor implementação.


Por outro lado, poucos cosméticos podem tornar o dicionário legal:

  1. As chamadas do estilo do indexador podem ser muito mais claras e intuitivas. Por exemplo,

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

    Portanto, exponha os indexadores necessários em sua classe de dicionário que lida internamente com as inserções e pesquisas.

  2. Além disso, implemente uma IEnumerableinterface adequada e forneça um Add(TypeA, TypeB, TypeC, string)método que forneça a sintaxe do inicializador de coleção, como:

    new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
    { 
        { a, b, c, null }, 
        ...
    };
Nawfal
fonte
No caso de dicionários aninhados, a sintaxe do indexador não seria mais parecida com esta string foo = dict[a][b][c]:?
Steven Rands
@StevenRands sim, será.
nawfal
1
@nawfal Posso pesquisar o dicionário de tupla quando tenho apenas uma ou todas as chaves? ou Posso fazer assim, dict [a, b], depois, dict [a, c]?
Khan Engineer
@KhanEngineer Muito disso depende de qual é o propósito do dicionário ou como você pretende usá-lo. Por exemplo, você deseja obter o valor de volta por uma parte da chave a,. Você poderia apenas iterar qualquer dicionário como qualquer coleção normal e verificar a propriedade da chave, se estiver a. Se você sempre deseja obter o item em dict pela primeira propriedade, você pode projetar melhor o dicionário como um dicionário de dicionários, conforme mostrado em minha resposta e consulta como dict[a], o que lhe dá outro dicionário.
nawfal
Se por "pesquisar por apenas uma chave" você pretende obter o valor de volta por qualquer uma das chaves que você possui, então é melhor redesenhar seu dicionário como uma espécie de "qualquer dicionário chave". Por exemplo, se você deseja obter valor 4para ambas as chaves ae b, então você pode torná-lo um dicionário padrão e adicionar valores como dict[a] = 4e dict[b] = 4. Pode não fazer sentido se logicamente seu ae bdevesse ser uma unidade. Nesse caso, você pode definir um personalizado IEqualityComparerque iguale duas instâncias-chave como iguais se alguma de suas propriedades for igual. Tudo isso pode ser feito genericamente com reflexão.
nawfal
30

Se você estiver no C # 7, deve considerar o uso de tuplas de valor como sua chave composta. As tuplas de valor geralmente oferecem melhor desempenho do que as tuplas de referência tradicionais ( Tuple<T1, …>), uma vez que as tuplas de valor são tipos de valor (structs), não tipos de referência, portanto, evitam os custos de alocação de memória e coleta de lixo. Além disso, eles oferecem uma sintaxe mais concisa e intuitiva, permitindo que seus campos sejam nomeados se você desejar. Eles também implementam a IEquatable<T>interface necessária para o dicionário.

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();
Douglas
fonte
13

As maneiras boas, limpas, rápidas, fáceis e legíveis são:

  • gerar o método de membros de igualdade (Equals () e GetHashCode ()) para o tipo atual. Ferramentas como ReSharper não apenas criam os métodos, mas também geram o código necessário para uma verificação de igualdade e / ou para calcular o código hash. O código gerado será mais otimizado do que a realização de Tupla.
  • basta fazer uma classe de chave simples derivada de uma tupla .

adicione algo semelhante a isto:

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

Então você pode usá-lo com o dicionário:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};
  • Você também pode usá-lo em contratos
  • como uma chave para ingressar ou agrupar no linq
  • dessa forma, você nunca errou na ordem do Item1, Item2, Item3 ...
  • você não precisa se lembrar ou olhar para o código para entender onde ir para conseguir algo
  • não há necessidade de substituir IStructuralEquatable, IStructuralComparable, IComparable, ITuple, todos eles já estão aqui
gabba
fonte
1
Agora você pode usar a expressão de membros public TypeA DataA => Item1;
corporais
7

Se, por algum motivo, você realmente deseja evitar criar sua própria classe Tuple, ou usar um embutido no .NET 4.0, existe uma outra abordagem possível; você pode combinar os três valores-chave em um único valor.

Por exemplo, se os três valores forem tipos inteiros juntos não ocupando mais de 64 bits, você pode combiná-los em um ulong.

Na pior das hipóteses, você sempre pode usar uma string, desde que certifique-se de que os três componentes nela são delimitados com algum caractere ou sequência que não ocorre dentro dos componentes da chave, por exemplo, com três números que você pode tentar:

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

Obviamente, há alguma sobrecarga de composição nessa abordagem, mas dependendo do que você está usando, isso pode ser trivial o suficiente para não se importar com isso.

Jerryjvl
fonte
6
Eu diria que depende fortemente do contexto; se eu tivesse três tipos de inteiros para combinar e o desempenho não fosse crítico, isso funcionaria perfeitamente com o mínimo de chance de cometer um erro. Claro, tudo isso é completamente redundante no .NET 4, já que a Microsoft nos fornecerá (presumivelmente corretos!) Tipos de tupla prontos para uso.
jerryjvl
Você pode até usar esse método em combinação com um JavaScriptSerializerpara concatenar uma matriz de tipos de string e / ou inteiros para você. Dessa forma, você não precisa criar um caractere delimitador sozinho.
binki
3
Isso pode ficar confuso real, se qualquer uma das teclas ( key1, key2, key3) foram strings contendo o deliminator ( "#")
Greg
4

Eu substituiria sua Tupla por um GetHashCode apropriado e apenas o usaria como a chave.

Contanto que você sobrecarregue os métodos adequados, deverá ver um desempenho decente.

John Gietzen
fonte
1
IComparable não tem efeito sobre como as chaves são armazenadas ou localizadas em um Dicionário <TKey, TValue>. Tudo é feito por meio de GetHashCode () e um IEqualityComparer <T>. Implementar IEquatable <T> obterá um melhor desempenho porque alivia o boxing causado pelo EqualityComparer padrão, que recorre à função Equals (objeto).
Dustin Campbell
Ia mencionar GetHashCode, mas pensei que o Dicionário usava IComparable no caso de os HashCodes serem idênticos ... acho que estava errado.
John Gietzen
3

Aqui está a tupla do .NET para referência:

[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;
        }
    } 
}
Michael Graczyk
fonte
3
O código de hash get é implementado como ((item1 ^ item2) * 33) ^ item3
Michael Graczyk
2

Se o seu código de consumo pode se contentar com uma interface IDictionary <>, em vez de Dictionary, meu instinto teria sido usar um SortedDictionary <> com um comparador de array personalizado, ou seja:

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

E crie assim (usando int [] apenas para um exemplo concreto):

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