Discussion :

[ilaomxp]

Merci beaucoup

[Beginner.]

Ce qui s'écrit basiquement:

Code :

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

1
2
3
for i in range(len(L)):
    n = L[i]
    R[n] = R[n]+1

reste à initialiser R avec "suffisamment" de 0.
"suffisament" est le plus grand nombre M contenu dans L... plus 1.
Donc R = [0] * (M+1).

Effectivement c'est bien mieux comme ça... C'est une autre manière de faire...

J'ai quand même voulu coder la manière expliquée par Sve@r (c'est-à-dire en utilisant une fonction qui compte combien de fois le nombre "n" se trouve dans une liste).

Code python :

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

1
2
3
4
5
def f1(lst):   
    res = [0] * (max(lst) + 1)
    for i in lst:
        res[i] = lst.count(i)
    return res

C'est moins performant (dans certains cas on fait plusieurs fois le même calcul)...

[wiztricks]

C'est moins performant (dans certains cas on fait plusieurs fois le même calcul)...

Il faudrait mémoriser dans un set les nombres déjà comptés.

Ceci dit si le max est grand et que la liste est petite, on se retrouve avec un R plein de zéros. C'est pour çà qu'on va préférer utiliser un dictionnaire (pour ne compter que les nombres présents).

Ce problème de comptage d’occurrences est tellement récurent que Python à collections.Counter.

- W

[Beginner.]

Ceci dit si le max est grand et que la liste est petite, on se retrouve avec un R plein de zéros. C'est pour çà qu'on va préférer utiliser un dictionnaire (pour ne compter que les nombres présents).

Oui justement c'est pour cela que j'avais dit (#5) que je trouvais cet exo bizarre... J'avais donné l'exemple d'une liste d'entiers naturels où il y a un grand nombre genre : [1,3, 6999999] il faudra renvoyé une liste de 7 millions d'éléments : [0,1,0,1,0,0,0,0,... ...,1]...

Ce problème de comptage d’occurrences est tellement récurent que Python à collections.Counter.

Merci. Je vais regarder ça...

Il faudrait mémoriser dans un set les nombres déjà comptés

Oui. Il y a un autre problème je suppose que la fonction count parcours à chaque fois toute la liste alors que dans le code que tu as proposé la liste n'est parcourue qu'une fois...

[Sve@r]

Oui. Il y a un autre problème je suppose que la fonction count parcours à chaque fois toute la liste alors que dans le code que tu as proposé la liste n'est parcourue qu'une fois...

Exact. C'est ce qu'on nomme une complexité en O(N²) parce qu'on considère qu''une liste de N éléments sera parcourue N fois. Et ça fait partie évidemment des complexités à essayer d'éviter.
Toutefois j'aimais bien cette approche car ça lui apprenait à découper un problème complexe en petits problèmes simples. Enfin il apprendra plus tard (ou pas).

[wiztricks]

Toutefois j'aimais bien cette approche car ça lui apprenait à découper un problème complexe en petits problèmes simples. Enfin il apprendra plus tard (ou pas).

Certes mais çà demande de faire une double boucle (ou de masquer la boucle interne par un appel de fonction). Et c'est loin d'être intuitif, car on ne balaie pas un tableau...

Bien sûr ce sont des constructions qu'il faut maîtriser parce qu'on n'a pas toujours le choix mais elles sont difficiles à piger lorsqu'on piétine déjà avec une boucle simple.

- W

[Beginner.]

Merci.