Tuple (o matrici) come chiavi del dizionario in C#

Question

Sto provando a creare una tabella di ricerca del dizionario in C#. Ho bisogno di risolvere una 3-tupla di valori su una stringa. Ho provato a utilizzare gli array come chiavi, ma non ha funzionato e non so cos'altro fare. A questo punto sto pensando di creare un dizionario di dizionari di dizionari, ma probabilmente non sarebbe molto bello da guardare, anche se è come lo farei in javascript.

Answer 1

Se siete su .NET 4.0 utilizzare una tupla:

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

Se non è possibile definire una tupla e l'uso che come chiave. La tupla ha bisogno di ignorare 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 2

Vorrei sovraccaricare la Tupla con un codice GetHash appropriato e usarlo come chiave.

Fintanto che si sovraccaricano i metodi corretti, si dovrebbero vedere prestazioni decenti.

Answer 3

Se per qualche ragione si vuole veramente evitare di creare la propria classe Tuple, o utilizzando il integrato in .NET 4.0, è possibile un altro approccio; è possibile combinare i tre valori chiave insieme in un unico valore.

Ad esempio, se i tre valori sono tipi interi insieme che non richiedono più di 64 bit, è possibile combinarli in un ulong.

Nel peggiore dei casi è sempre possibile utilizzare una stringa, purché si assicurino che i tre componenti in esso contenuti siano delimitati con un carattere o sequenza che non si verifica all'interno dei componenti della chiave, ad esempio, con tre numeri che si potrebbe provare:

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

C'è ovviamente un certo overhead composizione in questo approccio, ma a seconda di ciò che si sta utilizzando per questo può essere abbastanza banale non preoccuparsi a questo proposito.

Answer 4

Ecco la tupla .NET per riferimento:

[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 5

Se il codice di consumo può accontentarsi di un> Interfaccia IDictionary <, invece di dizionario, il mio istinto sarebbe stato quello di utilizzare un SortedDictionary <> con una matrice di confronto personalizzato, vale a dire:

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 creare in tal modo (usando int [] solo per amor di esempio concreto):

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

Answer 6

Tra approcci basati su dizionari tuple e nidificati, è quasi sempre preferibile utilizzare la tupla.

Dal punto manutenibilità di vista,

• la sua molto più facile da implementare una funzionalità che assomiglia a:

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

  di

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

  dal lato chiamato.Nel secondo caso ogni aggiunta, ricerca, rimozione ecc. Richiedono un'azione su più di un dizionario.

• Inoltre, se la propria chiave composita richiede un campo in più (o meno) in futuro, sarà necessario modificare il codice un lotto significativo nel secondo caso (dizionario nidificato) poiché è necessario aggiungere ulteriori dizionari nidificati e controlli successivi .

Dal punto di vista delle prestazioni, la conclusione migliore si può raggiungere è quello di misurare da soli. Ma ci sono alcune limitazioni teoriche che si può considerare a priori:

• Nel caso dizionario nidificato, che hanno un dizionario aggiuntivo per ogni chiavi (esterna e interna) avrà un certo sovraccarico di memoria (più di quello che la creazione di una tupla avrebbe).

• Nel caso del dizionario nidificato, ogni azione di base come aggiunta, aggiornamento, ricerca, rimozione ecc. Deve essere eseguita in due dizionari. Ora c'è un caso in cui l'approccio del dizionario nidificato può essere più veloce, cioè quando i dati che si trovano sono assenti, poiché i dizionari intermedi possono ignorare il calcolo completo del codice hash &, ma poi di nuovo dovrebbe essere cronometrato per essere sicuro. In presenza di dati, dovrebbe essere più lento poiché le ricerche dovrebbero essere eseguite due volte (o tre volte a seconda del nesting).

• Per quanto riguarda l'approccio a tuple, le tuple .NET non sono le più performanti quando devono essere utilizzate come chiavi in ​​serie dal suo Equals and GetHashCode implementation causes boxing for value types.

Vorrei andare con il dizionario basato su tupla, ma se voglio più prestazioni, userei la mia tupla con una migliore implementazione.

---

Una nota a parte, alcuni cosmetici possono rendere il fresco dizionario:

1. chiamate stile indicizzatore può essere molto più pulito e intuitivo. Per esempio,

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

   Quindi esporre indicizzatori necessarie nella classe dizionario che gestisce internamente gli inserimenti e le ricerche.

2. Inoltre, implementare una opportuna interfaccia IEnumerable e fornire un metodo Add(TypeA, TypeB, TypeC, string) che darebbe la sintassi di inizializzazione collezione, come:

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

Answer 7

Il modo buono, pulito, veloce, facile e leggibile è:

basta creare una semplice classe di chiave derivata da una tupla.

aggiungere qualcosa di simile come questo:

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

in modo da poter utilizzare con il dizionario:

var myDictinaryData = new Dictionary<myKey, string>() 
{ 
    {new myKey(1, 2, 3), "data123"}, 
    {new myKey(4, 5, 6), "data456"}, 
    {new myKey(7, 8, 9), "data789"} 
}; 

• È inoltre possibile utilizzarlo nei contratti
• come chiave per entrare o raggruppamenti in linq
• andando in questo modo non si scrive mai in modo errato l'ordine dell'articolo1, elemento2, elemento3 ...
si
• non c'è bisogno di ricordare o esaminare il codice per capire dove andare a prendere qualcosa
• nessuna necessità di sovrascrivere IStructuralEquatable, IStructuralComparable, IComparable, ITuple tutti alredy qui