Dictionnaire où plusieurs clés sont associés à la même valeur

Comment le déclarer

Le problème exposé dans ce sujet a été résolu.

Salut à tous,

Je me pose des questions (existentielles ?) sur la déclaration d’un dictionnaire où plusieurs clés sont associés à la même valeur. On pourrait faire ce code.

1
dic = {'a': 2, 'b': 2, 'c':2, 'd': 3}

Mais si on décide de changer la valeur associée, il faudrait faire de multiples changements. Sinon, on pourrait faire ça.

1
2
dic = {'d': 3}
dic['a'] = dic['b'] = dic['c'] = 2

Mais c’est quand même plus lourd. Et finalement, on pourrait utiliser une variable pour la valeur 2.

1
2
DEUX = 2
dic = {'a': DEUX, 'b': DEUX, 'c': DEUX, 'd':DEUX}

Mais il y a-t-il une autre méthode que j’ai raté qui permettrait de faire quelque chose du genre {'a', 'b', 'c': 2} ?

Merci d’avance pour vos réponses. :)

+0 -0

Bonjour,

Ça semble être un problème existentiel mais je ne le saisis pas bien.

Ton soucis c’est que dans ton code tu associes plusieurs clés à une même valeur, que tu pourrais à l’avenir modifier cette valeur dans ton programme et que tu voudrais que ça se fasse le plus simplement possible ?

Tu aurais un exemple de cas concret où ce « problème » se poserait ?

Merci pour vos réponses.

Je n’ai pas de programme où j’en ai besoin, je me posais juste la question. Mais voici un exemple (mauvais je pense) où ça pourrait être utile.

On a un endroit où on demande à l’utilisateur de rentrer une caractéristique, mais il y a plein de manières d’écrire cette caractéristique. Si c’est par exemple le sexe, on aurait garçon, homme, M, H, garcon, etc. On aurait alors

1
2
dic = {'H': 'H', 'M': 'H', etc.}
sexe = dic[sexe] 

Dans ce genre de cas, j’imagine que l’« inverse » du dictionnaire donné par @victor, correspondrait bien, s’il y a une manière simple d’obtenir la clé associé à un élément du tableau. Ici, si on avait {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}, il faudrait pouvoir obtenir 'H' facilement à partir de ’homme’.

+0 -0

Si tu as au départ le dictionnaire {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']} qui te permet d’éviter les répétitions, il est facile d’en calculer l’« inverse ».

1
2
3
>>> dic = {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}
>>> {value: key for key, values in dic.items() for value in values}
{'homme': 'H', 'H': 'H', 'h': 'H', 'femme': 'F', 'féminin': 'F', 'f': 'F'}

Effectivement.

Même si ce n’est pas trop le sujet, j’imagine qu’il y a une méthode plus Pythonesque pour cet exemple, non ?

+0 -0

Pour récupérer la clé du dictionnaire à partir d’une valeur ? Si oui, je verrais bien quelque chose comme ceci (qui peut surement être amélioré).

1
2
3
4
5
6
7
dic = {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}
gender = input()
gender_code = [k for k, v in dic.items() if gender in v]
try:
    gender_code = gender_code[0]
except KeyError:
    print("Entrée invalide.")
+0 -0

Le one-liner d’entwanne me semble déjà très pythonique. :)

Dans ce genre de cas, j’imagine que l’« inverse » du dictionnaire donné par @victor, correspondrait bien, s’il y a une manière simple d’obtenir la clé associé à un élément du tableau. Ici, si on avait {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}, il faudrait pouvoir obtenir 'H' facilement à partir de ’homme’.

Karnaj

Certes, mais pour ça tu gardes simplement le dict et son inverse synchronisés en tout temps, ou tu calcules à la volée celui que tu utilises le moins souvent. La RAM est pas cher, autant les garder les 2 en tout temps.

Ce que tu décris est quelque chose qu’on utilise parfois, y’a pas de mal à faire ça. Parfois des libs fournissent ça, par exemple en JS :

1
2
3
4
var object = { 'a': 1, 'b': 2, 'c': 1 };

_.invertBy(object);
// => { '1': ['a', 'c'], '2': ['b'] }

C’est notamment ce qu’on appelle un inverted index dans le vocabulaire des moteurs de recherche / information retrieval. C’est notamment ce qu’il y a derrière le moteur de recherche de ZdS : d’un côté on a le contenu de tous les posts dans la base de donnée, d’un autre côté on a un index mot => [post1, post2, …] associant à chaque mot une liste de contenus qui contiennent ce mot.

+1 -0

La description de ton problème me fait typiquement penser à une structure Union-find, couplée par exemple à un dictionnaire : tu peux regrouper des clefs ensemble dans ton union-find (par exemple, 'a', 'b' et 'c'), et étant donnée une clef, trouver à quelle classe elle appartient et utiliser cette classe comme clef de ton dictionnaire pour connaître la valeur associée.

La solution proposée par victor et entwanne (deux dictionnaires, dans les deux sens) est un peu différente, et j’ai l’impression qu’elle répond assez bien au problème « je veux pouvoir grouper une clef avec une autre » : on récupère la valeur X associée au groupe et on l’affecte à la nouvelle clef à grouper dans le dictionnaire direct, et on ajoute cette clef à grouper dans la valeur associée à X dans le dictionnaire indirect tout en l’enlevant de son ancienne valeur. Tout est en temps constant.

Ça permet aussi de résoudre efficacement le problème de « je veux pouvoir connaître toutes les clefs auxquelles est associée une certaine valeur » (sans reparcourir tout le dictionnaire, ce qui serait particulièrement inefficace), mais j’ai l’impression qu’il ne fait pas partie de ce que tu demandes (après le problème XY, la solution YZ ? :-D) Si on met de côté les groupes de clefs, c’est même la solution évidente pour résoudre ce problème, qui peut en effet aussi s’écrire comme « je veux une association clef/valeur mais aussi une association valeur/clef ».

Par contre, pour changer une valeur associée à un groupe, c’est plus compliqué. Le dictionnaire indirect te permet d’éviter de parcourir tout ton dictionnaire direct, mais il faut quand même, dans le dictionnaire direct, changer la valeur associée à chaque élément de ton groupe. Pan, $O(n)$ : la même complexité que si tu utilisais des bêtes listes d’association.

La solution avec l’union-find te permet d’éviter ça et d’avoir du $O(\log n)$ un peu partout, pour un coût en mémoire qui a l’air à peu près similaire. C’est vraiment un cas d’école d’utilisation de cette structure.

Note qu’il reste à mon avis quelque chose de pas clair dans la définition de ton problème : qu’est-ce qui se passe si par hasard deux clefs ont la même valeur associée alors que tu ne voulais pas les grouper, et que tu veux changer la valeur d’une des deux ? Est-ce que la deuxième veut changer aussi ? C’est difficile de répondre à ta place, et tu n’as pas donné suffisamment d’informations sur ton problème de départ pour savoir, mais mon intuition est que le comportement où on groupe les clefs explicitement ou pas du tout est plus logique. Si tu veux retrouver l’autre comportement, ajouter un union-find aux doubles dictionnaires de victor m’a l’air d’être la bonne solution (quand je change une valeur, je vérifie si elle n’est pas déjà présente ailleurs, et le cas échéant je fusionne les deux classes. La complexité globale de la mise à jour reste la même, c’est informagique.)

PS : une recherche très rapide « union find python » me donne pas mal de résultats, dont aucun ne me semble être universellement validé par la communauté. Ça fait trop longtemps que je n’ai pas utilisé sérieusement ce langage pour t’en proposer une, mais je suis à peu près certain qu’il y en a au moins une de qualité dans le lot.

+0 -0

Je n’avais pas du tout penser à du Union-Find pour ça, mais ouais c’est une manière cool de voir le problème en particulier quand on décide de changer l’un des deux valeurs.

Note qu’il reste à mon avis quelque chose de pas clair dans la définition de ton problème : qu’est-ce qui se passe si par hasard deux clefs ont la même valeur associée alors que tu ne voulais pas les grouper, et que tu veux changer la valeur d’une des deux ? Est-ce que la deuxième veut changer aussi ?

Ben, il n’y a aucun problème réel derrière, je me suis levé ce matin et je me suis posé cette question.

Si tu veux retrouver l’autre comportement, ajouter un union-find aux doubles dictionnaires de victor m’a l’air d’être la bonne solution (quand je change une valeur, je vérifie si elle n’est pas déjà présente ailleurs, et le cas échéant je fusionne les deux classes. La complexité globale de la mise à jour reste la même, c’est informagique.)

Ouep, on garde la même complexité et on a une solution assez flexible. Je suis quasiment sûr d’avoir un code sur mon ordi pour les Union-Find en Python. Je vais jouer un peu avec (et avec les deux comportements possibles).

+0 -0

Ben, il n’y a aucun problème réel derrière, je me suis levé ce matin et je me suis posé cette question.

Karnaj

Dans ce cas, aucun doute : tu t’es littéralement posé la question de « mais comment pourrait-on résoudre [le problème défini par union-find] » ? :D

Ouep, on garde la même complexité et on a une solution assez flexible. Je suis quasiment sûr d’avoir un code sur mon ordi pour les Union-Find en Python. Je vais jouer un peu avec (et avec les deux comportements possibles).

Attention à ne pas tomber dans un travers un peu trop répandu à mon goût dans les forums Python : la solution avec union-find est incontestablement le bon choix algorithmique, ça n’en sera pas pour autant la plus rapide en Python, pour la raison simple que c’est un langage aux performances assez particulières où il vaut souvent mieux faire quelque chose d’idiot algorithmiquement parlant pourvu que ça fasse tourner du code natif de l’interpréteur plutôt qu’une solution élégante écrite en utilisant le langage. À mon avis, et pour digresser, ça fait de Python un langage assez peu intéressant pour apprendre l’algorithmique proprement (mais la programmation, pourquoi pas, avant que les foules ne se déchaînent).

Note aussi que ce comportement de « la complexité algorithmique n’est pas suffisante pour présager des performances d’un programme » est présent dans à peu près tous les langages, notamment pour des raisons de bas niveau qui ne sont pas traitées dans les études algorithmiques usuelles, mais les concours de vitesse en Python qu’on voit parfois ici (mais aussi ailleurs) poussent en général ça à l’extrême : le but n’est pas de réfléchir à un programme efficace mais à encoder le maximum de ce qu’on veut faire dans des fonctionnalités proposées de base par l’interpréteur. Ça n’en fait pas un exercice totalement inintéressant pour autant, à condition de bien avoir en tête ce qu’on fait : un jeu avec l’interpréteur CPython, voire de l’optimisation exclusivement centrée sur l’utilisation de cet interpréteur, mais pas une réflexion sur un programme (surtout que même dans le cas de « je veux optimiser ce programme qui tourne et tournera dans mon environnement Python », la vraie bonne méthode est en général d’écrire les parties critiques en Cython ou en C).

Conclusion : jouer avec les différentes solutions, très bonne idée. Comprendre le code qu’on écrit pour voir ce qu’elles apportent, encore mieux. Comparer leurs performances réelles dans le cas concret borné d’une exécution en Python du programme, pourquoi pas (après tout, hacker avec l’interpréteur est aussi une activité ludique). Mais attention à ne pas déduire des performances de deux implémentations Python une comparaison générale des solutions proposées :-)

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte