Nombre d'occurence de valeurs d'un tableau en PYTHON

Le problème exposé dans ce sujet a été résolu.

Bonjour, j'ai un problème avec un exercice en python, je dois compter le nombre d'occurences pour chaque valeurs du tableau mais je n'y arrive vraiment pas. Si des personnes veulent bien m'aider/me donner des indices ça serait cool ! :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#!/usr/bin/python
#-*coding:Latin-1-*


tab=[11,12,11,9,1,5,4,6,12,12,10,6,6]
compteur=1
i=0

for i in range(len(tab)-1):
    if tab[i]==tab[i+1]:
        compteur=compteur+1
    else:
        print(tab[i], compteur)
    i=i+1

Voilà ce que j'ai essayé de faire mais évidemment ça ne marche pas, sinon j'ai une autre question, au niveau de ma boucle : si je ne met pas len(tab)-1 j 'ai une erreur : list index out of range, mais le problème avec le -1 c'est que je ne parcours pas tout le tableau /: Voilà merci d'avance pour votre aide !

+0 -0

Salut,

Pour commencer, il y a un problème avec le range de ton for. En effet, pour un range(n), les nombres vont 1 à n-1. Donc en mettant range(len(tab)-1) tu vas t'arrêter à l'avant dernière case de ton tableau. Il faut donc que tu enlèves le -1. Ok, en regardant la fin, je vois que c'est parce que tu incrémentes i, mais il se trouve que ça ne sert à rien vu que au retour au début du for, i va prendre la valeur du i de range. C'est assez étrange et à éviter.

Ex : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
for i in range(5):
    print("valeur i du range : {}".format(i))
    i += 2
    print("valeur i modifiée : {}\n".format(i))

#affiche :
#valeur i du range : 0
#valeur i modifiée : 2

#valeur i du range : 1
#valeur i modifiée : 3
#etc..

Ensuite dans ton programme tu te contentes de comparer la valeur de la case i avec la valeur de la case i+1 (avec le range corrigé, tu voudras la dernière avec la case dernière+1 d'où l'erreur, à toi de voir sachant que tu peux aussi accéder à la dernière case avec l'index -1). Donc tu ne regardes pas réellement combien d’occurrences il y a. Tu regardes juste s'il y a des doublons qui se suivent et ta valeur compteur vaut à la fin le nombre de doublons qui se suivent (3 normalement, oui parce que tu initialise compteur à 1 alors que tu devrais l'initialiser à 0 :) ).

À partir d'ici, je te donne quelques pistes, à toi de voir ce que tu veux faire. Je pense que les dictionnaires s'appliqueraient bien au problème. On peut imaginer une paire valeur du tableau (la clé) : nombre occurences (la valeur). Ensuite, il existe aussi une fonction en python pour compter les occurrences d'une valeur en particulier dans une liste (mais vu ton problème, tu dois sans doute et tu peux t'en passer).

Voilà, n'hésite pas si tu as d'autres questions ;).

+0 -0
  • En enlevant le -1 et le i=i+1 j'ai toujours l'erreur mais en y réfléchissant ça vient plutôt de mon if je pense car lorsque j'arrive à la dernière case i de mon tableau je la compare avec la case i+1 mais qui n'existe pas du coup :p .
  • Par contre j'ai vu vraiment rapidement ce que c'étaient les dico mais pour cet exercice je ne suis pas censé les avoir vu !
  • Et j'ai pas trop compris ce que tu veux dire par " On peut imaginer une paire valeur du tableau (la clé) : nombre occurrences (la valeur)."
  • Et effectivement cet exo c'est surtout pour m’entraîner à manipuler les listes :p
+0 -0

Ok,

Pour ton premier point, oui je me suis mépris le problème vient de ton tab[i]==tab[i+1]. Si i vaut la taille de ton tableau - 1 (donc l'index de la dernière case), le i + 1 sera en dehors de ton tableau. Du coup, tu peux éventuellement garder ton range initial si tu le souhaites.

Pour ton deuxième point, oui tu peux t'en passer sans problèmes.

Troisièmement, un dictionnaire c'est un ensemble de clé/valeur, donc je pensais à un truc comme. tab=[4,5,4,8,6] qui donnerait quelque chose comme { 4 : 2, 5 : 1, 8 : 1, 6 : 1}

Donc au final, tu peux aisément le faire en manipulant simplement des listes, c'est juste qu'actuellement, ton algo n'est pas bon parce que tu regardes juste si y'a des doublons qui se suivent, que ton compteur est biaisé et qu'en plus les valeurs affichées par ton else ne veulent donc rien dire. ^^

Une solution serait de parcourir la liste pour chaque valeur différente et de compter les occurrences de celle-ci. C'est pas la plus optimisée, mais ça marche.

+0 -0

Bah le problème du range initial c'est qu'il ne parcours pas tout le tableau, et pour le coup je voudrais juste utiliser des listes mais la je vois pas du tout comment je dois procéder, déjà juste traiter uniquement les valeurs différentes je vois pas :/

+0 -0

Salut,

3 solutions possibles :

  • La plus simple à coder est également la moins efficace. Pour chaque valeur du tableau, on regarde toutes les autres valeurs du tableau et on incrémente le compteur chaque fois qu'on trouve deux fois la même. On a deux boucles imbriqués et on peut montrer que ça fait en moyenne $n^2$ opérations, ce qui signifie que même pour des tableaux de seulement quelques milliers de cases ça risque de prendre du temps. Le tableau vu sert à éviter de compter deux fois les occurrences de la même valeur. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def compterStupide(tab):
    vu = [False]*len(tab)
    for i in range(len(tab)):
        if not vu[i]:
            compteur = 0
            for j in range(i, len(tab)):
                if tab[j] == tab[i]:
                    vu[j] = True
                    compteur += 1
            print(str(tab[i])+" a "+str(compteur)+" occurrences");
  • La méthode déjà évoquée avec les dictionnaires est surement la meilleur option en Python, et elle est très efficace également. Si toutefois tu ne sais pas ce qu'est un dictionnaire tu peux t'en sortir avec les listes. Pour chaque valeur du tableau, on incrémente une case dans un autre tableau qui contient le nombre d'occurrences de cette valeur. Tu peux voir ça comme un ensemble d'urnes numérotés : chaque fois que tu croises une valeur dans ton tableau tu mets une pièce dans l'urne dont le numéro est égal à cette valeur. À la fin, il te suffit de compter les pièces dans chaque urne.
    Cette solution réalise de l'ordre de $n+A$ opérations, avec $A$ la plus grande valeur du tableau. C'est donc souvent assez bon : même pour $n$ valant plusieurs dizaine de milliers ça reste rapide, à condition que $A$ ne dépasse pas quelques dizaines de milliers non plus. 
1
2
3
4
5
6
7
def compterMalin(tab):
    urnes = [0]*(max(tab)+1)
    for v in tab:
        urnes[v] += 1
    for v in range(len(urnes)):
        if urnes[v] != 0:
            print(str(v)+" a "+str(urnes[v])+" occurrences");

Attention ! Coder comme ça, ça ne fonctionne qu'avec des nombres entiers, positifs, et pas trop grands. Utiliser un dictionnaire permet de contourner cette difficulté. Un dictionnaire ça fonctionne comme une liste, sauf que les numéros des urnes peuvent être n'importe quoi : des grands entiers, des entiers négatifs, des réels, des chaînes de caractères, voir même des listes !

  • Dernière solution, pas trop mauvaise en pratique : tu tris ton tableau ! Ainsi toutes les valeurs identiques seront adjacentes. Il te suffit de compter la valeurs contigües qui sont égales. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def compterTri(tab):
    trie = sorted(tab)
    compteur = 1
    avant = None
    for v in trie:
        if v == avant:
            compteur += 1
        elif avant != None:
            print(str(avant)+" a "+str(compteur)+" occurrences")
            compteur = 1
        avant = v
    print(str(avant)+" a "+str(compteur)+" occurrences")

Cette dernière méthode fait de l'ordre de $n \ln{n}$ opérations, soit à peine quelques multiples de $n$ en pratique.

+0 -0

Pourquoi utiliser range, déjà ?

1
2
3
4
5
6
7
8
9
>>> def count(lst, val):
...     res = 0
...     for elt in lst:
...         if elt == val:
...             res += 1
...     return res
... 
>>> count([3, 4, 5, 6, 3, 4, 2, 1], 3)
2

Bon. Accessoirement il faut aussi savoir que les listes ont déjà la méthode qui va bien :

1
2
>>> [3, 4, 5, 6, 3, 4, 2, 1].count(3)
2

Je pense que les dictionnaires s'appliqueraient bien au problème. On peut imaginer une paire valeur du tableau (la clé) : nombre occurences (la valeur).

Smokiev

Mieux que ça encore :

1
2
3
>>> from collections import Counter
>>> Counter([3, 4, 5, 6, 3, 4, 2, 1])
Counter({3: 2, 4: 2, 1: 1, 2: 1, 5: 1, 6: 1})
+4 -0

Merci pour ta réponse, par contre dans ton 1 er et 2 éme code il y a une ligne de je ne comprends pas:

  • vu = [False]*len(tab) : c'est quoi [False] ? et tu multiplies ça à la longueur de ta liste ?
  • urnes = [0]*(max(tab)+1) : tu multiplies la première valeur de ta liste tab à la valeur maximale de la liste tab +1 ? Pourquoi ?
+0 -0

C'est une manière de construire les listes en Python.

Essaie dans ta ligne de commande : 

1
t = [False]*5

Alors tu verras que t est un tableau à 5 éléments valant False.
De même : 

1
t2 = [42]*1337

t2 est un tableau de taille 1337, dont chaque case contient la valeur 42.

C'est un moyen simple de fabriquer des tableaux, en choisissant leur taille et leur valeur initiale.

+0 -0

J'ai encore une question, désolé .. :s

Pourquoi utiliser str ici : print(str(avant)+" a "+str(compteur)+" occurrences") ou encore print(str(tab[i])+" a "+str(compteur)+" occurrences");

str est utilisé pour convertir ou créer des chaînes de caractère non ? Ici on en a pas vraiment besoin, si ?

+0 -0

Bah, pour afficher un nombre il faut d'abord le convertir en chaînes de caractère.
Si tu donnes un nombre à print, il le converti naturellement en chaînes de caractères.
Toutefois là je donne une chaîne de caractère à print(), en concaténant différentes chaînes plus petites. Tu as peux être dû voir que "a"+"b" renvoyait "ab", c'est ça la concaténation. Toutefois elle ne fonctionne que sur les chaînes de caractère.
Si tu écris "a"+42 Python va te renvoyer une erreur car il ne sait pas quoi faire. En revanche si tu écris "a"+str(42) alors Python va remplacer str(42) par "42" et ensuite il pourra faire "a"+"42" qui renverra bien "a42".

Ben là c'est pareil, je convertis mes nombres en chaîne de caractère avant de les concaténer à d'autres chaînes, puis d'afficher le tout.

+0 -0

Oui d'une façon générale, il faut se méfier de l'opérateur + sur les chaînes de caractères et les séquences en général.

Dès qu'il y a plus d'un + dans l'expression (foo + bar + baz), il est préférable de se rappatrier sur :

  • La méthode str.join pour tout concaténer d'un coup sans allouer/remplir/désallouer des chaînes temporaires :

    1
    ''.join((foo, bar, baz))

  • une format string :

    1
    "{} a {} occurrences".format(avant, compteur)

  • le mécanisme de formattage de la fonction print ou du logger : 

    1
    print(foo, bar, baz)

    ou

    1
    logger.info("%s a %d occurrences", avant, compteur)

+2 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte