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

je suis en train de faire une recherche dans le Dictionnaire de table en C#. J'ai besoin de résoudre un 3-tuple de valeurs à une seule chaîne. J'ai essayé d'utiliser des tableaux comme clés, mais ça n'a pas marché, et je ne sais pas quoi faire d'autre. À ce stade, j'envisage de faire un dictionnaire de dictionnaires de dictionnaires, mais ce ne serait probablement pas très joli à regarder, bien que ce soit la façon dont je le ferais en javascript.

92
demandé sur Sung Kim 2009-06-05 17:56:24

7 réponses

si vous êtes sur .NET 4.0 utilisez un Tuple:

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

si ce n'est pas le cas, 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);
    }
}
99
répondu Hallgrim 2011-08-30 18:31:38

entre les approches de tuple et de dictionnaires imbriqués, il est presque toujours préférable d'opter pour les approches de tuple.

du point de vue de la maintenabilité ,

  • son 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é callee. Dans le second cas, chaque ajout, recherche, suppression, etc demandent une action de plus d'un dictionnaire.

  • de plus, si votre clé composite nécessite un champ supplémentaire (ou moins) à l'avenir, vous devrez changer le code d'un lot important dans le second cas (dictionnaire imbriqué) puisque vous devez ajouter d'autres dictionnaires imbriqués et des vérifications ultérieures.

du point de vue de la performance , la meilleure conclusion que vous puissiez tirer est de mesurer vous-même. Mais il y a quelques limites théoriques que vous pouvez considérer à l'avance:

  • dans le cas du dictionnaire emboîté, avoir un dictionnaire supplémentaire pour chaque clé (externe et interne) aura une certaine mémoire au-dessus (plus que ce que la création d'un tuple aurait).

  • dans le cas du dictionnaire emboîté, chaque action de base comme l'ajout, la mise à jour, la recherche, la suppression, etc. doivent être effectuées en deux dictionnaire. Maintenant il y a un cas où l'approche de dictionnaire imbriqué peut être plus rapide, c'est-à-dire quand les données recherchées sont absentes, puisque les dictionnaires intermédiaires peuvent contourner le calcul et la comparaison de code de hachage complet, mais là encore, il doit être chronométré pour être sûr. En présence de données, elle devrait être plus lente puisque les recherches devraient être effectuées deux fois (ou trois fois selon la nidification).

  • en ce qui concerne l'approche tuple, les tuples ne sont pas les plus performant quand ils sont destinés à être utilisés comme clés dans les ensembles depuis ses Equals et GetHashCode l'implémentation provoque la boxe pour les types de valeur .

j'utiliserais le dictionnaire tuple, mais si je veux plus de performance, j'utiliserais mon propre tuple avec une meilleure implémentation.


sur une note latérale, 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
    

    ainsi exposez indexeurs nécessaires dans votre classe de dictionnaire qui gère intérieurement les insertions et les recherches.

  2. aussi, mettre en œuvre une interface IEnumerable appropriée et fournir une méthode Add(TypeA, TypeB, TypeC, string) qui vous donnerait la syntaxe de collecte initialiseur, comme:

    new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
    { 
        { a, b, c, null }, 
        ...
    };
    
32
répondu nawfal 2017-05-23 11:54:59

la bonne façon, propre, rapide, facile et lisible est:

il suffit de faire une classe clé simple dérivée d'un tuple .

ajouter quelque chose de similaire:

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

donc vous pouvez 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é de jointure ou de groupement dans linq
  • va de cette façon, vous n'avez jamais mal saisir l'ordre de Item1, Item2, Item3 ...
  • vous n'avez besoin de se rappeler ou de regarder dans le code pour comprendre où aller pour obtenir quelque chose
  • pas besoin de passer outre est Structuralequequatable, est Structuralcomparable, IComparable, ITuple ils ont tous déjà ici
9
répondu gabba 2016-06-01 14:59:41

si pour une raison quelconque vous voulez vraiment éviter de créer votre propre classe de Tuple, ou d'utiliser on built into .NET 4.0, il y a une autre approche possible; vous pouvez combiner les trois valeurs clés ensemble dans 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 dans un ulong .

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

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

il y a évidemment une certaine composition au-dessus de cette approche, mais en fonction de ce que vous l'utilisez pour cela peut être assez trivial pour ne pas s'en soucier.

6
répondu jerryjvl 2009-06-05 14:16:01

Je surchargerais votre Tuple avec un bon GetHashCode, et je l'utiliserais comme la clé.

tant que vous surchargez les bonnes méthodes, vous devriez voir des performances décentes.

4
répondu John Gietzen 2009-06-07 12:40:01

voici le .net tuple 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;
        }
    } 
}
3
répondu Michael Graczyk 2012-06-09 08:54:47

si votre code de consommation peut se contenter d'une interface IDictionary<>, au lieu d'un dictionnaire, mon instinct aurait été d'utiliser un<> SortedDictionary avec un compareur de tableau personnalisé, i.e.:

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éer ainsi (en utilisant int[] juste pour exemple concret):

var dictionary = new SortedDictionary<int[], string>(new ArrayComparer<int>());
2
répondu mungflesh 2013-06-21 13:16:57