Bonjour je suis bloqué sur une question je crois très simple, mais comme je débute en python, je n'arrive pas à la résoudre...

J'ai un dictionnaire "dico", et, sachant une valeur du dico je voudrais récupérer la clé:

cle_avec_valeur_12= []
valeur = 12
for i in dico.values():
   if (i == valeur):
      cle_avec_valeur_12.append(<gras>????</gras>)

Voila j'aimerais récuperer les clés qui ont pour valeurs 12 dans le dico,

Merci de votre aide

Simplement en utilisant la méthode dict.items().

keys, value = [], 12

for k, v in dict.items():
    if v == value:
        keys.append(k)

# ou en une ligne :
keys = [ k  for k, v in dict.items()  if v == value ]

Nickel

Merci PsycoPy

keys = [ k  for k in dico.keys()  if dico[k] == value ]

La solution de PsycoPy est plus efficace : elle a le mérite d'être linéaire, alors que le lookup dico[k] à l'intérieur de la list comprehension fait la même chose en O(n²).

J'y comprendrais jamais rien avec ces complexités

Ben c'est pas spécialement compliqué :

Imagine que ton dictionnaire contienne <math>\(n\)</math> éléments. Pour rechercher un élément dedans, (en faisant dico[cle]) ça te prend au pire <math>\(n\)</math> opérations — comparaisons —. Donc l'opération dico[cle] est en <math>\(O(n)\)</math>.

Maintenant, si tu fais cette opération pour chaque élément du dictionnaire (comme dans ta list comprehension), alors tu fais <math>\(n\)</math> fois une opération en <math>\(O(n)\)</math>, donc l'opération globale est en <math>\(O(n \times n) = O(n^2)\)</math>.

Dans l'autre cas, avec la méthode items, tu ne parcours qu'une seule fois le dictionnaire en entier, et tu construis le résultat au fur et à mesure que tu le parcours, donc sur un dictionnaire de taille <math>\(n\)</math>, ça te prend <math>\(n\)</math> opérations en tout (il n'y a qu'une seule comparaison de faite pour chaque élément du dictionnaire), d'où une complexité en <math>\(O(n)\)</math>, linéaire.

Je pense effectivement que la méthode items() est plus efficace ici, mais je ne suis pas sur que l'opérateur d'indexation des dictionnaires (dict[key]) exécute n opérations maxi. N'y a-t-il pas une histoire de hashage quelque-part ?

Citation : PsycoPy

Je pense effectivement que la méthode items() est plus efficace ici, mais je ne suis pas sur que l'opérateur d'indexation des dictionnaires (dict[key]) exécute n opérations maxi. N'y a-t-il pas une histoire de hashage quelque-part ?

Tu peux vérifier ici, dans le pire cas, la complexité est bien O(n).

Ok, merci pour le lien. C'est très instructif.
Je ne sais pas pourquoi j'imaginais que le hashage aurait un impact sur les algorithmes de type getter... Encore une fausse idée pour me rappeller qu'un jour il faudra que je lise les sources de CPython pour me cultiver un peu.

Enfin dans le cas moyen c'est quand même O(1) hein.

C'est juste qu'on ne peut pas compter dessus.

Ah oui, le cas moyen. L'algorithme n'est donc pas un simple parcourt d'une quelconque liste de clés.

Citation

Tu peux vérifier ici, dans le pire cas, la complexité est bien O(n).

Merci pour le lien, je ne connaissais pas.

Va falloir quand même que je m'y mette sérieusement, mais il est vrai que je n'en n'avais jamais vraiment l'utilité.

En tout cas merci