Discussion :

[tom77380]

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

[josmiley]

cela implique t'il de remplir 3000 variables ?

ben oué ...

Code :

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

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}

[tom77380]

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

[mont29]

Code :

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

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*!

PS*: pour py2:

Code :

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

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

[josmiley]

mais c’est tellement beau, les oneliners*!

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

[mont29]

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
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 :

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

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

Dont acte…

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

[wiztricks]

Salut,

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

Code :

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

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

[mont29]

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

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
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 :

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

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*!

[PauseKawa]

Bonjour,

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 :

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

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 ?

@+

[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

[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).

[mont29]

La différence f1/f3 me surprend un peu, moi aussi… À noter, elle semble diminuer pour de très grosses listes*:

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
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 :

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

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*! ).

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 :

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

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…

[PauseKawa]

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.