«Set» devrait-il avoir une méthode Get?

22

Ayons cette classe C # (ce serait presque la même chose en Java)

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}

   public override bool Equals(object obj) {
        var item = obj as MyClass;

        if (item == null || this.A == null || item.A == null)
        {
            return false;
        }
        return this.A.equals(item.A);
   }

   public override int GetHashCode() {
        return A != null ? A.GetHashCode() : 0;
   }
}

Comme vous pouvez le voir, l'égalité de deux instances de MyClassdépend Auniquement de. Il peut donc y avoir deux instances égales, mais détenant différentes informations dans leur Bpropriété.

Dans une bibliothèque de collection standard de nombreux langages (y compris C # et Java, bien sûr), il y a un Set( HashSeten C #), qui une collection, qui peut contenir au plus un élément de chaque ensemble d'instances égales.

On peut ajouter des éléments, supprimer des éléments et vérifier si l'ensemble contient un élément. Mais pourquoi est-il impossible d'obtenir un élément particulier de l'ensemble?

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
    //something
}

//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye

La seule façon de récupérer mon article est d'itérer sur toute la collection et de vérifier l'égalité de tous les articles. Cependant, cela prend du O(n)temps au lieu de O(1)!

Jusqu'à présent, je n'ai trouvé aucune langue qui prend en charge get à partir d'un ensemble. Tous les langages "courants" que je connais (Java, C #, Python, Scala, Haskell ...) semblent être conçus de la même manière: vous pouvez ajouter des éléments, mais vous ne pouvez pas les récupérer. Y a-t-il une bonne raison pour laquelle toutes ces langues ne prennent pas en charge quelque chose d'aussi simple et évidemment utile? Ils ne peuvent pas tout simplement se tromper, non? Y a-t-il des langues qui le prennent en charge? Peut-être que récupérer un élément particulier d'un ensemble est faux, mais pourquoi?


Il y a quelques questions liées au SO:

/programming/7283338/getting-an-element-from-a-set

/programming/7760364/how-to-retrieve-actual-item-from-hashsett

vojta
la source
12
C ++ std::setprend en charge la récupération d'objets, donc tous les langages "courants" ne sont pas comme vous le décrivez.
Rétablir Monica
17
Si vous prétendez (et codez) que "l'égalité de deux instances de MyClass ne dépend que de A", alors une autre instance qui a la même valeur A et un B différent est effectivement "cette instance particulière", puisque vous avez vous-même défini qu'elles sont égales et les différences en B n'ont pas d'importance; le conteneur est "autorisé" à retourner l'autre instance car il est égal.
Peteris
7
Histoire vraie: en Java, de nombreuses Set<E>implémentations sont juste Map<E,Boolean>à l'intérieur.
corsiKa
10
parlant à la personne A : "Salut, pouvez-vous amener la personne A ici s'il vous plaît"
Brad Thomas
7
Cela casse la réflexivité ( a == btoujours vraie) au cas où this.A == null. Le if (item == null || this.A == null || item.A == null)test est "exagéré" et vérifie beaucoup, peut-être afin de créer artificiellement du code "de haute qualité". Je vois ce genre de "dépassement" et d'être trop correct tout le temps sur la révision du code.
usr

Réponses:

66

Le problème ici n'est pas qu'il HashSetmanque une Getméthode, c'est que votre code n'a aucun sens du point de vue du HashSettype.

Cette Getméthode est effectivement "obtenez-moi cette valeur, s'il vous plaît", à laquelle les gens du framework .NET répondraient raisonnablement, "hein? Vous avez déjà cette valeur <confused face />".

Si vous souhaitez stocker des éléments, puis les récupérer en fonction de la correspondance avec une autre valeur légèrement différente, utilisez-la Dictionary<String, MyClass>comme vous pouvez alors:

var mset = new Dictionary<String, MyClass>();
mset.Add("Hello", new MyClass {A = "Hello", B = "Bye"});

var item = mset["Hello"];
Console.WriteLine(item.B); // will print Bye

Les informations d'égalité fuient de la classe encapsulée. Si je voulais changer l'ensemble des propriétés impliquées dans Equals, je devrais changer le code à l'extérieur MyClass...

Eh bien oui, mais c'est parce que ça MyClassdément avec le principe du moindre étonnement (POLA). Avec cette fonctionnalité d'égalité encapsulée, il est tout à fait raisonnable de supposer que le code suivant est valide:

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) 
{
    // this code is unreachable.
}

Pour éviter cela, MyClassdoit être clairement documenté quant à sa forme étrange d'égalité. Cela fait, il n'est plus encapsulé et changer le fonctionnement de l'égalité romprait le principe ouvert / fermé. Ergo, il ne devrait pas changer et Dictionary<String, MyClass>est donc une bonne solution pour cette exigence étrange.

David Arno
la source
2
@vojta, Dans ce cas, utilisez Dictionary<MyClass, MyClass>car il récupérera alors la valeur en fonction d'une clé qui utilise MyClass.Equals.
David Arno
8
Je voudrais utiliser un Dictionary<MyClass, MyClass>fourni avec un approprié IEqualityComparer<MyClass>, et retirer la relation d'équivalence de MyClassPourquoi faut MyClass-il connaître cette relation sur ses instances?
Caleth
16
@vojta et le commentaire là-bas: " meh. Remplacer l'implémentation d'égaux pour que les objets non égaux soient" égaux "est le problème ici. Demander une méthode qui dit" obtenez-moi l'objet identique à cet objet ", puis s'attendre à ce qu'un objet non identique soit retourné semble fou et facile à provoquer des problèmes de maintenance "est sur place. C'est souvent le problème avec SO: les réponses sérieusement erronées sont votées par des gens qui n'ont pas réfléchi aux implicants de leur désir de trouver une solution rapide à leur code cassé ...
David Arno
6
@DavidArno: un peu inévitable mais aussi longtemps que nous persistons à utiliser des langages qui distinguent l'égalité et l'identité ;-) object to this object ", mais" get me the canonical object that is equal to this object ". Quiconque pense que HashSet.Get dans ces langues signifierait nécessairement «obtenez-moi l'objet identique» est déjà gravement dans l'erreur.
Steve Jessop
4
Cette réponse contient de nombreuses déclarations générales telles que ...reasonable to assume.... Tout cela peut être vrai dans 99% des cas, mais la possibilité de récupérer un élément d'un ensemble peut toujours être utile. Le code du monde réel ne peut pas toujours adhérer aux principes de POLA, etc. Par exemple, si vous dédupliquez des chaînes sans tenir compte de la casse, vous souhaiterez peut-être obtenir l'élément "maître". Dictionary<string, string>est une solution de contournement, mais cela coûte de la perf.
usr
24

Vous avez déjà l'élément qui est "dans" l'ensemble - vous l'avez passé comme clé.

"Mais ce n'est pas le cas que j'ai appelé Ajouter avec" - Oui, mais vous avez spécifiquement affirmé qu'ils étaient égaux.

A Setest également un cas particulier de a Map|Dictionary, avec void comme type de valeur (enfin les méthodes inutiles ne sont pas définies, mais cela n'a pas d'importance).

La structure de données que vous recherchez est un Dictionary<X, MyClass>endroit où en Xquelque sorte obtient le As des MyClasses.

Le type de dictionnaire C # est agréable à cet égard, car il vous permet de fournir un IEqualityComparer pour les clés.

Pour l'exemple donné, j'aurais ce qui suit:

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}
}

public class MyClassEquivalentAs : IEqualityComparer<MyClass>{
   public override bool Equals(MyClass left, MyClass right) {
        if (Object.ReferenceEquals(left, null) && Object.ReferenceEquals(right, null))
        {
            return true;
        }
        else if (Object.ReferenceEquals(left, null) || Object.ReferenceEquals(right, null))
        {
            return false;
        }
        return left.A == right.A;
   }

   public override int GetHashCode(MyClass obj) {
        return obj?.A != null ? obj.A.GetHashCode() : 0;
   }
}

Utilisé ainsi:

var mset = new Dictionary<MyClass, MyClass>(new MyClassEquivalentAs());
var bye = new MyClass {A = "Hello", B = "Bye"};
var seeyou = new MyClass {A = "Hello", B = "See you"};
mset.Add(bye);

if (mset.Contains(seeyou)) {
    //something
}

MyClass item = mset[seeyou];
Console.WriteLine(item.B); // prints Bye
Caleth
la source
Il existe un certain nombre de situations où il peut être avantageux pour le code qui a un objet correspondant à la clé, de le remplacer par une référence à l'objet utilisé comme clé. Par exemple, si de nombreuses chaînes sont connues pour correspondre à une chaîne dans une collection hachée, le remplacement des références à toutes ces chaînes par des références à celle de la collection peut être un gain de performances.
supercat
@supercat aujourd'hui qui est réalisé avec un Dictionary<String, String>.
MikeFHay
@MikeFHay: Oui, mais il semble un peu inélégant de devoir stocker chaque référence de chaîne deux fois.
supercat
2
@supercat Si vous voulez dire une chaîne identique , c'est juste un internement de chaîne. Utilisez les éléments intégrés. Si vous voulez dire une sorte de représentation "canonique" (qui ne peut pas être obtenue en utilisant des techniques simples de changement de casse, etc.), cela ressemble à vous avez essentiellement besoin d'un index (dans le sens où les DB utilisent le terme). Je ne vois pas de problème avec le stockage de chaque "forme non canonique" comme une clé qui correspond à une forme canonique. (Je pense que cela s'applique également si la forme "canonique" n'est pas une chaîne.) Si ce n'est pas de cela que vous parlez, alors vous m'avez complètement perdu.
jpmc26
1
Personnalisé Compareret Dictionary<MyClass, MyClass>est une solution pragmatique. En Java, la même chose peut être obtenue par TreeSetou TreeMapplus personnalisée Comparator.
Markus Kull
19

Votre problème est que vous avez deux concepts contradictoires d'égalité:

  • égalité réelle, où tous les champs sont égaux
  • définir l'égalité d'appartenance, où seul A est égal

Si vous souhaitez utiliser la relation d'égalité réelle dans votre ensemble, le problème de la récupération d'un élément particulier de l'ensemble ne se pose pas - pour vérifier si un objet est dans l'ensemble, vous avez déjà cet objet. Il n'est donc jamais nécessaire de récupérer une instance particulière d'un ensemble, en supposant que vous utilisez la relation d'égalité correcte.

Nous pourrions également faire valoir qu'un ensemble est un type de données abstrait qui est défini uniquement par la relation S contains xou x is-element-of S(«fonction caractéristique»). Si vous voulez d'autres opérations, vous ne recherchez pas réellement un ensemble.

Ce qui se produit assez souvent - mais ce n'est pas un ensemble - est que nous regroupons tous les objets dans des classes d'équivalence distinctes . Les objets de chaque classe ou sous-ensemble sont uniquement équivalents, pas égaux. Nous pouvons représenter chaque classe d'équivalence à travers n'importe quel membre de ce sous-ensemble, et il devient alors souhaitable de récupérer cet élément représentant. Ce serait un mappage de la classe d'équivalence à l'élément représentatif.

En C #, un dictionnaire peut utiliser une relation d'égalité explicite, je pense. Sinon, une telle relation peut être implémentée en écrivant une classe wrapper rapide. Pseudocode:

// The type you actually want to store
class MyClass { ... }

// A equivalence class of MyClass objects,
// with regards to a particular equivalence relation.
// This relation is implemented in EquivalenceClass.Equals()
class EquivalenceClass {
  public MyClass instance { get; }
  public override bool Equals(object o) { ... } // compare instance.A
  public override int GetHashCode() { ... } // hash instance.A
  public static EquivalenceClass of(MyClass o) { return new EquivalenceClass { instance = o }; }
}

// The set-like object mapping equivalence classes
// to a particular representing element.
class EquivalenceHashSet {
  private Dictionary<EquivalenceClass, MyClass> dict = ...;
  public void Add(MyClass o) { dict.Add(EquivalenceClass.of(o), o)}
  public bool Contains(MyClass o) { return dict.Contains(EquivalenceClass.of(o)); }
  public MyClass Get(MyClass o) { return dict.Get(EquivalenceClass.of(o)); }
}
amon
la source
"récupérer une instance particulière d'un ensemble" Je pense que cela traduirait ce que vous voulez dire plus directement si vous changiez "instance" en "membre". Juste une petite suggestion. =) +1
jpmc26
7

Mais pourquoi est-il impossible d'obtenir un élément particulier de l'ensemble?

Parce que ce n'est pas à cela que servent les ensembles.

Permettez-moi de reformuler l'exemple.

"J'ai un HashSet dans lequel je veux stocker des objets MyClass et je veux pouvoir les obtenir en utilisant la propriété A qui est égale à la propriété A de l'objet".

Si remplacer "HashSet" par "Collection", "objets" par "Valeurs" et "propriété A" par "Clé", la phrase devient:

"J'ai une collection dans laquelle je veux stocker les valeurs de MyClass et je veux pouvoir les obtenir en utilisant la clé qui est égale à la clé de l'objet".

Ce qui est décrit est un dictionnaire. La véritable question posée est "Pourquoi ne puis-je pas traiter HashSet comme un dictionnaire?"

La réponse est qu'ils ne sont pas utilisés pour la même chose. La raison d'utiliser un ensemble est de garantir l'unicité de son contenu individuel, sinon vous pouvez simplement utiliser une liste ou un tableau. Le comportement décrit dans la question est à quoi sert un dictionnaire. Tous les concepteurs de langage n'ont pas foiré. Ils ne fournissent pas de méthode get car si vous avez l'objet et qu'il est dans l'ensemble, ils sont équivalents, ce qui signifie que vous "obtiendrez" un objet équivalent. Faire valoir que HashSet devrait être implémenté de telle manière que vous puissiez "obtenir" des objets non équivalents que vous avez définis comme égaux est un non-démarreur lorsque les langages fournissent d'autres structures de données qui vous permettent de le faire.

Une note sur le POO et les commentaires / réponses sur l'égalité. Il est normal que la clé du mappage soit une propriété / un membre de la valeur stockée dans un dictionnaire. Par exemple: avoir un Guid comme clé et aussi la propriété qui est utilisée pour la méthode equals est parfaitement raisonnable. Ce qui n'est pas raisonnable, c'est d'avoir des valeurs différentes pour le reste des propriétés. Je trouve que si je vais dans cette direction, j'ai probablement besoin de repenser ma structure de classe.

Old Fat Ned
la source
6

Dès que vous remplacez égal à, il vaut mieux remplacer le code de hachage. Dès que vous avez fait cela, votre "instance" ne devrait plus jamais changer d'état interne.

Si vous ne remplacez pas égal et que l'identité d'objet de la machine virtuelle hashcode est utilisée pour déterminer l'égalité. Si vous placez cet objet dans un ensemble, vous pouvez le retrouver.

La modification d'une valeur d'un objet qui est utilisée pour déterminer l'égalité entraînera la non traçabilité de cet objet dans les structures basées sur le hachage.

Un poseur sur A est donc dangereux.

Maintenant, vous n'avez pas B qui ne participe pas à l'égalité. Le problème ici n'est pas sémantiquement et techniquement. Parce que changer techniquement B est neutre au fait de l'égalité. Sémantiquement, B doit être quelque chose comme un drapeau "version".

Le point est:

Si vous avez deux objets égaux à A mais pas B, vous supposez que l'un de ces objets est plus récent que l'autre. Si B n'a pas d'informations sur la version, cette hypothèse est masquée dans votre algorithme QUAND vous décidez de "remplacer / mettre à jour" cet objet dans un ensemble. Cet emplacement de code source où cela se produit peut ne pas être évident, donc un développeur aura du mal à identifier la relation entre l'objet X et l'objet Y qui diffère de X en B.

Si B possède des informations sur la version, vous exposez l'hypothèse qui n'était auparavant implicitement dérivable que du code. Vous pouvez maintenant voir que cet objet Y est une version plus récente de X.

Pensez à vous: votre identité reste toute votre vie, peut-être que certaines propriétés changent (par exemple la couleur de vos cheveux ;-)). Bien sûr, vous pouvez supposer que si vous avez deux photos, une avec des cheveux bruns et une avec des cheveux gris, vous pourriez être plus jeune sur la photo avec des cheveux bruns. Mais peut-être que vous avez coloré vos cheveux? Le problème est: VOUS savez peut-être que vous avez coloré vos cheveux. Les autres? Pour mettre cela dans un contexte valide, vous devez introduire l'âge de la propriété (version). Alors vous vous êtes sémantiquement explicite et sans ambiguïté.

Pour éviter l'opération cachée "remplacer l'ancien par un nouvel objet", un ensemble ne doit pas avoir de méthode get. Si vous voulez un comportement comme celui-ci, vous devez le rendre explicite en supprimant l'ancien objet et en ajoutant le nouvel objet.

BTW: Qu'est-ce que cela devrait signifier si vous passez un objet qui est égal à l'objet que vous souhaitez obtenir? Ça n'a pas de sens. Gardez votre sémantique propre et ne le faites pas bien que techniquement personne ne vous gênera.

oopexpert
la source
7
"Dès que vous remplacez égal à, vous feriez mieux de remplacer le code de hachage. Dès que vous avez fait cela, votre" instance "ne devrait plus jamais changer d'état interne." Cette déclaration vaut +100, juste là.
David Arno
+1 pour avoir souligné les dangers de l'égalité et du code de hachage en fonction de l'état mutable
Hulk
3

Plus précisément en Java, a HashSetété initialement implémenté en utilisant de HashMaptoute façon, et en ignorant simplement la valeur. La conception initiale ne prévoyait donc aucun avantage à fournir une méthode get HashSet. Si vous souhaitez stocker et récupérer une valeur canonique parmi divers objets qui sont égaux, alors vous utilisez simplement vous- HashMapmême.

Je ne me suis pas tenu au courant de ces détails d'implémentation, donc je ne peux pas dire si ce raisonnement s'applique toujours en Java, encore moins en C # etc. Mais même s'il a HashSetété réimplémenté pour utiliser moins de mémoire que HashMap, en tout cas, serait un changement de rupture pour ajouter une nouvelle méthode à l' Setinterface. C'est donc beaucoup de peine pour un gain que tout le monde ne considère pas comme intéressant.

Steve Jessop
la source
Eh bien, en Java, il pourrait être possible de fournir une defaultimplémentation pour le faire sans interruption. Cela ne semble tout simplement pas un changement terriblement utile.
Hulk
@Hulk: Je peux me tromper, mais je pense que toute implémentation par défaut serait terriblement inefficace, car comme le dit le questionneur, "la seule façon de récupérer mon élément est d'itérer sur l'ensemble de la collection et de vérifier tous les éléments pour leur égalité". Donc bon point, vous pouvez le faire d'une manière rétrocompatible, mais en ajoutant un gotcha que la fonction get résultante ne garantit que l'exécution dans les O(n)comparaisons même si la fonction de hachage donne une bonne distribution. Ensuite, les implémentations Setqui remplacent l'implémentation par défaut dans l'interface, y compris HashSet, pourraient donner une meilleure garantie.
Steve Jessop
D'accord - je ne pense pas que ce serait une bonne idée. Il y aurait cependant des priorités pour ce type de comportement - List.get (int index) ou - pour choisir une implémentation par défaut ajoutée récemment List.sort . L'interface offre des garanties de complexité maximale, mais certaines implémentations peuvent faire beaucoup mieux que d'autres.
Hulk
2

Il existe une langue majeure dont l'ensemble a la propriété que vous souhaitez.

En C ++, std::setest un ensemble ordonné. Il a une .findméthode qui recherche l'élément en fonction de l'opérateur de commande <ou de la bool(T,T)fonction binaire que vous fournissez. Vous pouvez utiliser find pour implémenter l'opération get que vous souhaitez.

En fait, si la bool(T,T)fonction que vous fournissez possède un indicateur spécifique ( is_transparent), vous pouvez passer des objets d'un autre type pour lesquels la fonction a des surcharges. Cela signifie que vous n'avez pas à coller le deuxième champ "fictif" de données dans le deuxième champ, assurez-vous simplement que l'opération de commande que vous utilisez peut commander entre les types de recherche et de type ensemble.

Cela permet une efficacité:

std::set< std::string, my_string_compare > strings;
strings.find( 7 );

my_string_compare comprend comment ordonner les entiers et les chaînes sans d'abord convertir l'entier en chaîne (à un coût potentiel).

Pour unordered_set(l'ensemble de hachage C ++), il n'y a pas encore d'indicateur transparent équivalent. Vous devez passer un Tà une unordered_set<T>.findméthode. Il pourrait être ajouté, mais les hachages nécessitent== et un hachage, contrairement aux ensembles ordonnés qui nécessitent simplement une commande.

Le modèle général est que le conteneur effectuera la recherche, puis vous donnera un "itérateur" pour cet élément dans le conteneur. À quel moment vous pouvez récupérer l'élément dans l'ensemble, le supprimer, etc.

En bref, les conteneurs standard de toutes les langues n'ont pas les défauts que vous décrivez. Les conteneurs basés sur itérateur de la bibliothèque standard C ++ n'existent pas, et au moins certains des conteneurs existaient avant les autres langages que vous avez décrits, et la possibilité de faire un get encore plus efficacement que la façon dont vous décrivez a même été ajoutée. Il n'y a rien de mal à votre conception ou à vouloir cette opération; les concepteurs des ensembles que vous utilisez n'ont tout simplement pas fourni cette interface.

Conteneurs standard C ++ conçus pour envelopper proprement les opérations de bas niveau du code C équivalent roulé à la main, qui a été conçu pour correspondre à la façon dont vous pouvez l'écrire efficacement dans l'assemblage. Ses itérateurs sont une abstraction de pointeurs de style C. Les langues que vous mentionnez se sont toutes éloignées des pointeurs en tant que concept, donc elles n'ont pas utilisé l'abstraction de l'itérateur.

Il est possible que le fait que C ++ n'ait pas cette faille soit un accident de conception. Le chemin centré sur l'itérateur signifie que pour interagir avec un élément dans un conteneur associatif, vous obtenez d'abord un itérateur sur l'élément, puis vous utilisez cet itérateur pour parler de l'entrée dans le conteneur.

Le coût est qu'il existe des règles d'invalidation d'itération que vous devez suivre, et certaines opérations nécessitent 2 étapes au lieu d'une (ce qui rend le code client plus bruyant). L'avantage est que l'abstraction robuste permet une utilisation plus avancée que celles que les concepteurs d'API avaient à l'esprit à l'origine.

Yakk
la source