Tableaux unidimensionnels et fichiers texte

Résumé en cinq points

1Le tableau unidimensionnel en Python

1.1Listes et indices

Pour une liste t de longueur $n$, obtenue par len(t), les indices valides vont de $0$ à $n - 1$. L'annexe ne rend exigible que l'accès par indice positif valide, sans indice négatif.

masses = [23.1, 25.4, 22.8, 26.0, 24.3]   # masses en grammes
len(masses)      # 5
masses[0]        # 23.1, premier élément
masses[4]        # 24.3, dernier élément, indice len(masses) - 1
masses[2] = 22.9 # modification d'un élément

1.2Créer une liste

Trois façons, toutes dans l'annexe :

• par append successifs, à partir de la liste vide : t = [] puis t.append(x) ajoute x à la fin ;
• par compréhension, [e for x in s] : par exemple [x * 1000 for x in masses] convertit les masses de grammes en milligrammes ;
• par répétition, [0] * n donne une liste de $n$ zéros, utile pour préparer des compteurs.

1.3Parcourir une liste

Deux types de boucles, à choisir selon le besoin.

for x in t:                 # parcours des valeurs
    ...
for i in range(len(t)):     # parcours des indices, t[i] est la valeur
    ...

Le parcours par valeur est plus lisible quand seule la valeur compte. Le parcours par indice est nécessaire quand on veut la position, ou comparer un élément à son voisin t[i + 1]. L'indice doit alors s'arrêter à $n - 2$, avec range(len(t) - 1).

2Manipulations élémentaires, indexation et extraction

2.1Tranches

On peut omettre une borne : t[:k] donne les $k$ premiers éléments, t[k:] tous les éléments à partir de l'indice $k$. La même syntaxe s'applique aux chaînes de caractères.

releves = [12, 14, 15, 17, 16, 13, 11]
releves[2:5]     # [15, 17, 16]
releves[:3]      # [12, 14, 15]
releves[3:]      # [17, 16, 13, 11]

Une tranche est une copie. Modifier releves[2:5] une fois extraite ne modifie pas releves. Son coût est proportionnel à sa longueur.

2.2Concaténation, répétition, retrait en fin

• t + u renvoie une nouvelle liste formée des éléments de t suivis de ceux de u ;
• t * 3 répète t trois fois ;
• t.pop() retire et renvoie le dernier élément.

Ces opérations permettent par exemple de fusionner les relevés de deux journées ou de retirer une dernière mesure aberrante.

2.3Copie et alias

L'affectation u = t ne crée pas de nouvelle liste. u et t désignent la même liste, et modifier u[0] modifie aussi t[0]. Pour obtenir une liste indépendante, on écrit u = t.copy() ou u = t[:].

2.4Extraire selon une condition

Pour extraire les valeurs qui vérifient une condition, on parcourt la liste et l'on ajoute les bonnes valeurs à une nouvelle liste.

def superieures(t, seuil):
    # t : liste de nombres. Renvoie la liste des éléments
    # de t strictement supérieurs à seuil, dans l'ordre.
    res = []
    for x in t:
        if x > seuil:
            res.append(x)
    return res

La compréhension avec condition, [x for x in t if x > seuil], fait la même chose en une ligne. Elle est très utilisée, mais elle n'est pas listée dans l'annexe et devrait être accompagnée d'une explication dans un sujet.

2.5Construire une liste à partir d'une autre par les indices

Beaucoup de manipulations élémentaires consistent à calculer une nouvelle liste case par case à partir des indices de l'ancienne. Deux exemples.

def renverse(t):
    # Nouvelle liste : éléments de t dans l'ordre inverse.
    n = len(t)
    return [t[n - 1 - i] for i in range(n)]

def differences(t):
    # Écarts entre éléments consécutifs, longueur len(t) - 1.
    return [t[i + 1] - t[i] for i in range(len(t) - 1)]

La seconde fonction sert par exemple à calculer la croissance d'une population d'une année sur l'autre à partir des effectifs annuels.

3Recherche d'un élément

3.1Présence

On veut savoir si une valeur x apparaît dans une liste t. On parcourt la liste et l'on s'arrête dès qu'on la trouve.

def est_present(t, x):
    # Renvoie True si x est un élément de t, False sinon.
    for y in t:
        if y == x:
            return True
    return False

3.2Position

Variante : renvoyer l'indice de la première occurrence, ou $-1$ si la valeur est absente. Cette convention doit toujours être précisée.

def premier_indice(t, x):
    for i in range(len(t)):
        if t[i] == x:
            return i
    return -1

• Pour la dernière occurrence, on parcourt sans s'arrêter et l'on garde le dernier indice trouvé.
• Pour le nombre d'occurrences, on incrémente un compteur.

3.3Coût

Dans le pire des cas, valeur absente ou en dernière position, on examine les $n$ éléments. Le nombre d'opérations est proportionnel à $n$ : on dit que le coût est linéaire. Doubler la taille du tableau double le temps de recherche.

On verra plus tard qu'une recherche dichotomique, possible sur un tableau trié, est beaucoup plus rapide.

4Recherche du maximum

4.1Valeur du maximum

On garde dans une variable la plus grande valeur rencontrée jusqu'ici, initialisée avec le premier élément, ce qui suppose la liste non vide.

def maximum(t):
    # t : liste non vide de nombres. Plus grande valeur.
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

C'est vrai au départ, et chaque tour de boucle le conserve. À la fin, m est le maximum de toute la liste. Une telle propriété s'appelle un invariant de boucle.

4.2Position du maximum

Souvent, l'information utile n'est pas la valeur mais la position, par exemple l'heure du pic de température. On garde alors l'indice.

def indice_max(t):
    im = 0
    for i in range(1, len(t)):
        if t[i] > t[im]:
            im = i
    return im

Avec la comparaison stricte, en cas d'égalité, on obtient la première position du maximum. Avec >=, on obtiendrait la dernière. Le minimum s'obtient en inversant la comparaison.

4.3Second maximum

Le second maximum demande de fixer une convention.

• Convention 1 : la deuxième valeur de la liste rangée par ordre décroissant, doublons compris. Le second maximum de [7, 9, 9, 4] est 9.
• Convention 2 : la plus grande valeur strictement inférieure au maximum. Elle vaut ici 7.

L'énoncé doit préciser la convention.

Pour la convention 1, on garde deux variables, m1 la plus grande valeur vue et m2 la deuxième. On suppose au moins deux éléments.

def second_maximum(t):
    # t : liste d'au moins deux nombres. Doublons comptés.
    if t[0] >= t[1]:
        m1 = t[0]
        m2 = t[1]
    else:
        m1 = t[1]
        m2 = t[0]
    for i in range(2, len(t)):
        x = t[i]
        if x > m1:
            m2 = m1
            m1 = x
        elif x > m2:
            m2 = x
    return m2

Un seul parcours suffit, le coût est linéaire.

Pour la convention 2, on peut calculer le maximum, puis chercher le maximum des valeurs qui lui sont strictement inférieures, en deux parcours. Il faut alors prévoir le cas où toutes les valeurs sont égales.

5Lecture et écriture dans un fichier texte

5.1Fichier texte et fichier de données

Un fichier de données comporte souvent une ligne d'en-tête décrivant les colonnes, puis une ligne par individu ou par mesure. Les valeurs sont séparées par un caractère fixé : point-virgule, virgule ou tabulation.

individu;masse_g;longueur_mm
1;23.1;87
2;25.4;91
3;22.8;85

5.2Les fonctions utiles

L'annexe du programme de BCPST ne liste pas ces fonctions. Un sujet qui les utilise en donne la documentation. Il faut néanmoins savoir les employer couramment en travaux pratiques.

• f = open(nom, "r") ouvre le fichier nom en lecture, "w" l'ouvre en écriture en effaçant son contenu, "a" en ajout à la fin.
• f.read() renvoie tout le contenu dans une seule chaîne.
• f.readline() renvoie la ligne suivante, fin de ligne comprise, ou une chaîne vide à la fin du fichier.
• f.readlines() renvoie la liste des lignes restantes.
• f.write(s) écrit la chaîne s, sans ajouter de fin de ligne.
• f.close() ferme le fichier, indispensable en écriture pour que les données soient réellement enregistrées.
• s.split(sep) découpe la chaîne s selon le séparateur sep et renvoie la liste des morceaux.

La lecture avance dans le fichier. Après un readline qui a lu l'en-tête, readlines ne renvoie que les lignes de données.

5.3Des chaînes aux nombres

Tout ce qu'on lit dans un fichier est du texte. La chaîne "23.1" doit être convertie avec float, et "87" avec int, avant tout calcul. Sinon, "23.1" + "25.4" donne la chaîne "23.125.4".

5.4Exemple de lecture

def lire_masses(nom):
    # nom : fichier individu;masse_g;longueur_mm avec en-tête.
    # Renvoie la liste des masses, en flottants.
    f = open(nom, "r")
    f.readline()                    # on saute l'en-tête
    masses = []
    for ligne in f.readlines():
        morceaux = ligne.split(";")
        if len(morceaux) == 3:      # on ignore une ligne vide
            masses.append(float(morceaux[1]))
    f.close()
    return masses

On combine ensuite lecture et recherche : indice_max(lire_masses("souris.csv")) donne la position de l'individu le plus lourd.

5.5Écriture

Pour enregistrer des résultats, on ouvre en mode "w", on écrit ligne par ligne en convertissant les nombres avec str et en ajoutant "\n", puis on ferme.

def ecrire_selection(nom, valeurs):
    f = open(nom, "w")
    f.write("masse_g\n")
    for v in valeurs:
        f.write(str(v) + "\n")
    f.close()

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Donner les indices valides d'une liste, expliquer une tranche t[i:j] et le nombre de ses éléments.
2. Expliquer la différence entre u = t et u = t.copy().
3. Écrire la recherche d'un élément, en version booléenne et en version indice, et donner son coût.
4. Écrire la recherche du maximum et de sa position, et justifier l'algorithme par un invariant.
5. Écrire le calcul du second maximum dans une convention donnée, et discuter l'autre convention.
6. Extraire d'une liste les éléments qui vérifient une condition.
7. Lire un fichier de données avec en-tête et en extraire une colonne sous forme de liste de flottants.
8. Écrire une liste de résultats dans un fichier texte.

Les résultats à connaître

En informatique, les « résultats » sont trois choses : le comportement exact du langage, la correction des algorithmes et leur nombre d'opérations dans le pire cas.

• Une liste t de longueur n a pour indices valides les entiers de 0 à n − 1. Lire ou écrire t[n] provoque une erreur : exigible.
• Pour 0 ≤ i ≤ j ≤ n, la tranche t[i:j] est une nouvelle liste de j − i éléments. Son coût est proportionnel à j − i : exigible.
• Une tranche dont les bornes dépassent la longueur ne provoque pas d'erreur. Elle est simplement tronquée : à savoir reconnaître.
• t.append(x) et t.pop() agissent en fin de liste avec un coût considéré comme constant. t + u crée une nouvelle liste, pour un coût proportionnel à len(t) + len(u) : exigible.
• u = t crée un alias. t.copy() et t[:] créent une copie indépendante : exigible.
• Une fonction qui modifie une liste reçue en argument modifie la liste de l'appelant : exigible.
• Recherche séquentielle : elle est correcte et fait au plus n comparaisons. Le coût est linéaire dans le pire cas : exigible avec justification par invariant.
• Maximum, minimum et leur position : un parcours, n − 1 comparaisons, sur une liste non vide : exigible avec invariant.
• Second maximum, doublons comptés : un parcours, au plus 2n comparaisons, sur une liste d'au moins deux éléments : exigible avec invariant.
• Extraction selon une condition : un parcours, et l'ordre des éléments est conservé : exigible.
• Fichier texte : la lecture est séquentielle, tout ce qu'on lit est une chaîne, et le mode "w" efface le fichier dès l'ouverture. Il faut savoir employer ces fonctions, mais un sujet les fournit avec leur documentation.
• Hors programme signalé : indices négatifs, fonctions max, min, sum et sorted, méthodes index, count et sort, construction with open, compréhension avec condition. Il est prudent de ne pas compter sur le test x in t quand l'énoncé demande d'écrire la recherche.

Clés de démonstration

Recherche d'un élément. Invariant : au début du tour d'indice k, x n'est égal à aucun des éléments t[0] à t[k − 1]. Si la boucle se termine sans return, x n'est donc égal à aucun élément. L'astuce est de voir que le return True est sûr dès qu'il se déclenche, et que seul le cas « non trouvé » demande l'invariant.

Maximum et position du maximum. Invariant : après examen des k premiers éléments, t[im] est le maximum de t[0:k] et im la première position où il est atteint. L'initialisation im = 0 le rend vrai pour k = 1. L'astuce est la comparaison stricte, qui préserve la première position en cas d'égalité.

Second maximum, doublons comptés. Invariant : après examen des k premiers éléments, m1 et m2 sont les deux premières valeurs de t[0:k] rangée par ordre décroissant. Quand x dépasse m1, l'ancien m1 devient le deuxième. Quand x est entre m2 et m1, seul m2 change. L'astuce est de traiter les deux premiers éléments à part, pour que l'invariant soit vrai dès k = 2.

Extraction. Invariant : après examen de t[0:k], res est la liste des éléments de t[0:k] qui vérifient la condition, dans leur ordre d'apparition. L'astuce est append, qui ajoute en fin et conserve donc l'ordre.

Coût. On compte les tours de boucle et le travail fait à chaque tour. Un parcours complet avec un travail constant par tour donne un coût proportionnel à n. Attention au travail caché : une tranche ou une concaténation dans une boucle coûte autant que sa longueur.

Terminaison d'un while à deux indices. La quantité entière j − i décroît strictement à chaque tour. Elle finit donc par devenir négative ou nulle, et la boucle s'arrête. L'astuce est de choisir la condition i < j, qui couvre les longueurs paires et impaires.

Exemples et contre-exemples à connaître

1. Avec m initialisé à 0, le maximum de [−3, −1, −7] vaut 0, valeur absente de la liste. C'est le cas d'école de la mauvaise initialisation.
2. Si le return False est placé dans un else à l'intérieur de la boucle, est_present([4, 7], 7) renvoie False, car la fonction s'arrête dès 4.
3. Après u = t puis u.append(5), t contient aussi 5. Les deux noms désignent la même liste.
4. Pour t de longueur 3, t[3] provoque une erreur, mais t[2:5] renvoie une liste d'un seul élément. Une tranche ne signale pas un dépassement.
5. Pour [7, 9, 9, 4], le second maximum vaut 9 si l'on compte les doublons, et 7 sinon. Sans convention, la question n'a pas de sens.
6. La ligne "1;23.1;87\n" découpée selon ";" donne ['1', '23.1', '87\n']. Le test '87\n' == '87' vaut False, alors que int('87\n') vaut bien 87.
7. "23.1" + "25.4" vaut "23.125.4". On a oublié de convertir en nombres.
8. float("23,1") provoque une erreur. La virgule décimale d'un tableur français doit être remplacée par un point.
9. Deux appels f.write("12.5") puis f.write("13.1") écrivent 12.513.1 sur une seule ligne. write n'ajoute pas de fin de ligne.
10. Après un readlines, un readline renvoie la chaîne vide. La lecture a déjà atteint la fin du fichier.

Techniques du chapitre

Technique 1, tester les bornes sur de toutes petites listes. Mini-exercice : combien de tours fait for i in range(len(t) - 1) pour t = [5] et pour t = [] ? Réponse : zéro dans les deux cas, car range d'un entier négatif ou nul est vide. Une comparaison de voisins ne plante donc pas sur ces listes.

Technique 2, garder un indice plutôt qu'une valeur. Mini-exercice : trouver l'heure du minimum de températures relevées de 0 h à 23 h. On adapte indice_max en remplaçant > par <. L'indice renvoyé est l'heure, et la valeur s'obtient ensuite par t[i].

Technique 3, sortir dès que la réponse est connue. Mini-exercice : tester que toutes les mesures sont positives. On parcourt et l'on renvoie False au premier x < 0. On place return True après la boucle. Une liste vide donne True, ce qui est la convention logique.

Technique 4, un compteur qu'on remet à zéro. Mini-exercice : dans une série de mesures, compter les montées, c'est-à-dire les i tels que t[i + 1] > t[i]. On parcourt range(len(t) - 1) et on incrémente c à chaque montée. Pour [1, 3, 2, 5], on obtient 2.

Technique 5, un tableau de compteurs indexé par les valeurs. Mini-exercice : compter les notes entières de 0 à 20. On crée c = [0] * 21, puis pour chaque note x on fait c[x] = c[x] + 1. La longueur 21 vient des 21 valeurs possibles.

Technique 6, lire, découper, nettoyer, convertir. Mini-exercice : extraire la masse de la ligne "3;22,8;85\n". On découpe selon le point-virgule et l'on prend le morceau d'indice 1, qui vaut "22,8". On remplace la virgule par un point, puis float donne 22.8.

Technique 7, écrire la spécification avant le code. Mini-exercice : spécifier une fonction position(t, x). On écrit en commentaire la nature de t, le résultat, et la convention −1 si x est absent. Le cas limite se déduit de la spécification : pour une liste vide, on renvoie −1.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

def derniere_occurrence(t, x):
    # Indice de la dernière occurrence de x dans t, ou -1.
    res = -1
    for i in range(len(t)):
        if t[i] == x:
            res = i
    return res

def amplitude(t):
    # t : liste non vide de nombres.
    mini = t[0]
    maxi = t[0]
    for x in t:
        if x > maxi:
            maxi = x
        elif x < mini:
            mini = x
    return maxi - mini

def est_croissante(t):
    for i in range(len(t) - 1):
        if t[i] > t[i + 1]:
            return False
    return True

def plus_longue_serie(t, seuil):
    meilleure = 0
    courante = 0
    for x in t:
        if x > seuil:
            courante = courante + 1
            if courante > meilleure:
                meilleure = courante
        else:
            courante = 0
    return meilleure

def second_strict(t):
    # t non vide. Renvoie (True, s) ou (False, 0).
    m1 = t[0]
    existe = False
    m2 = 0
    for x in t:
        if x > m1:
            m2 = m1
            existe = True
            m1 = x
        elif x < m1 and (not existe or x > m2):
            m2 = x
            existe = True
    return (existe, m2)

def effectifs(t, vmax):
    # t : entiers entre 0 et vmax.
    c = [0] * (vmax + 1)
    for x in t:
        c[x] = c[x] + 1
    return c

def lire_temperatures(nom):
    f = open(nom, "r")
    f.readline()
    temp = []
    for ligne in f.readlines():
        morceaux = ligne.split(";")
        if len(morceaux) == 3:
            texte = morceaux[2].replace(",", ".")
            temp.append(float(texte))
    f.close()
    return temp

def ecrire_anomalies(nom, t, seuil):
    f = open(nom, "w")
    f.write("indice;valeur\n")
    for i in range(len(t)):
        if t[i] > seuil:
            f.write(str(i) + ";" + str(t[i]) + "\n")
    f.close()

def moyenne_glissante(t, k):
    res = []
    s = 0
    for i in range(k):
        s = s + t[i]
    res.append(s / k)
    for i in range(k, len(t)):
        s = s + t[i] - t[i - k]
        res.append(s / k)
    return res

def renverse_sur_place(t):
    i = 0
    j = len(t) - 1
    while i < j:
        aux = t[i]
        t[i] = t[j]
        t[j] = aux
        i = i + 1
        j = j - 1

Erreurs fréquentes