Tuples (ou tableaux) en tant que clés de dictionnaire en C #

Question

J'essaye de faire une table de consultation de dictionnaire en C #. J'ai besoin de résoudre un triplet de valeurs en une chaîne. J'ai essayé d'utiliser des tableaux comme clés, mais cela n'a pas fonctionné et je ne sais pas quoi faire d'autre. À ce stade, j’envisage de créer un dictionnaire de dictionnaires de dictionnaires, mais ce ne serait probablement pas très joli à regarder, bien que ce soit comme cela que je le ferais en javascript.

Answer 1

Si vous êtes sur .NET 4.0, utilisez un tuple:

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

Sinon, vous pouvez définir un tuple et l'utiliser comme clé. Le tuple doit remplacer GetHashCode, Equals et 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

Entre n-uplet et imbriquées les dictionnaires en fonction des approches, il est presque toujours préférable d'opter pour un tuple base.

De maintenabilité point de vue,

• son beaucoup plus facile de mettre en œuvre une fonctionnalité qui ressemble à ceci:

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

  que

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

  à partir de l'appelé côté. Dans le second cas, chaque ajout, recherche, suppression, etc demandent une action de plus d'un dictionnaire.

• En outre, si votre clé composite nécessitent un plus (ou moins) dans l'avenir, vous aurez besoin de changer le code d'un important lot, dans le second cas (nested dictionnaire) depuis que vous avez à ajouter d'autres imbriqués les dictionnaires et les contrôles ultérieurs.

Du point de vue des performances, la meilleure conclusion que vous pouvez atteindre est en mesure de vous-même. Mais il y a quelques limitations théoriques que vous pouvez considérer à l'avance:

• Dans le imbriqués dictionnaire les cas, avoir un dictionnaire supplémentaire pour toutes les touches (extérieure et intérieure) aura une certaine surcharge de la mémoire (plus que ce que la création d'un tuple aurait).

• Dans le imbriqués dictionnaire cas, toutes les actions de base comme l'addition, la mise à jour, recherche, suppression, etc doivent être effectuées dans les deux dictionnaires. Maintenant, il est un cas où imbriquée dictionnaire approche peut être plus rapide, c'est à dire, lorsque les données regardé est absent, puisque l'intermédiaire des dictionnaires peut contourner le plein de code de hachage de calcul et la comparaison, mais là encore, il devrait être programmé pour être sûr. En présence de données, il devrait être plus lente depuis les recherches doivent être effectuées deux fois (ou trois fois selon la nidification).

• Concernant tuple approche .NET les tuples ne sont pas les plus performants lorsqu'ils sont destinés à être utilisés comme clés dans les ensembles depuis sa Equals et GetHashCode de la mise en œuvre des causes de boxe pour les types de valeur.

Je voudrais aller avec tuple base de dictionnaire, mais si je veux plus de performance, je voudrais utiliser mon propre tuple avec une meilleure mise en œuvre.

---

Sur une note de côté, peu de produits cosmétiques peut faire le dictionnaire cool:

1. Indexeur de style, les appels peuvent être beaucoup plus propre et intuitive. Par exemple,

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

   Afin d'exposer nécessaire indexeurs dans votre dictionnaire de la classe qui gère en interne les insertions et les recherches.

2. Aussi, de mettre en œuvre un adapté IEnumerable interface et de fournir un Add(TypeA, TypeB, TypeC, string) méthode serait vous donner la syntaxe d'initialiseur de collection, comme:

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

Answer 3

Si pour quelque raison vous voulez vraiment éviter de créer votre propre Tuple de la classe ou de l'aide sur les construit dans .NET 4.0, il existe une autre approche possible; vous pouvez combiner les trois valeurs de clés en une seule valeur.

Par exemple, si les trois valeurs sont les types integer, ensemble, de ne pas prendre plus de 64 bits, vous pouvez les combiner en un ulong.

Le pire des cas vous pouvez toujours utiliser une chaîne de caractères, aussi longtemps que vous vous assurez que les trois composantes sont délimités avec un certain personnage ou d'une séquence qui ne se produit pas à l'intérieur de l'composants de la clé, par exemple, avec trois nombres, vous pourriez essayer:

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

Il y a évidemment une certaine composition de frais généraux dans cette approche, mais en fonction de ce que vous l'utilisez pour cela peut être assez trivial de ne pas s'en soucier.

Answer 4

Voici le tuple .NET pour référence:

 [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

Je surchargerais votre tuple avec un GetHashCode approprié et l'utiliserais simplement comme clé.

Tant que vous surchargez les méthodes appropriées, vous devriez voir des performances décentes.