Manière pythonique d'ignorer le dernier élément lors de la différence d'ensemble

11

Disons que j'ai deux set()s:

a = {('1', '2', '3', 'a'), ('1', '2', '4', 'a'), ('1', '2', '5', 'b')}
b = {('1', '2', '3', 'b'), ('1', '2', '4', 'b'), ('1', '2', '6', 'b')}

Maintenant, ce que je veux faire est de trouver la différence définie b \ amais en ignorant le dernier élément de chaque tuple. C'est comme faire quelque chose comme ça:

a = {('1', '2', '3'), ('1', '2', '4'), ('1', '2', '5')}
b = {('1', '2', '3'), ('1', '2', '4'), ('1', '2', '6')}

In[1]: b - a
Out[1]: {('1', '2', '6')}

Production attendue:

b \ a = {('1', '2', '6', 'b')}

Existe-t-il un moyen évident / pythonique d'y parvenir sans avoir à parcourir manuellement chaque ensemble et à les comparer tuple[:3]?

Grajdeanu Alex.
la source
3
Ma pensée initiale est d'en faire des classes, de définir un opérateur de comparaison
Kenny Ostrom
2
sous set- classe et écraser l'opération de différence. Il n'y a pas de solution prête à l'emploi que je sache et je doute qu'une existe.
Ev. Kounis
Il n'y a pas de "clé = ..." ou quelque chose de similaire (comme pour le tri (..)) pour les ensembles. Les tuples sont immuables et lavables et sont comparés en fonction de leur hachage. La suppression d'un élément annulerait le hachage. Donc non - pas possible. Si vous n'avez pas besoin de la valeur, vous pouvez créer des ensembles en 3 parties:aa = { t[:3] for t in a }
Patrick Artner
2
@ AK47 La différence (d'ensemble) entre deux ensembles S et T s'écrit S ∖ T, et signifie l'ensemble qui se compose des éléments de S qui ne sont pas des éléments de T: x∈S ∖ T⟺x∈S∧x∉T
Alex Grajdeanu.
Sous tuple- classe et remplacement de l'opérateur de différence
Pynchia

Réponses:

10

Voici comment vous pouvez écrire votre propre classe pour remplacer le comportement de hachage normal d'un tuple:

a_data = [('1', '2', '3', 'a'), ('1', '2', '4', 'a'), ('1', '2', '5', 'b')]
b_data = [('1', '2', '3', 'b'), ('1', '2', '4', 'b'), ('1', '2', '6', 'b')]

class HashableIgnoresLastElement(tuple):
    def __eq__(self, other):
        return self[:-1] == other[:-1]

    def __hash__(self):
        return hash(self[:-1])

a = set(map(HashableIgnoresLastElement, a_data))
b = set(map(HashableIgnoresLastElement, b_data))

print(b - a)

avec sortie

{('1', '2', '6', 'b')}

Pour modifier le comportement des ensembles de tuples, nous devons modifier la façon dont les tuples sont hachés.

De ,

Un objet est lavable s'il a une valeur de hachage qui ne change jamais pendant sa durée de vie (il a besoin d'une __hash__()méthode), et peut être comparée à d'autres objets (il a besoin d'une __eq__()méthode). Les objets hachables qui se comparent égaux doivent avoir la même valeur de hachage.

La capacité de hachage rend un objet utilisable comme clé de dictionnaire et membre d'ensemble, car ces structures de données utilisent la valeur de hachage en interne.

Donc, pour que le hachage ignore le dernier élément, nous devons surcharger les méthodes de dunder __eq__et de __hash__manière appropriée. Cela ne finit pas par être si difficile car tout ce que nous avons à faire est de couper le dernier élément et de déléguer ensuite les méthodes appropriées d'une normale tuple.

Lectures complémentaires:

Izaak van Dongen
la source
1
Très propre! Pourriez-vous également décrire un peu comment cela fonctionne? Cela pourrait valoir la peine pour ceux qui liront cette solution.
Alex Grajdeanu.
@GrajdeanuAlex. J'ai ajouté une courte explication :). En réalité, il s'agit simplement de combiner des morceaux de surcharge d'opérateur et le fonctionnement du hachage en Python.
Izaak van Dongen
2

Voici une approche définissant aet bavec des listes plutôt que des ensembles, car il me semble que la solution la plus simple implique l'indexation b:

a = [('1', '2', '3', 'a'), ('1', '2', '4', 'a'), ('1', '2', '5', 'b')]
b = [('1', '2', '3', 'b'), ('1', '2', '4', 'b'), ('1', '2', '6', 'b')]

# reconstruct the sets of tuples removing the last elements
a_ = {tuple(t) for *t, _ in a}
b_ = [tuple(t) for *t, _ in b]

# index b based on whether an element in a_
[b[ix] for ix, j in enumerate(b_) if j not in a_]
# [('1', '2', '6', 'b')]
yatu
la source
1
Si je ne me trompe pas, c'est O (n), car j'utilise un ensemble pour la recherche. Bien que je ne pense que la réponse de Izaak van Dongen est beaucoup plus élégant @konrad
YATU
1
Vous avez tout à fait raison, l'utilisation (et l'énumération sur) une liste m'a déstabilisé, mais bien sûr, une différence d'ensemble doit également être répétée sur le premier ensemble.
Konrad Rudolph
1

Les décors fonctionnent bien. Ce sont vos données qui ne fonctionnent pas correctement. S'ils sont différents mais qu'ils sont en fait les mêmes, définissez un type de données qui se comporte comme vous le souhaitez. Ensuite, le jeu fonctionne bien seul.

class thing:
    def __init__(self, a, b, c, d):
        self.a, self.b, self.c, self.d = a, b, c, d

    def __repr__(self):
        return (str((self.a, self.b, self.c, self.d)))

    def __hash__(self):
        return hash((self.a, self.b, self.c))

    def __eq__(self, other):
        return self.a == other.a and self.b == other.b and self.c == other.c       

a = {thing('1', '2', '3', 'a'), thing('1', '2', '4', 'a'), thing('1', '2', '5', 'b')}
b = {thing('1', '2', '3', 'b'), thing('1', '2', '4', 'b'), thing('1', '2', '6', 'b')}
print (b - a)

{('1', '2', '6', 'b')}

Kenny Ostrom
la source
3
Vous avez défini __repr__et __hash__en termes de tuples, mais pas __eq__. Ne serait-il pas plus court d'utiliser des tuples ici aussi? En fait, vous pouvez utiliser le découpage ici et __hash__dedans pour raccourcir davantage le code.
Konrad Rudolph
Oui, le simple sous-classement des tuples a été une grande amélioration de la question posée.
Kenny Ostrom