Discussion :

[pioupiou67290]

Bonjour,
Mon problème est assez simple mais je ne vois pas du tout comment m'en sortir avec python...
alors j'ai une liste, disons [a,a,b,c,b,a,e] et je voudrais que python me sorte l'élément qui apparait le plus souvent; ici a.
Merci d'avance

[josmiley]

y a une fonction, ça tiend en une ligne mais j'arrive pas a m'en rapeler ...
je crois que ça concernait sorted() ou max().
désolé.
______________________________________________
ça me revient !!!

Code :

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

1
2
3
>>>l = ['a', 'a', 'b', 'c', 'b', 'a', 'e']
>>>sorted(l,key=l.count)
['c', 'e', 'b', 'b', 'a', 'a', 'a']

avec ça tu devrais y arriver.

[eyquem]

sorted(l,key=l.count) est peu rapide:
pour chaque élément de la liste examiné, sorted() calcule d’abord son nombre d’apparition dans la liste, puis il le classe en fonction de ce nombre.

Pour un élément répété 50 fois dans la liste, sorted() va répéter 49 fois la détermination de son count déjà établi.

Cette méthode n’est donc adaptée que si le temps d’exécution ne compte pas, ou si la liste est peu longue.
Plus la liste sera longue , plus le travail sera énorme.




Pour une liste longue, je propose une autre méthode, basée sur le fait que la fonction sort() est extrêmement rapide, mais avec un peu d'algorihme autour

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from time import clock
 
li = [3,6,7,4,5,3,1,3,7,5,6,3,4,5,2,5,4,6,5,4,3,4,5,3,4,2,3,5,6,7,5,4,8,5,6,5,7,
      2,4,3,1,2,5,3,2,6,4,5,3,4,5,5,5,4,3,4,5,2,2,5,6,7,4,4,6,5,2,3,4,7,5,6,4,3,
      5,6,7,6,5,6,4,5,7,8,9,8,7,4,3,4,5,6,2,3,4,1,3,2,4,1,4,5,3,4,1,3,2,7,6,7,5,
      3,2,5,4,3,5,4,3,2,3,4,1,2,3,2,4,5,3,4,5,6,5,3,4,5,2,3,4,6,2,4,9,3,7,9,7,3,
      3,6,7,4,5,3,1,3,7,5,6,3,4,5,2,5,4,6,5,4,3,4,5,3,4,2,3,5,6,7,5,4,8,5,6,5,7,
      2,4,3,1,2,5,3,2,6,4,5,3,4,5,5,5,4,3,4,5,2,2,5,6,7,4,4,6,5,2,3,4,7,5,6,4,3,
      5,6,7,6,5,6,4,5,7,8,9,8,7,4,3,4,5,6,2,3,4,1,3,2,4,1,4,5,3,4,1,3,2,7,6,7,5,
      3,2,5,4,3,5,4,3,2,3,4,1,2,3,2,4,5,3,4,5,6,5,3,4,5,2,3,4,6,2,4,9,3,7,9,7,3,
      3,6,7,4,5,3,1,3,7,5,6,3,4,5,2,5,4,6,5,4,3,4,5,3,4,2,3,5,6,7,5,4,8,5,6,5,7,
      2,4,3,1,2,5,3,2,6,4,5,3,4,5,5,5,4,3,4,5,2,2,5,6,7,4,4,6,5,2,3,4,7,5,6,4,3,
      5,6,7,6,5,6,4,5,7,8,9,8,7,4,3,4,5,6,2,3,4,1,3,2,4,1,4,5,3,4,1,3,2,7,6,7,5,
      3,2,5,4,3,5,4,3,2,3,4,1,2,3,2,4,5,3,4,5,6,5,3,4,5,2,3,4,6,2,4,9,3,7,9,7,3,
      3,6,7,4,5,3,1,3,7,5,6,3,4,5,2,5,4,6,5,4,3,4,5,3,4,2,3,5,6,7,5,4,8,5,6,5,7,
      2,4,3,1,2,5,3,2,6,4,5,3,4,5,5,5,4,3,4,5,2,2,5,6,7,4,4,6,5,2,3,4,7,5,6,4,3,
      5,6,7,6,5,6,4,5,7,8,9,8,7,4,3,4,5,6,2,3,4,1,3,2,4,1,4,5,3,4,1,3,2,7,6,7,5,
      3,2,5,4,3,5,4,3,2,3,4,1,2,3,2,4,5,3,4,5,6,5,3,4,5,2,3,4,6,2,4,9,3,7,9,7,3,
      3,6,7,4,5,3,1,3,7,5,6,3,4,5,2,5,4,6,5,4,3,4,5,3,4,2,3,5,6,7,5,4,8,5,6,5,7,
      2,4,3,1,2,5,3,2,6,4,5,3,4,5,5,5,4,3,4,5,2,2,5,6,7,4,4,6,5,2,3,4,7,5,6,4,3,
      5,6,7,6,5,6,4,5,7,8,9,8,7,4,3,4,5,6,2,3,4,1,3,2,4,1,4,5,3,4,1,3,2,7,6,7,5]
print li
print
 
aff = 0
te = clock()
li.sort()
w = []
x,cntmax,cnt = li[0],0,0
if aff: print 'cntmax =',cntmax
for y in li:
    if aff: print '\ncnt('+str(x)+') = '+str(cnt)+'\ny =',y
    if y==x:
        cnt += 1
    elif cnt==cntmax:
        if aff: print 'cntmax = cnt = '+str(cntmax)
        w.append(x)
        x = y
        cnt = 1
    elif cnt>cntmax:
        if aff: print 'cnt = '+str(cnt)+' > cntmax = '+str(cntmax)
        w = [x]
        cntmax = cnt
        x = y
        cnt = 1
    else:
        cnt = 1
    if aff: print 'cnt post = '+str(cnt)+'   w = '+repr(w)+'\ncntmax post = '+str(cntmax)
if cnt==cntmax:
    w.append(x)
elif cnt>cntmax:
    w = [x]
tf = clock()
print tf-te
print w
print
for d in set(li):
    print d,': ',li.count(d),'fois'
 
 
print '\n'
te = clock()
x = sorted(li,key=li.count)
tf = clock()
print tf-te
print x[-1:]

--> Mettre aff à1 pour afficher le suivi de l'exécution



La méthode avec sorted() est dans un ratio par rapport à la méthode que je propose supérieur à 1, qui croît avec la longueur de la liste

Pour la liste
li = [3,2,5,4,3,5,4,3,2,3,4,1,2,3,2,4,5,3,4,5,6,5,3,4,5,2,3,4,6,2,4,9,3,7,9,7,3]
ce ratio est de 2,2

Pour la liste dans le code ci dessus, ce ratio est de 29.


Nota: mon code donne plusieurs éléments de la liste comme solution s’ils ont tous la même fréquence la plus élevée.

[dividee]

La méthode de josmiley est extrêmement lente sur de grandes listes, mais la tienne est un peu complexe à mon goût eyquem ; on peut faire plus rapide et plus court:

Code :

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

1
2
3
4
5
6
7
from collections import defaultdict
from operator import itemgetter
 
l = [...]
d = defaultdict(int)
for e in l: d[e] += 1
x = max(d.items(),key=itemgetter(1))[0]

On est presque toujours gagnant en utilisant les fonctions standard, mais il ne faut pas en abuser comme josmiley

[miawaw]

Bonsoir,

J'ai aussi une idée utilisant les fonctions standard.
Elle utilise deux fois la fonctions sort mais c'est pas trop grave je crois:

Code :

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

1
2
3
4
def trie(a):
    C = [(x, len(list(g))) for x, g in groupby(sorted(a))]
    C.sort(key=lambda x: x[1])
    return sum([[x]*k  for x, k in C], [])

EDIT
La fonction groupby est définie dans le module itertools.

EDIT 2
oups, j'ai mal compris. Mon algo trie le vecteur...


Sinon j'aime bien la proposition de dividee.

[tyrtamos]

Bonjour,

Autre solution.

Son avantage est qu'elle n'exécute le 'count' qu'une seule fois pour chaque élément distinct, grâce au sort() qui a permis de placer les éléments identiques ensemble.

S'il y a plusieurs éléments qui ont la fréquence maxi, seul le 1er est donné. On pourrait adapter le code pour donner la liste de tels éléments si c'était demandé.

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
def leplusfrequent(L):
    """Retourne l'élément le plus fréquent de la liste"""
    L.sort()  # pour que les éléments identiques soient assemblés
    n0, e0 = 0, None  # pour conserver le plus fréquent
    ep = None  # stocke l'élément distinct de la boucle précédente
    for e in L:
        if e != ep:  # si l'élément e a déjà été rencontré, on ne fait rien
            n = L.count(e)
            if n > n0:
                n0, e0 = n, e  # on stocke le nouvel élément le plus fréquent
            ep = e  # on stocke l'élément courant pour la boucle suivante
    return e0, n0
 
e, n = leplusfrequent(['a', 'a', 'b', 'c', 'b', 'a', 'e', 'c', 'c', 'c', 'c'])
print e, n
e, 5

Tyrtamos