compter le nombre de toutes les occurences d'une liste

Version imprimable

14/12/2011, 23h19
tom77380

compter le nombre de toutes les occurences d'une liste

Bonjour,

je dipose d'une liste contenant des milliers de valeurs, j'aimerai pouvoir déterminer le nombre d'occurences de chacunes des valeurs. Je sais compter combien de fois un nombre apparait (grâce à la méthode count), mais ici, j'aimerai récupérer le nombre d'occurence d'environ 3000 chiffres (cela implique t'il de remplir 3000 variables ?). Je ne vois pas a marche à suivre, si vous avez une piste je suis preneur :)

Citation:

Envoyé par tom77380

cela implique t'il de remplir 3000 variables ?

ben oué ...

Code:

1
2
3
4
5
6
7
8
>>> liste = [2,65,42,53,27,2,42,27,2,53,53,53,65,21,27,53,2,53,65,27]
>>>
>>> compte = {}.fromkeys(set(liste),0)
>>> for valeur in liste:
...     compte[valeur] += 1
... 
>>> print(compte)
{53: 6, 65: 3, 2: 4, 27: 4, 42: 2, 21: 1}

15/12/2011, 00h48
tom77380

Je n'avais pas pensé aux dictionnaires, merci pour votre solution :)

Code:

1 2 3 4 5 >>> liste = [2,65,42,53,27,2,42,27,2,53,53,53,65,21,27,53,2,53,65,27] >>> >>> compte = {k: liste.count(k) for k in set(list)} >>> print(compte) {53: 6, 65: 3, 2: 4, 27: 4, 42: 2, 21: 1}
Non*? D’accord, c’est du py3… mais c’est tellement beau, les oneliners*! 8-)

PS*: pour py2:

Code:

compte = dict([(k, liste.count(k)) for k in set(liste)])

:D

15/12/2011, 01h09
josmiley

Citation:

mais c’est tellement beau, les oneliners*!

seulement si c'est efficace ... et je doute que count le soit.

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
import random, time
 
def f1(liste):
    compte = {}.fromkeys(set(liste),0)
    for valeur in liste:
        compte[valeur] += 1
    return compte
 
def f2(liste):
    compte = {k: liste.count(k) for k in set(liste)}
    return compte
 
num = 30000
start = 0
end = 3000
mul = int(num/(end-start) * 10)
liste = random.sample(tuple(range(start, end))*mul, num)
 
print("{} values, {} elements.".format(end-start, num))
ts = time.time()
f1(liste)
print("f1: {} sec".format(time.time()-ts))
 
ts = time.time()
f2(liste)
print("f2: {} sec".format(time.time()-ts))

Code:

1
2
3
3000 values, 30000 elements.
f1: 0.005090951919555664 sec
f2: 2.5202560424804688 sec

Dont acte… :mouarf: :mouarf: :mouarf: :aie:

(Et les choses ne doivent pas aller en s’améliorant quand la liste prend du poids…)

Salut,

Juste pour vous signaler une "feature", 2.7/3.1:
Code:

1 2 3 4 5 >>> from collections import Counter >>> liste = [2,65,42,53,27,2,42,27,2,53,53,53,65,21,27,53,2,53,65,27] >>> c = Counter(liste) >>> c Counter({53: 6, 2: 4, 27: 4, 65: 3, 42: 2, 21: 1})
- W
PS: les "dict comprehension" sont aussi en 2.7

Ah, merci, je ne connaissais pas… Du coup*:

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
import random, time, collections
 
def f1(liste):
    compte = {}.fromkeys(set(liste),0)
    for valeur in liste:
        compte[valeur] += 1
    return compte
 
def f2(liste):
    compte = {k: liste.count(k) for k in set(liste)}
    return compte
 
def f3(liste):
    compte = collections.Counter(liste)
    return compte
 
num = 30000
start = 0
end = 3000
mul = int(num/(end-start) * 10)
liste = random.sample(tuple(range(start, end))*mul, num)
 
print("{} values, {} elements.".format(end-start, num))
 
ts = time.time()
f1(liste)
print("f1: {} sec".format(time.time()-ts))
 
ts = time.time()
f2(liste)
print("f2: {} sec".format(time.time()-ts))
 
ts = time.time()
f3(liste)
print("f3: {} sec".format(time.time()-ts))

Code:

1
2
3
4
3000 values, 30000 elements.
f1: 0.0061109066009521484 sec
f2: 2.5340070724487305 sec
f3: 0.016598939895629883 sec

La solution de josmiley reste plus de deux fois plus performante*! 8O

17/12/2011, 09h11
PauseKawa
Bonjour,

Citation:

Envoyé par josmiley

seulement si c'est efficace ... et je doute que count le soit.

C'est évident, mais pourquoi ? Cela ne viens sans doute pas de la closure car l'alien
Code:

1 2 list(map(lambda k: (k in compte or compte.__setitem__(k, 1)) and compte.__setitem__(k, compte[k]+1), lst))
En fait une et reste plus performant.
Cela viens donc sans doute de .count()

En explication ?

@+
17/12/2011, 09h26
fred1599

@mont29, salut

Je suis surpris par la vitesse de f1 par rapport à f3 qui est censé être une fonction (je parle de f3) optimale et spécialisée pour faire cela.

Comme je suis une tare en algo, je veux bien qu'on m'explique le pourquoi du comment.

Même si c'est pas énorme, on est bien d'accord :)
17/12/2011, 09h51
PauseKawa

Cela viens sans doute du fait que f1 est un simple loop alors que Counter appelle une fonction.
'Optimiser' au sens code cela implique des tests (if).

La différence f1/f3 me surprend un peu, moi aussi… À noter, elle semble diminuer pour de très grosses listes*:
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 import random, time, collections def f1(liste): compte = {}.fromkeys(set(liste),0) for valeur in liste: compte[valeur] += 1 return compte def f2(liste): compte = {k: liste.count(k) for k in set(liste)} return compte def f3(liste): compte = collections.Counter(liste) return compte def f4(liste): compte = {} tuple(map(lambda k: (k in compte or compte.__setitem__(k, 1)) and compte.__setitem__(k, compte[k]+1), liste)) return compte num = 10000000 start = 0 end = 1000000 mul = int(num/(end-start) * 10) liste = random.sample(tuple(range(start, end))*mul, num) print("{} values, {} elements.".format(end-start, num)) ts = time.time() f1(liste) print("f1: {} sec".format(time.time()-ts)) #ts = time.time() #f2(liste) # print("f2: {} sec".format(time.time()-ts)) ts = time.time() f3(liste) print("f3: {} sec".format(time.time()-ts)) ts = time.time() f4(liste) print("f4: {} sec".format(time.time()-ts))
Code:

1 2 3 4 1000000 values, 10000000 elements. f1: 4.12390398979187 sec f3: 6.297826051712036 sec f4: 6.9556519985198975 sec
L’ET de PauseKawa est donc presque aussi performant que le Counter (je me suis fait grâce de f2 ici*! :mouarf: ).

Pour ce qui est de f2, je suis à peu près persuadé que count() se contente de parcourir toute la liste à chaque fois, alors que toutes les autres solutions ne la parcourent qu’une seule fois, d’où un temps d’exécution proportionnel au carré du nombre de valeurs dans la liste (plus un gros overhead lors de la création du set, probablement).

Pour finir, avec un petit nombre de valeurs et un très grands nombre d’éléments*:
Code:

1 2 3 4 5 100 values, 10000000 elements. f1: 1.8053059577941895 sec f2: 26.246901988983154 sec f3: 4.434233903884888 sec f4: 5.044877052307129 sec
f1 semble définitivement être la solution la plus performante…

17/12/2011, 12h18
PauseKawa

Citation:

Envoyé par mont29

Pour ce qui est de f2, je suis à peu près persuadé que count() se contente de parcourir toute la liste à chaque fois, alors que toutes les autres solutions ne la parcourent qu’une seule fois

Idem: J'ai bien l'impression que cela reprend la lecture de l'objet du début (jusqu'au 'match' suivant). Ce serait bien d'avoir confirmation.