Compter éléments identiques d'une liste

Version imprimable

08/04/2010, 21h23
pioupiou67290

Compter éléments identiques d'une liste

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
08/04/2010, 21h51
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:

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.

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:

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.

09/04/2010, 00h09
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:

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 ;)
09/04/2010, 00h30
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:

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.

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:

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

allez, une variante encore simple qui fait intervenir mon dico adoré....

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
a=[1,1,4,5,2,8,5,4,5,2,1,4,5,2,3,6,5,8,9]
b={}#dico
for i in a:
    b[str(i)]=b.setdefault(str(i),0)+1 # boucle sur la liste et injection dans le dico de l'iteration comme clé si elle n'existe pas.
#puis attribution de sa valeur (compteur).
 
c=b.items()#recupération de la liste des items du dico
v=[]#liste pour conserver les items les plus fréquent de a
w=0#valeur du compteur
for e in c:#boucle sur c pour recherche des items ayant la valeur de compteur la plus grande
    if e[1]>w:#
        w=e[1]
        v=[e[0]]
    elif e[1]==w:
        v.append(e[0])
 
print v

Citation:

>> ['5']

le retour est une liste des éléments se répétant le plus souvent dans la liste initiale.
ca mériterait une petite comparaison de temps d'éexécution tout ca!

Code:

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
from time import clock
 
a = [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]
 
 
b={}
te = clock()
for i in a:
    b[str(i)]=b.setdefault(str(i),0)+1
 
c=b.items()
v=[]
w=0
for e in c:
    if e[1]>w:
        w=e[1]
        v=[e[0]]
    elif e[1]==w:
        v.append(e[0])
 
tf = clock()
print tf-te
 
print v
print w

Citation:

0.00109601498797
['5']
149

8-)

Salut !

J'y vais de ma petite réponse, qui est une adaptation de la fonction unique_everseen, décrite ici.
Code:

1 2 3 4 5 6 7 8 from itertools import ifilterfalse def plusfrequent(sequence): seen = {} for elt in ifilterfalse(seen.__contains__, sequence): seen[elt] = sequence.count(elt) return max((v, k) for k, v in seen.iteritems())[1]
Spéciale dédicace à eyquem : le ifilterfalse combiné avec la méthode __contains__ ici permet de n'appliquer la méthode count qu'une seule fois par élément, quelque soit sa fréquence d'apparition dans la liste (l'ajout d'un print elt dans la boucle convaincra les plus sceptiques (dont j'ai fait partie)).

Je rejoins airod : il faudrait vraiment avoir une comparaison des perfs de chaque solution proposée.

09/04/2010, 10h41
josmiley

alors comme ça on chipote ^^
bon:

Code:

x=sorted(set(l),key=l.count)[-1]

cette seule ligne; quand même plus lisible pour ce que ça doit faire; est un peu plus rapide que le code de dividee.
le 1er code que j'ai posté c'etait juste pour mettre pioupiou67290 sur la voie.
si ce que veut fairepioupiou67290 est seulement ce tri alors pourquoi pas optimiser à fond;
sinon, s'il faut intégrer plusieurs lignes, voire des def juste pour ça dans un code plus grand, ça va faire brouillon je pense.

s'il faut faire des appels:

Code:

monmax = lambda l:sorted(set(l),key=l.count)[-1]

non ?
09/04/2010, 12h23
pioupiou67290

Merci a tout le monde pour vos réponses!
Par contre je ne suis vraiment pas très avancé en python et il y a donc des fonctions qui me sont complètement inconnues...
Je vais reprendre toutes vos propositions une par une et essayer de bien tout comprendre.
Mais en tout cas merci beaucoup ;)
09/04/2010, 13h31
dividee

Citation:

Envoyé par josmiley

alors comme ça on chipote ^^
bon:

Code:

x=sorted(set(l),key=l.count)[-1]

cette seule ligne; quand même plus lisible pour ce que ça doit faire; est un peu plus rapide que le code de dividee.

Effectivement c'est toujours aussi élégant et beaucoup plus rapide ! Bien vu.
On peut encore l'améliorer:

Code:

x=max(set(l),key=l.count)

Mais mon premier code avec defautldict reste entre 2 et 3 fois plus rapide dans mes tests. Je ne sais pas vraiment pourquoi.
09/04/2010, 14h07
josmiley

Citation:

Code:

x=max(set(l),key=l.count)

zut!!! j'allai le poster mais j'etais au boulot ... :(

Puisqu'on en est au fignolage, je fais un petit toilettage de ma solution:
Code:

1 2 3 4 5 from collections import defaultdict d = defaultdict(int) for e in l: d[e] += 1 x = max(d,key=d.__getitem__)

10/04/2010, 16h45
dividee
Je viens de voir qu'une nouvelle classe collections.Counter a été ajoutée en Python 3.1.
Dans cette version de Python, on peut donc écrire:
Code:

1 2 from collections import Counter x = Counter(l).most_common(1)[0][0]
Counter hérite de dict, mais pas de defaultdict. Etant une fonction de librairie, il fallait faire bien attention à la sémantique et aux cas limites, et ils ont préféré lever une KeyError lors de l'accès à une clé inexistante plutôt que retourner 0, comme ça aurait été le cas avec un defaultdict.