Comment faire pour que SortedSet mette à jour la position de l'ancienne valeur ?

Question

J'ai l'objet suivant que j'aimerais conserver dans un conteneur qui est trié lors de l'insertion et qui ne contient pas de doublons, j'utilise donc un fichier SortedSet

from sortedcontainers import SortedSet, SortedList

class R():

    def __hash__(self):
        return hash(self.person_id)

    def __eq__(self, other):
        return self.__class__ == other.__class__ and self.person_id == other.person_id

    def __nq__(self, other):
        return not (self == other)

    def __lt__(self, other):
        return other.value < self.value

    def __init__(self, person_id, value):
        self.person_id = person_id
        self.value = value

    def __repr__(self):
        return "person: %s (%s)" % (self.person_id, self.value)

x = SortedSet()

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))

print(x)

Lorsque j'exécute ce code, j'obtiens le résultat suivant, comme prévu :

SortedSet([personne : 11 (21), personne : 17 (4), personne : 13 (2), personne : 7 (-41)])

Cependant, si j'ajoute un élément supplémentaire en double, c'est-à-dire 17 :

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))
x.add(R(17, -67))

print(x)

Je m'attends à ce que l'objet R avec l'id 17 soit nommé person: 17 (4) à déplacer vers l'arrière avec valeur person: 17 (-67) comme :

SortedSet([personne : 11 (21), personne : 13 (2), personne : 7 (-41), personne : 17 (-67)])

Cependant, rien ne change :

SortedSet([personne : 11 (21), personne : 17 (4), personne : 13 (2), personne : 7 (-41)])

Comment puis-je obtenir le résultat désiré tel que décrit en utilisant une SortedSet ou tout autre conteneur qui est trié à l'insertion et qui n'a pas de doublons ?

Answer 1

La réponse de DeepSpace couvre le fonctionnement de ce système (même s'il est quelque peu inefficace). mais je vais lancer un défi de cadre ici : C'est un mauvais design.

Les ensembles (la construction logique) sont conçus pour stocker des éléments uniques. Si un élément add Si un élément ajouté à un ensemble est égal à un élément qui s'y trouve déjà, il n'y a aucune raison de remplacer l'ancien élément, car l'ancien et le nouvel élément sont identiques. équivalent . Si votre classe n'utilise pas une définition de l'égalité dans laquelle l'égalité implique la substituabilité (deux instances égales peuvent être utilisées de manière interchangeable de toutes les manières pertinentes), alors les instances ne sont pas appropriées pour être utilisées dans une classe de type set . Même sans SortedSet s'impliquer, utiliser plain set cela ne fonctionnerait pas, car set.add ne remplacera pas un élément lorsque vous insérez un élément "égal" ; ils sont tous deux équivalents après tout, alors pourquoi faire le travail supplémentaire ?

Lorsque vous avez besoin de disposer d'un concept de clés pouvant correspondre à des valeurs, où les valeurs d'une clé donnée peuvent être modifiées ultérieurement sans connaître la valeur d'origine, vous voulez un mappage ( dict -), et non un ensemble ( set -).

Kelly Bundy suggère que ce que vous voulez peut déjà exister dans le sortedcollections paquet ( ValueSortedDict ), donc j'irais avec ça si ça marche. Puisque sortedcontainers ne contient rien qui permette de remplacer les valeurs et trier sur les valeurs, il faudrait aller dans une lot de travail pour ajouter ce comportement, soit à peu près le même ordre de grandeur que de l'implémenter soi-même à partir de zéro.

---

Notes supplémentaires sur les raisons pour lesquelles cela ne fonctionne pas :

En plus du fait que votre cas d'utilisation est fondamentalement inadapté aux ensembles (le concept logique, et non pas simplement l'utilisation de l'ensemble), il est possible d'utiliser les ensembles pour des raisons de sécurité. set lui-même), SortedSet elle-même est inhabituellement inappropriée pour votre classe, car elle s'appuie implicitement sur deux invariants (dont un seul est strictement requis par Python, bien que l'autre soit généralement respecté) :

1. Requis par Python : __eq__ doit être conforme à __hash__ : Si deux éléments sont égaux, ils doit avoir le même hachage, et, dans la mesure du possible, deux éléments inégaux devraient no ont le même hachage (idéalement, le hachage devrait être basé sur les mêmes champs). __eq__ mais il est légal de le baser sur un sous-ensemble de ces champs)
2. Requis par SortedSet (et souvent assumé par d'autres choses qui fonctionnent avec des objets triés) : __eq__ doit être conforme à __lt__ (et tous les autres opérateurs de comparaison riche) : Si a == b alors a < b y b < a doivent tous deux être faux ; de même, si a < b o b < a est vrai, alors a != b . La plupart des opérations de tri en Python s'en tiennent à __lt__ exclusivement pour permettre des définitions incohérentes, mais si vous mettez les mêmes objets dans une tuple pour les comparaisons, soudainement les règles d'ordre lexicographique signifie tuple de l'entreprise __lt__ s'appuie à la fois sur le __lt__ y __eq__ de votre classe, donc en pratique vous voulez qu'ils soient cohérents de toute façon.

Votre classe viole la règle n°2 ; les règles de triage sont complètement sans rapport avec la définition de l'égalité. SortedSet s'embrouille ici, déterminant l'unicité en se basant sur __hash__ + __eq__ et de commander avec __lt__ mais, dans certaines circonstances (par exemple, lors de la suppression d'éléments), il s'appuie sur la fonction __lt__ être conforme à __eq__ . Plus précisément, après avoir retiré de l'interne set (en utilisant __hash__ + __eq__ ) qu'il retire ensuite de la liste interne SortedList qui se divise en deux pour trouver l'élément à retirer, en utilisant __lt__ et confirme qu'il a trouvé le bon élément en effectuant un contrôle d'égalité, en utilisant la fonction __eq__ . Puisque __eq__ y __lt__ ne sont pas cohérentes (elles ne correspondent que si vous essayez de supprimer une R avec le même person_id y value ), il ne trouve jamais la valeur qu'il essaie de supprimer, et il lève une exception.

Answer 2

Vous pouvez sous-classer SortedSet en remplaçant son add y remove méthodes. Nous devons surcharger remove car l'implémentation originale utilise self._list.remove qui échouera parce que les deux R les objets ne seront pas identifiés comme étant égaux.

class MySortedSet(SortedSet):
    def add(self, value):
        if value in self:
            self.remove(value)
        super().add(value)

    def remove(self, value):
        self._set.remove(value)
        for index, e in enumerate(self._list[:]):
            if hash(e) == hash(value):
                self._list.pop(index)
                break

x = MySortedSet()

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))
x.add(R(17, -67))

print(x)

sorties

MySortedSet([person: 11 (21), person: 13 (2), person: 7 (-41), person: 17 (-67)])