suma - recorrer matriz c#

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

Question

Estoy tratando de hacer una tabla de búsqueda del diccionario en C #. Necesito resolver una 3-tupla de valores para 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 Dictionary of Dictionaries of Dictionaries, pero probablemente no sería muy bonito de ver, aunque así es como lo haría en javascript.

Answer 1

Aquí está la tupla .NET para 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;
        }
    } 
}

Answer 2

Entre los enfoques basados ​​en tuplas y diccionarios anidados, casi siempre es mejor elegir una tupla.

Desde el punto de vista de la mantenibilidad ,

• es mucho más fácil implementar una funcionalidad que se ve así:

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

  que

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

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

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

Desde la perspectiva del rendimiento , 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 tecla (externa e interna) tendrá cierta 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, la actualización, la búsqueda, la eliminación, etc. deben llevarse a cabo en dos diccionarios. Ahora hay un caso en el que el enfoque del diccionario anidado puede ser más rápido, es decir, cuando los datos que se buscan son ausentes, dado que los diccionarios intermedios pueden omitir el cómputo y la comparación del código hash completo, pero una vez más debe estar sincronizado para asegurarse. En presencia de datos, debe ser más lento ya que las búsquedas se deben realizar dos veces (o tres veces según la anidación).

• Con respecto al enfoque de tupla, las tuplas de .NET no son las más efectivas cuando se supone que deben usarse como claves en los conjuntos, ya que su implementación Equals y GetHashCode provocan el encajamiento de los tipos de valores .

Me gustaría ir con el diccionario basado en tuplas, pero si quiero más rendimiento, usaría mi propia tupla con una mejor implementación.

En una nota lateral, algunos cosméticos pueden refrescar el diccionario:

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

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

   De modo que exponga los indexadores necesarios en su clase de diccionario, que maneja internamente las inserciones y las búsquedas.

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

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

Answer 3

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

solo crea una clase de clave simple derivada de una tupla .

agregue algo similar como este:

public sealed class myKey : Tuple<TypeA, TypeB, TypeC>
{
    public myKey(TypeA dataA, TypeB dataB, TypeC dataC) : base (dataA, dataB, dataC) { }

    public TypeA DataA { get { return Item1; } }

    public TypeB DataB { get { return Item2; } }

    public TypeC DataC { get { return 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 una clave para unirse o agruparse en linq
• yendo de esta manera, nunca se escribe mal el orden de Item1, Item2, Item3 ...
• no es necesario que recuerdes o revises el código para entender a dónde ir para obtener algo
• no hay necesidad de anular IStructuralEquatable, IStructuralComparable, IComparable, ITuple all allredy aquí

Answer 4

Si estás en .NET 4.0 usa un Tuple:

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

Si no, puede definir un Tuple y usarlo como la clave. El Tuple necesita 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);
    }
}

Answer 5

Si por alguna razón realmente desea evitar la creación de su propia clase Tuple, o usarla incorporada 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 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 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 no importarle.

Answer 6

Si su código de consumo puede arreglarse con una interfaz IDictionary <>, en lugar de Dictionary, mi instinto habría sido utilizar 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 para el ejemplo concreto]:

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

Answer 7

Sobrecargaría tu Tuple con un GetHashCode adecuado y solo lo usaría como clave.

Siempre que sobrecargues los métodos adecuados, deberías ver un rendimiento decente.