Tuplas (o matrices) como claves de diccionario en C #

109

Estoy tratando de hacer una tabla de búsqueda de diccionario en C #. Necesito resolver una tupla de valores de 3 en una cadena. Intenté usar matrices como claves, pero eso no funcionó, y no sé qué más hacer. En este punto, estoy considerando hacer un Diccionario de Diccionarios de Diccionarios, pero probablemente no sería muy bonito de ver, aunque así es como lo haría en javascript.

AlexH
fuente

Respuestas:

114

Si está en .NET 4.0 use una tupla:

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

Si no, puede definir una tupla y usarla como clave. La tupla debe anular GetHashCode, Equals e 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
fuente
6
Esta estructura también debería implementar IEquatable <Tuple <T, U, W >>. De esa manera, puede evitar el boxeo cuando se llama a Equals () en el caso de colisiones de códigos hash.
Dustin Campbell
16
@jerryjvl y todos los que encuentran esto en Google como lo hice yo, Tuple de .NET 4 implementa iguales para que pueda usarse en un diccionario.
Scott Chamberlain
30
Tu GetHashCodeimplementación no es muy buena. Es invariante bajo la permutación de los campos.
CodesInChaos
2
La tupla no debe ser una estructura. En el marco, Tuple es un tipo de referencia.
Michael Graczyk
5
@Thoraot: por supuesto, su ejemplo es falso ... debería serlo. ¿Por qué sería new object()igual a otro new object()? No solo usa una comparación de referencia directa ... intente:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Mike Marynowski
35

Entre los enfoques basados ​​en tuplas y diccionarios anidados, casi siempre es mejor optar por tuplas.

Desde el punto de vista de la mantenibilidad ,

  • es mucho más fácil implementar una funcionalidad que se parece a:

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

    que

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

    desde el lado del destinatario. En el segundo caso, cada adición, búsqueda, eliminación, etc. requiere una acción en más de un diccionario.

  • Además, si su clave compuesta requiere un campo más (o menos) en el futuro, deberá cambiar mucho el código en el segundo caso (diccionario anidado) ya que debe agregar más diccionarios anidados y verificaciones posteriores.

Desde la perspectiva del desempeño , la mejor conclusión a la que puede llegar es midiéndola usted mismo. Pero hay algunas limitaciones teóricas que puede considerar de antemano:

  • En el caso del diccionario anidado, tener un diccionario adicional para cada clave (externa e interna) tendrá una sobrecarga de memoria (más de lo que tendría la creación de una tupla).

  • En el caso del diccionario anidado, todas las acciones básicas, como la adición, actualización, búsqueda, eliminación, etc., deben realizarse en dos diccionarios. Ahora hay un caso en el que el enfoque de diccionario anidado puede ser más rápido, es decir, cuando los datos que se buscan están ausentes, ya que los diccionarios intermedios pueden omitir el cálculo y la comparación del código hash completo, pero de nuevo debe cronometrarse para estar seguro. En presencia de datos, debería ser más lento ya que las búsquedas deberían realizarse dos veces (o tres veces dependiendo del anidamiento).

  • Con respecto al enfoque de tuplas, las tuplas de .NET no son las más eficaces cuando están destinadas a usarse como claves en conjuntos, ya que su implementación EqualsyGetHashCode su implementación provocan un recuadro para los tipos de valor .

Yo optaría por un diccionario basado en tuplas, pero si quiero más rendimiento, usaría mi propia tupla con una mejor implementación.


En una nota al margen, pocos cosméticos pueden hacer que el diccionario sea genial:

  1. Las llamadas de estilo indexador pueden ser mucho más limpias e intuitivas. Por ejemplo,

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

    Así que exponga los indexadores necesarios en su clase de diccionario que maneja internamente las inserciones y búsquedas.

  2. Además, implemente una IEnumerableinterfaz adecuada y proporcione un Add(TypeA, TypeB, TypeC, string)método que le brinde la sintaxis del inicializador de la colección, como:

    new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
    { 
        { a, b, c, null }, 
        ...
    };
nawfal
fuente
En el caso de los diccionarios anidados, ¿la sintaxis del indexador no sería más parecida a esta string foo = dict[a][b][c]:?
Steven Rands
@StevenRands sí lo será.
nawfal
1
@nawfal ¿Puedo buscar en el diccionario de tuplas cuando solo tengo una clave, no todas? o ¿Puedo hacer como este dict [a, b] y luego dict [a, c]?
Khan Engineer
@KhanEngineer Mucho de eso depende de cuál sea el propósito del diccionario o cómo pretendas usarlo. Por ejemplo, desea volver valor por una parte de la clave, a. Podría simplemente iterar cualquier diccionario como cualquier colección normal y verificar la propiedad clave si es así a. Si siempre desea obtener el elemento en dict por primera propiedad, entonces puede diseñar mejor el diccionario como diccionario de diccionarios como se muestra en mi respuesta y consultar como dict[a], lo que le brinda otro diccionario.
Nawfal
Si por "buscar por una sola clave" quiere recuperar el valor por cualquiera de las claves que tiene, entonces será mejor que rediseñe su diccionario como una especie de "diccionario de cualquier clave". Por ejemplo, si desea obtener valor 4para ambas claves ay b, puede convertirlo en un diccionario estándar y agregar valores como dict[a] = 4y dict[b] = 4. Puede que no tenga sentido si lógicamente es tuyo ay bdebería ser una unidad. En tal caso, puede definir una costumbre IEqualityComparerque iguale dos instancias clave como iguales si alguna de sus propiedades es igual. Todo esto se puede hacer genéricamente con refelction.
Nawfal
30

Si está en C # 7, debería considerar el uso de tuplas de valor como clave compuesta. Las tuplas de valor suelen ofrecer un mejor rendimiento que las tuplas de referencia tradicionales ( Tuple<T1, …>) ya que las tuplas de valor son tipos de valor (estructuras), no tipos de referencia, por lo que evitan la asignación de memoria y los costos de recolección de basura. Además, ofrecen una sintaxis más concisa e intuitiva, lo que permite nombrar sus campos si así lo desea. También implementan la IEquatable<T>interfaz necesaria para el diccionario.

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
fuente
13

La forma buena, limpia, rápida, fácil y legible es:

  • generar miembros de igualdad ( método Equals () y GetHashCode ()) para el tipo actual. Herramientas como ReSharper no solo crean los métodos, sino que también generan el código necesario para una verificación de igualdad y / o para calcular el código hash. El código generado será más óptimo que la realización de Tuple.
  • simplemente cree una clase clave simple derivada de una tupla .

agregue algo similar como esto:

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

Entonces puedes usarlo con el diccionario:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};
  • También puedes usarlo en contratos.
  • como clave para unirse o agrupaciones en linq
  • De esta manera, nunca escribirá mal el pedido de Item1, Item2, Item3 ...
  • no es necesario recordar o buscar en el código para comprender dónde ir para obtener algo
  • no es necesario anular IStructuralEquatable, IStructuralComparable, IComparable, ITuple todos ellos ya están aquí
gabba
fuente
1
Ahora puede usar miembros con cuerpo de expresión, es aún más limpio, por ejemplopublic TypeA DataA => Item1;
andrewtatham
7

Si por alguna razón realmente desea evitar la creación de su propia clase Tuple o el uso integrado en .NET 4.0, existe otro enfoque posible; puede combinar los tres valores clave en un solo valor.

Por ejemplo, si los tres valores son tipos enteros juntos y no toman más de 64 bits, puede combinarlos en un ulong.

En el peor de los casos, siempre puede usar una cadena, siempre que se asegure de que los tres componentes que contiene estén delimitados con algún carácter o secuencia que no ocurra dentro de los componentes de la clave, por ejemplo, con tres números que podría intentar:

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

Obviamente, hay una sobrecarga de composición en este enfoque, pero dependiendo de lo que esté usando para esto, puede ser lo suficientemente trivial como para que no le importe.

jerryjvl
fuente
6
Sin embargo, diría que depende en gran medida del contexto; si tuviera tres tipos de enteros para combinar y el rendimiento no fuera crítico, esto funciona perfectamente con una mínima posibilidad de cometer un error. Por supuesto, todo esto es completamente redundante a partir de .NET 4, ya que Microsoft nos proporcionará tipos de tupla (¡presumiblemente correctos!) Listos para usar.
jerryjvl
Incluso podría usar este método en combinación con a JavaScriptSerializerpara concatenar una matriz de tipos de cadenas y / o enteros por usted. De esta forma, no es necesario que usted mismo cree un carácter delimitador.
binki
3
Esto podría llegar desordenado real si cualquiera de las teclas ( key1, key2, key3) eran cadenas que contienen la deliminator ( "#")
Greg
4

Anularía su Tuple con un GetHashCode adecuado y lo usaría como clave.

Siempre que sobrecargue los métodos adecuados, debería ver un rendimiento decente.

John Gietzen
fuente
1
IComparable no tiene ningún efecto sobre cómo se almacenan o ubican las claves en un Dictionary <TKey, TValue>. Todo se hace a través de GetHashCode () y un IEqualityComparer <T>. La implementación de IEquatable <T> logrará un mejor rendimiento porque alivia el encuadre causado por el EqualityComparer predeterminado, que recurre a la función Equals (objeto).
Dustin Campbell
Iba a mencionar GetHashCode, pero pensé que el Diccionario usaba IComparable en el caso de que los HashCodes fueran idénticos ... supongo que estaba equivocado.
John Gietzen
3

Aquí está la tupla .NET como referencia:

[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
fuente
3
Obtener el código hash se implementa como ((item1 ^ item2) * 33) ^ item3
Michael Graczyk
2

Si su código de consumo puede conformarse con una interfaz IDictionary <>, en lugar de Dictionary, mi instinto habría sido usar un SortedDictionary <> con un comparador de matriz personalizado, es decir:

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

Y crea así (usando int [] solo por el bien de un ejemplo concreto):

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