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

109

J'essaie de créer une table de recherche de dictionnaire en C #. J'ai besoin de résoudre un 3-tuple de valeurs en une seule 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, même si c'est comme ça que je le ferais en javascript.

AlexH
la source

Réponses:

113

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

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

Sinon, vous pouvez définir un Tupleet l'utiliser comme clé. Le Tuple doit passer outre GetHashCode, Equalset 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
la source
6
Cette structure doit également implémenter IEquatable <Tuple <T, U, W >>. De cette façon, vous pouvez éviter la boxe lorsque Equals () est appelé dans le cas de collisions de code de hachage.
Dustin Campbell
16
@jerryjvl et tous les autres qui trouvent cela par Google comme je l'ai fait, Tuple de .NET 4 implémente equals afin qu'il puisse être utilisé dans un dictionnaire.
Scott Chamberlain
30
Votre GetHashCodeimplémentation n'est pas très bonne. C'est invariant sous permutation des champs.
CodesInChaos
2
Tuple ne doit pas être une structure. Dans le framework, Tuple est un type de référence.
Michael Graczyk
5
@Thoraot - bien sûr, votre exemple est faux ... ça devrait l'être. Pourquoi serait new object()égal à un autre new object()? Il n'utilise pas seulement une comparaison de référence directe ... essayez:bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));
Mike Marynowski
35

Entre les approches basées sur les tuple et les dictionnaires imbriqués, il est presque toujours préférable d'opter pour les tuple.

Du point de vue de la maintenabilité ,

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

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

    que

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

    du côté de l'appelé. Dans le second cas, chaque ajout, recherche, suppression, etc. nécessite une action sur plusieurs dictionnaires.

  • De plus, si votre clé composite nécessite un champ de plus (ou moins) à l'avenir, vous devrez changer beaucoup de code dans le second cas (dictionnaire imbriqué) car vous devez ajouter d'autres dictionnaires imbriqués et les vérifications suivantes.

Du point de vue de la performance , la meilleure conclusion que vous puissiez tirer est de la mesurer vous-même. Mais il y a quelques limitations théoriques que vous pouvez considérer au préalable:

  • Dans le cas du dictionnaire imbriqué, avoir un dictionnaire supplémentaire pour chaque clé (externe et interne) entraînera une surcharge de mémoire (plus que ce que la création d'un tuple aurait).

  • Dans le cas du dictionnaire imbriqué, toutes les actions de base telles que l'ajout, la mise à jour, la recherche, la suppression, etc. doivent être effectuées dans deux dictionnaires. Maintenant, il y a un cas où l'approche par dictionnaire imbriqué peut être plus rapide, c'est-à-dire lorsque les données recherchées sont absentes, car les dictionnaires intermédiaires peuvent contourner le calcul et la comparaison du code de hachage complet, mais là encore, il devrait être chronométré pour être sûr. En présence de données, il devrait être plus lent car les recherches doivent être effectuées deux fois (ou trois fois selon l'imbrication).

  • En ce qui concerne l'approche par tuple, les tuples .NET ne sont pas les plus performants lorsqu'ils sont destinés à être utilisés comme clés dans des ensembles, car leur implémentation Equalset leur GetHashCodeimplémentation provoquent un encadrement des types valeur .

J'irais avec un dictionnaire basé sur un tuple, mais si je veux plus de performances, j'utiliserais mon propre tuple avec une meilleure implémentation.


Par ailleurs, peu de cosmétiques peuvent rendre le dictionnaire cool:

  1. Les appels de style indexeur peuvent être beaucoup plus propres et intuitifs. Par exemple,

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

    Exposez donc les indexeurs nécessaires dans votre classe de dictionnaire qui gère en interne les insertions et les recherches.

  2. En outre, implémentez une IEnumerableinterface appropriée et fournissez une Add(TypeA, TypeB, TypeC, string)méthode qui vous donnerait une syntaxe d'initialisation de collection, comme:

    new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
    { 
        { a, b, c, null }, 
        ...
    };
nawfal
la source
Dans le cas des dictionnaires imbriqués, la syntaxe de l'indexeur ne ressemblerait-elle pas davantage à ceci string foo = dict[a][b][c]:?
Steven Rands
@StevenRands oui ça le sera.
nawfal
1
@nawfal Puis-je rechercher un dictionnaire de tuple quand je n'ai qu'une seule des clés pas toutes? ou Puis-je faire comme ce dict [a, b] puis dict [a, c]?
Khan Engineer
@KhanEngineer Cela dépend en grande partie de l'objectif du dictionnaire ou de la manière dont vous comptez l'utiliser. Pour exemple, vous voulez obtenir la valeur de retour d'une partie de la clé, a. Vous pouvez simplement itérer n'importe quel dictionnaire comme n'importe quelle collection normale et vérifier la propriété de clé si c'est le cas a. Si vous voulez toujours obtenir l'élément dans dict par la première propriété, vous pouvez mieux concevoir le dictionnaire en tant que dictionnaire de dictionnaires comme indiqué dans ma réponse et une requête comme dict[a], ce qui vous donne un autre dictionnaire.
nawfal
Si par «recherche par une seule clé», vous entendez récupérer la valeur par l'une des clés que vous avez, alors vous feriez mieux de reconcevoir votre dictionnaire comme une sorte de «dictionnaire de toute clé». Par exemple, si vous souhaitez obtenir une valeur 4pour les deux clés aet b, vous pouvez en faire un dictionnaire standard et ajouter des valeurs telles que dict[a] = 4et dict[b] = 4. Cela peut ne pas avoir de sens si logiquement votre aet bdevrait être une unité. Dans un tel cas, vous pouvez définir une personnalisation IEqualityComparerqui assimile deux instants clés comme égaux si l'une de leurs propriétés est égale. Tout cela peut être fait de manière générique avec refelction.
nawfal
30

Si vous êtes sur C # 7, vous devriez envisager d'utiliser des tuples de valeur comme clé composite. Les tuples de valeur offrent généralement de meilleures performances que les tuples de référence traditionnels ( Tuple<T1, …>) car les tuples de valeur sont des types de valeur (structs), pas des types de référence, ils évitent donc les coûts d'allocation de mémoire et de garbage collection. En outre, ils offrent une syntaxe plus concise et plus intuitive, permettant à leurs champs d'être nommés si vous le souhaitez. Ils implémentent également l' IEquatable<T>interface nécessaire au dictionnaire.

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
la source
13

Les moyens efficaces, propres, rapides, faciles et lisibles sont:

  • générer des membres d'égalité ( méthode Equals () et GetHashCode ()) pour le type actuel. Des outils comme ReSharper créent non seulement les méthodes, mais génèrent également le code nécessaire pour une vérification d'égalité et / ou pour calculer le code de hachage. Le code généré sera plus optimal que la réalisation Tuple.
  • créez simplement une classe de clé simple dérivée d'un tuple .

ajoutez quelque chose de similaire comme ceci:

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

Vous pouvez donc l'utiliser avec le dictionnaire:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};
  • Vous pouvez également l'utiliser dans les contrats
  • comme clé pour la jointure ou les regroupements dans linq
  • en procédant de cette façon, vous ne vous trompez jamais dans l'ordre de Item1, Item2, Item3 ...
  • vous n'avez pas besoin de vous souvenir ou d'examiner le code pour comprendre où aller pour obtenir quelque chose
  • pas besoin de remplacer IStructuralEquatable, IStructuralComparable, IComparable, ITuple ils sont tous déjà ici
gabba
la source
1
Maintenant, vous pouvez utiliser l'expression membres corsés, c'est encore plus propre, par exemplepublic TypeA DataA => Item1;
andrewtatham
7

Si, pour une raison quelconque, vous voulez vraiment éviter de créer votre propre classe Tuple ou d'utiliser une fonction intégrée à .NET 4.0, il existe une autre approche possible; vous pouvez combiner les trois valeurs clés en une seule valeur.

Par exemple, si les trois valeurs sont des types entiers ensemble ne prenant pas plus de 64 bits, vous pouvez les combiner en un fichier ulong.

Dans le pire des cas, vous pouvez toujours utiliser une chaîne, tant que vous vous assurez que les trois composants sont délimités par un caractère ou une séquence qui ne se produit pas à l'intérieur des composants de la clé, par exemple, avec trois nombres, vous pouvez essayer:

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

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

jerryjvl
la source
6
Je dirais cependant que cela dépend fortement du contexte; si j'avais trois types d'entiers à combiner et que les performances n'étaient pas essentielles, cela fonctionne parfaitement bien avec un risque minimal de faire une erreur. Bien sûr, tout cela est complètement redondant à partir de .NET 4, puisque Microsoft nous fournira des types de tuple (vraisemblablement corrects!) Prêts à l'emploi.
jerryjvl
Vous pouvez même utiliser cette méthode en combinaison avec un JavaScriptSerializerpour concaténer un tableau de types chaîne et / ou entier pour vous. De cette façon, vous n'avez pas besoin de créer vous-même un caractère délimiteur.
binki
3
Cela pourrait être gênant si réel l' une des touches ( key1, key2, key3) sont des chaînes contenant le deliminator ( "#")
Greg
4

Je remplacerais 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.

John Gietzen
la source
1
IComparable n'a pas d'effet sur la façon dont les clés sont stockées ou localisées dans un Dictionary <TKey, TValue>. Tout est fait via GetHashCode () et un IEqualityComparer <T>. L'implémentation de IEquatable <T> permettra d'obtenir de meilleures performances car elle atténue la boxe causée par le EqualityComparer par défaut, qui se rabat sur la fonction Equals (object).
Dustin Campbell
J'allais mentionner GetHashCode, mais je pensais que le dictionnaire utilisait IComparable dans le cas où les HashCodes étaient identiques ... je suppose que j'avais tort.
John Gietzen
3

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;
        }
    } 
}
Michael Graczyk
la source
3
Obtenir le code de hachage est implémenté sous la forme ((item1 ^ item2) * 33) ^ item3
Michael Graczyk
2

Si votre code consommateur peut se contenter d'une interface IDictionary <>, au lieu de Dictionary, mon instinct aurait été d'utiliser un SortedDictionary <> avec un comparateur de tableau personnalisé, c'est-à-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;
    }
}

Et créez ainsi (en utilisant int [] juste pour des exemples concrets):

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