Discussion :

[stephbb75]

Bonjour,

Je cherche a trouver Les plus grands élément dans un dict.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
val = {'a': 4, 'b': 1, 'c': 4, 'd' : 3  }
maxi = max(val, key=val.get)
print(maxi)

Ce code me donne bien 'a', mai je voudrais avoir comme résultat {'a', 'c'}
J'ai tenté avec plusieurs truc mais pas trouvé (et s'astrouve c'est tout con ;-) ).

Merci
Steph

[wiztricks]

Salut,

max retourne une seule valeur... et s'il y en a plusieurs, il faut écrire une boucle qui construise la liste de...

- W

[Sve@r]

Salut

Ce code me donne bien 'a', mai je voudrais avoir comme résultat {'a', 'c'}
J'ai tenté avec plusieurs truc mais pas trouvé (et s'astrouve c'est tout con ;-) ).

Ouais, s'astrouve... set(x[0] for x in val.items() if x[1] == max(val.values())).

[fred1599]

Salut

Ouais, s'astrouve... set(x[0] for x in val.items() if x[1] == max(val.values())).

Mais algorithmiquement je pense qu'il y a mieux, mais c'est plus long.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
def get_max(val):    
    keys = list(val.keys())
    maxi = val[keys[0]]
    results = [keys[0]]
    for key in keys[1:]:
        value = val[key]
        if value > maxi:
            results = [key]
        elif value == maxi:
            results.append(key)
    return results

Je dois bien gagner une boucle de trop (je pense à max(val.values()))

[Sve@r]

Mais algorithmiquement je pense qu'il y a mieux, mais c'est plus long.Je dois bien gagner une boucle de trop (je pense à max(val.values()))

Sais pas trop. Effectivement le max() effectue un premier balayage dans tout le tableau, balayage que j'effectue ensuite une seconde fois dans la comprehension mais c'est juste un "double balayage" et non pas un "balayage dans le balayage" donc on ne tombe pas dans le N² (enfin j'espère que le max() n'est pas effectué à chaque comparaison ).
De ton côté tu multiplies les accès crochets qui ne sont pas gratuits et surtout tu as un append() qui est généralement perçu comme gros consommateur de ressources.
Peut-être un bench dirait lequel des deux mais j'ai un peu la flemme ce soir.

[edit]Ah ben si, j'ai écrit ceci

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def xxx(val):
	print("xxx")
	return max(val.values())
print(set(x[0] for x in val.items() if x[1] == xxx(val)))

Et j'ai eu la douleur de voir apparaitre "xxx" 4 fois

[fred1599]

Oui tu te doutes bien que j'avais déjà fais le test et de comprendre pourquoi ça allait deux fois moins vite

Disons qu'un des avantages de ton code c'est la partie optimisation de la fonction max, mais elle ne suffit pas à combler cette boucle supplémentaire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from timeit import timeit
 
def get_max(val):
    keys = list(val.keys())
    maxi = val[keys[0]]
    results = [keys[0]]
    for key in keys[1:]:
        value = val[key]
        if value > maxi:
            results = [key]
        elif value == maxi:
            results.append(key)
    return results
 
 
def get_max_sveor(val):
    return set(x[0] for x in val.items() if x[1] == max(val.values()))
 
 
val = {'a': 4, 'b': 1, 'c': 4, 'd': 3}
print(timeit("get_max(val)", setup="from __main__ import get_max, val"))
print(timeit("get_max_sveor(val)", setup="from __main__ import get_max_sveor, val"))

Ce qui donne chez moi,

0.49668644499615766
1.1246752470033243

[Sve@r]

Disons qu'un des avantages de ton code c'est la partie optimisation de la fonction max, mais elle ne suffit pas à combler cette boucle supplémentaire.

Pour supprimer le N², j'ai tenté...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
def get_max_sveor(val):
	m=max(val.values())
	return set(x[0] for x in val.items() if x[1] == m)

... et je passe de 0.8144763539312407 à 0.78484934696462 (mais tu restes gagnant). Ceci dit, si on remplace ton list() de la ligne 2 par un tuple(), on passe de (chez-moi) 0.5988283799961209 à 0.5485420490149409 (il n'y a pas de petites économies )

[fred1599]

Hello,

Beaucoup mieux en effet, mais pourquoi le set et pourquoi pas le remplacer par une list comprehension ?

EDIT: Par contre de mon côté j'ai un petit oubli, qui n'a pas d'impact, mais qui rendait faux l'exercice,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
def get_max(val):    
    keys = tuple(val.keys())
    maxi = val[keys[0]]
    results = [keys[0]]
    for key in keys[1:]:
        value = val[key]
        if value > maxi:
            results = [key]
            maxi = value  # l'oubli
        elif value == maxi:
            results.append(key)
    return results

[lg_53]

Il faudrait benchmarké sur plusieurs jeux de données, car je ne suis pas convaincu que la solution de fred soit toujours plus rapide. Car il construit quand même à chaque fois la liste de la valeur courante du max, alors qu'on pourrait n'en construire qu'une seule !

Faudrait tester :
1) sur un dictionnaire plus grand
2) sur un dictionnaire déjà trié (avec les valeurs les plus grandes à la fin), et avec plein de valeurs qui se répète du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

{ ('x%05d'%i) : i//1000 for i in range(100000) }

Je vous laisse faire le test.

[fred1599]

Car il construit quand même à chaque fois la liste de la valeur courante du max, alors qu'on pourrait n'en construire qu'une seule !

Sans calculer la valeur max au préalable je vois pas trop comment, mais effectivement, ça va bien plus vite sur des données de plus grandes tailles (2x environ)

Donc en conclusion l'important ici est de connaître la taille de la donnée pour choisir la meilleure solution.

[lg_53]

Sans calculer la valeur max au préalable je vois pas trop comment

Si si, en faisant une première passe pour calculer la valeur max d'abord, on est d'accord
Et une seconde pour trouver la liste des argmax. Mais là on ne construira que cette liste, et pas plein de liste d'argmax de morceau du dictionnaire initial.

[Sve@r]

mais pourquoi le set

Parce que le PO a écrit qu'il voulait {'a', 'c'} ce qui est la symbolique d'un set

et pourquoi pas le remplacer par une list comprehension ?

Perso je considères le terme "list comprehension" comme un terme générique signifiant "construction d'ensemble" et charge au concepteur de choisir l'ensemble qui lui convient. Celui qui voudra un tuple écrira xxx=tuple(...), celui qui voudra un ensemble écrira xxx=set(...), celui qui voudra un dictionnaire écrira xxx=dict(...) et celui qui une liste écrira xxx=list(...) (avec dans ce cas précis un raccourci syntaxique possible avec xxx=[...] mais que perso je n'aime pas utiliser) ; ces 4 cas (tuple en intension, ensemble en intension, dictionnaire en intension, liste en intension) étant tous regroupés sous une même notion commune "comprehension list".

Il faudrait benchmarké sur plusieurs jeux de données, car je ne suis pas convaincu que la solution de fred soit toujours plus rapide. Car il construit quand même à chaque fois la liste de la valeur courante du max, alors qu'on pourrait n'en construire qu'une seule !

J'ai tenté cette méthode sur la solution de fred1599 mais de simplifications en simplifications on retombe sur mon code de comprehension list.

Faudrait tester :
1) sur un dictionnaire plus grand
2) sur un dictionnaire déjà trié (avec les valeurs les plus grandes à la fin), et avec plein de valeurs qui se répète du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

{ ('x%05d'%i) : i//1000 for i in range(100000) }

Je vous laisse faire le test.

Je l'ai fait et retournement de situation !!! Voici les résultats
12617.72787903808
5425.207766342908

pourtant je l'ai fait en pensant honnêtement que la solution de fred1599 serait plus rapide