Le développement d’un grand programme demande une certaine organisation, et en particulier un découpage des différents aspects du programme
et des différentes tâches qui doivent être accomplies. Ceci est d'autant plus vrai lorsque plusieurs personnes participent au développement.
Parmi ces questions relevant du génie logiciel (« génie », au sens d’ingénierie), nous nous intéressons dans cette séquence à la manière dont les différentes parties
d’un programme peuvent s’articuler.
L’un des objectifs consiste à spécifier le rôle de chaque partie suffisamment précisément pour que chacune puisse ensuite être réalisée indépendamment des autres.
Lorsque l'on réunit 23 personnes, ii y a une chance sur deux pour que deux d'entre elles soient nées le même jour. Ce résultat est appelé le paradoxe des anniversaires.
Ci-dessous, nous avons le programme qui le vérifie expérimentalement. Celui-ci permet de tirer 1000 fois aléatoire 23 dates d'anniversaire, c'est-à-dire 23 entiers entre 1 et 365.
De cette manière, vous allez observer combien de fois au moins deux personnes sont nées le même jour.
Le programme est le suivant :
from random import randint
def contient_doublon(t) :
s = set()
for x in t:
if x in s:
return True
s.add(x)
return False
nb_personnes = 23
nb_tirages = 1000
ok = 0
for __ in range(nb_tirages) :
if contient_doublon([randint(1,365) for __ in range(nb_personnes)]) :
ok += 1
print(\"nb doublons : \",ok)
Tester le code ci-dessus et en déduire si le paradoxe des anniversaires est vérifié expérimentalement.
Ce programme, consiste à remplir un tableau de taille 23 avec les dates d'anniversaire tirées au hasard puis à vérifier si ce tableau contient au moins un doublon à l'aide de la fonction contient_doublon().
Celle-ci passe tous les éléments en revue et les stocke à la volée dans un ensemble s, jusqu’à trouver un élément déjà présent dans cet ensemble, c'est-à-dire qui apparaissait déjà plus tôt dans le tableau t.
Nous allons voir différente manière pour écrire la fonction contient_doublon()
Mettre le résultat ici (code et figure).
Si nous utilisions un simple tableau pour s comme dans
le programme 1. L'opération append est efficace. Le problème vient seulement du test x in s dont le temps d'exécution est le plus souvent proportionnel au nombre d'éléments stockés dans s.
Nous pouvons améliorer cela avec une recherche dichotomique si le tableau est trié, Mais pour trié le tableau s, il faudra insérer les éléments au bon endroit et décaler tous les suivants. Le coût de cette méthode est proportionnel au nombre d'éléments dans le tableau.
Nous allons utiliser une autre approche pour laquelle le coût du test est minimal.
Regarde le programme 2, Alice, nous créons un grand tableau de booléens, un pour chaque date possible.
Nous décidons que s{x] vaut True si nous avons enregistré x et False sinon.
Programme 1 — rechercher un doublon dans un tableau
def contient_doublon(t):
\"\"\"Le tableau t contient-il un doublon ?\"\"\"
s = []
for x in t:
if x in s:
return True
s.append(x)
return False
Programme 2 — rechercher un doublon dans un tableau
def contient_doublon(t):
\"\"\"Le tableau t contient-il un doublon ?\"\"\"
s = [False] * 367
for x in t:
if s[x]:
return True
s[x] = True
return False
L'inconvénient de cette méthode, c'est de prendre un tableau de 366 cases pour utiliser que 23 éléments.
Il est dommage que les booléens occupent autant d'espace en mémoire que des nombres entiers (au moins 8 octets, 64 bits!), alors qu’un seul bit est réellement utile pour choisir entre les deux valeurs True ou False. le tableau s du programme 2 est 64 fois trop grand!
Nous allons compacter cela en utilisant des entiers pour représenter plusieurs booléens. En effet, la représentation des entiers en machine est une suite de bits (0 ou 1!) basée sur leur écriture en base 2. De plus, il existe des opérations arithmétiques classiques qui
agissent directement sur cette représentation binaire.
Par exemple, l’opéra-tion | de « ou » bit à bit renvoie l’entier pour lequel chaque bit vaut 1 dès lors
qu’il valait 1 dans au moins l’un des paramètres : si je prends 40 qui s'écrit en binaire 101000 et 10 qui s’écrit en binaire 1010 (ou 001010 si j'ajoute
des zéros pour avoir le même nombre de chiffres), l'opération 40 | 10 me renvoie l’entier dont l'écriture binaire est 101010, c’est-à-dire 42.
Nous considérons un entier s de 64 bits représente par un tableau b de 64 booléens, dont la clé de lecture.b[x] vaut True si et seulement si le bit de rang x de s vaut 1.
Ainsi l’entier 26, qui s’écrit en binaire 0...011010, représente le tableau de booléens (False, True, False, True, True, False, ..., False], autrement dit l’ensemble {1,3,4}. Alors je peux utiliser l’entier 2, qui a tous
ses bits à 0 sauf le bit de rang x qui vaut 1, comme révélateur.
On calcule 2x avec l'opération de décalage 1 << x. Si je fais un « ou » bit à bit s | ( 1 << x) je fais passer le bit de rang x de s à 1 (et il y reste s'il y était déjà). Si en revanche je fais un «et » bit à bit s & (1 << x) j'obtiens soit 2x si b{x] vaut True, soit 0 sinon. Avec ces ingrédients, on pourrait obtenir le programme 3. En plus, c’est particulièrement facile à écrire en Python,
les entiers n'étant même pas limités à 64 bits.
De plus, sans ces entiers illimités on pourrait aussi utiliser un tableau d’entiers ordinaires. On décompose x sous la forme x = i + 64j avec les opérations
de quotient et de reste de la division entière et on fait correspondre à x le bit de rang i de l’entier d'indice j.
Le code s'exécute aussi vite, et on gagne un facteur 64 en occupation de la mémoire par rapport au tableau de booléens.
Pour notre cas d'application effectivement il suffirait alors d’un tableau de six entiers pour représenter n'importe quel ensemble de dates d'anniversaires, comme dans le programme 4. Dans ce cas précis, cela m'a l'air d’être imbattable.
Cependant, si on ne parle plus de jours de l’année et que l’amplitude des éléments auxquels on s’intéresse est bien plus grande que l'intervalle [1,366], ce facteur 64 gagné finira par devenir dérisoire. »
Programme 3 — rechercher un doublon dans un tableau
def contient_doublon(t):
\"\"\"Le tableau t contient-il un doublon ?\"\"\"
s = 0
for x in t:
if s & (1 << x) != 0:
return True
s = s | (1 << x)
return False
Programme 4 — rechercher un doublon dans un tableau
def contient_doublon(t):
\"\"\"le tableau t contient-il un doublon ?\"\"\"
s = [0] * 6
for x in t:
if s[x // 64] & (1 << (x % 64)) != 0:
return True
s[x // 64] = s[x // 64] | (1 << (x % 64))
return False
La représentation des ensembles développée dans les programmes 3 et 4 donne les idées essentielles de la
structure de tableau de bits (en anglais bit array ou bit set).
Cette structure donne une représentation compacte d’un ensemble de booléens. Elle permet donc une meilleure utilisation des ressources de mémoire limitées comme la mémoire cache, cette mémoire accessible
beaucoup plus rapidement que la mémoire vive de l’ordinateur et conservant temporairement les derniers éléments consultés.
L'avantage du programme 1 qui stockait directement les éléments dans le tableau s était d’avoir un tableau dont la taille correspondait au nombre d'éléments présents. L’inconvénient en était que chaque élément pouvait se trouver n’importe où dans le tableau.
À l'inverse, dans le programme 2 et ses dérivés, il était immédiat de trouver la case du tableau liée à un élément donné, mais il fallait pour cela utiliser un tableau bien trop grand.
Peut-on combiner les avantages de ces deux méthodes ?
Prendre par exemple un tableau de 23 cases, puisque pour l'application au paradoxe des anniversaires c’est le nombre d'éléments que l’on est susceptible de stocker dans notre ensemble, dans lequel chacune des 366 dates est liée a priori à une et une seule de ses cases ?
Programme 5 — rechercher un doublon dans un tableau
def contient_doublon(t):
\"\"\"Le tableau t contient-il un doublon ?\"\"\"
s = [[] for __ in range(23)]
for x in t:
if x in s[x % 23]:
return True
s[x % 23].append(x)
return False
C’est cela. Nous pourrions par exemple, s’il faut enregistrer l’entier x, le placer dans la case d'indice x % 28.
Mais que faire si l’on doit stocker deux éléments associés à la même case ? Par exemple 24 et 47?
On pourrait stocker dans la case s[i] un tableau contenant tous les éléments x enregistrés tels que x % 23 vaut i. Voir le programme 5.
Je comprends, nous avons un maximum de 23 éléments à répartir entre 23 petits tableaux (appelons ces derniers des paquets). Chacun des 23 paquets sera quasiment vide. Même sans la moindre organisation des éléments à l’intérieur de chaque paquet le coût des tests x in s[x % 23] sera en général négligeable. Nous perdrions en efficacité seulement si de nombreux
éléments se retrouvaient aiguillés par malchance dans le même paquet, mais la situation est extrêmement peu probable. Ici en l'occurrence, tous les jours de naissance étant à peu près également probables, la répartition dans les différents paquets a les meilleures chances d’être équitable.
— Et on peut toujours imaginer sinon une fonction de répartition qui mélange convenablement les éléments, en évitant que deux dates similaires se trouvent systématiquement envoyées dans le même paquet. Avec un peu d’arithmétique on devrait certainement pouvoir arranger cela. En revanche, peut-on adapter l’idée si l’on ne connaît pas à l’avance le nombre d’éléments ?
— On pourrait partir d'un nombre de paquets arbitraire, et agrandir le tableau s lorsque l’on commence à avoir trop d’éléments par rapport au nombre de paquets. On peut tenter une nouvelle version de notre programme. »
Factorisation du code
« Stop. Nous avons déjà écrit un certain nombre de programmes quasiment identiques, en changeant simplement une petite structure de données.
J'aimerais bien qu’on puisse mettre fin à ces redondances et se concentrer sur l'essentiel.
— Comment comptes-tu t’y prendre ?
— Commençons par regarder les parties qui n’ont jamais changé une version du programme à l’autre.
def contient_doublon(t):
\"\"\"le tableau t contient-il un doublon ?\"\"\"
s = ...
for x in t:
if ... :
return True
...
return False
Dans tous les cas, la structure s représente d’une manière ou d’une autre un ensemble de dates. Le premier trou correspond à la création de la structure s, le deuxième au test de la présence de x dans s et le dernier à l’ajout de x dans s.
Seules ces trois choses varient d’un programme à l’autre.
— On pourrait donc isoler ces trois aspects dans trois fonctions cree(),
contient et ajoute pour avoir la fonction contient_doublon unique suivante.
def contient_doublon(t):
\"\"\"Ile tableau t contient-il un doublon ?\"\"\"
s = cree()
for x in t:
if contient(s, x):
return True
ajoute(s, x)
return False
Ainsi, on pourrait changer la représentation de l’ensemble de dates s en changeant uniquement les définitions de ces trois fonctions, sans qu'il y ait
besoin de toucher à la fonction contient_doublon.
— Et on gagnerait même plus : une fois ainsi isolée, notre définition des ensembles de dates pourrait plus facilement être réutilisée dans un autre programme qui en aurait également besoin.
— D'une certaine manière, ces trois fonctions définissent une frontière entre un programme qui utilise une structure de données et un programme qui la
définit. Celui qui l'utilise n’a pas besoin de connaître le détail de la réalisation de la structure utilisée, et cette réalisation peut elle-même être faite sans savoir comment ni combien de fois elle sera utilisée.
— Frontière n’est pas vraiment le mot. Certes la séparation permet d'ignorer ce qui se passe de l’autre côté, mais ces fonctions sont plutôt l'outil qui permet aux deux programmes d’interagir, de coopérer. Je parlerais plutôt d’une interface. »
Une des clés du développement à grande échelle consiste à circonscrire et séparer proprement les différentes parties du programme.
On peut par exemple séparer le code qui définit une
structure de données du code qui l’utilise, ou dans un plus grand projet séparer l'interface graphique du cœur de l'application.
Chacun des morceaux obtenus peut être placé dans un fichier de code différent, appelé un module.
Un petit module de manipulation d’ensembles de dates correspondant à la stratégie du programme 4 pourrait ainsi être défini par le fichier dates .py reproduit dans le programme 6.
Mettre le résultat ici (code et figure).
Tout projet a donc un code séparé en plusieurs modules, les fonctionnalités définies dans l’un pouvant être utilisées par d’autres. Nous avons pu observer cette utilisation par un programme principal de fonctionnalités issues d’un autre module avec les directives import et les appels à des bibliothèques livrées avec Python, comme random, math, turtle et ....
Nous allons voir ici que cela s'applique également à des modules définis par nous-mêmes ou par des tiers. En particulier, une définition de notre fonction contient _doublon utilisant le module dates défini par le programme 6 s’écrirait comme dans le
programme 7.
Notez qu'en Python le nom d’un module défini par un fichier de code s’obtient simplement en retirant le suffixe .py au nom du fichier.
Un module peut donc faire référence à un certain nombre d'autres modules, qui peuvent aussi bien être issus du projet lui-même que de sources extérieures. On dit alors qu’il dépend de ces autres modules. En dehors de ces dépendances, un module reste a priori autonome et indépendant du reste du projet.
En conséquence, un module constitue également une « brique » logicielle pouvant être réutilisée dans d’autres projets (ou plusieurs fois dans un même projet). On a donc tout intérêt à ce que chaque module soit dédié à la résolution d’une tâche, ou d’un ensemble de tâches apparentées, clairement identifiable.
Cela permet notamment, à chaque fois que le même problème se pose à nouveau, de faire appel au module déjà défini plutôt que d'écrire une nouvelle fois un code similaire et dépenser son temps à résoudre un problème déjà résolu.
Ainsi, si l’on veut savoir combien d'élèves il faut en moyenne dans une école pour qu’un anniversaire soit fêté chaque jour, on peut utiliser un programme tirant des dates au hasard et les stockant dans un ensemble jusqu’à ce que toutes aient été obtenues au moins une fois. Le programme 8 réalise cela. en tirant narti de notre module dates
Programme 6 — dates.py
def cree():
return [0] * 6
def contient(s, x):
paquet = x // 64
bit = x % 64
return s[paquet] & (1 << bit) != 0
def ajoute(s,x):
paquet = x // 64
bit = x % 64
s[paquet] = s[paquet] | (1 << bit)
Programme 7 — rechercher un doublon dans un tableau
from dates import cree, contient, ajoute
def contient_doublon(t):
\"\"\"le tableau t contient-il un doublon ?\"\"\"
s = cree()
for x in t:
if contient(s, x):
return True
ajoute(s, x)
return False
Programme 8 — fête continue
from dates import cree, contient, ajoute
from random import randint
def fete_continue():
compteur = 0
nombre_dates = 0
s = cree()
while nombre_dates < 366:
compteur += 1
x = randint(1, 366)
if not contient(s, x):
nombre_dates += 1
ajoute(s, x)
return compteur
n = 0
for __ in range(1000):
n += fete_continue()
print (\"En moyenne\", n / 1000, \"élèves\")
Mettre le résultat ici (code et figure).
cree() crée et renvoie un ensemble de dates vide
contient(s, x) | renvoie True si et seulement si l’ensemble 5
contient la date x
ajoute(s, x) ajoute la date x à l’ensemble sInterfaces
Pour chaque module, on distingue :
- sa réalisation ou implémentation, c’est-à-dire le
code lui-même;
- son interface, consistant en une énumération des fonctions définies dans le module qui sont destinées à être utilisées dans la réalisation d’autres modules, appelés clients.
L'interface d’un module est liée à sa documentation, et doit notamment expliciter ce qu’un utilisateur a besoin de connaître des fonctions proposées :
comment et pour quoi les utiliser.
Pour chaque fonction de l’interface, on a besoin de :
- son nom,
- de la liste de ses paramètres
- de sa spécification, c'est-à-dire les conditions auxquelles la fonction peut être appliquée et les
résultats à attendre.
Des informations supplémentaires concernant des caractéristiques comme le temps d’exécution ou l’espace mémoire requis peuvent également être utiles.
L'objectif est que ces fonctions incluses dans l'interface soient suffisantes pour permettre à un utilisateur de faire appel aux fonctionnalités du module,
et qu’elles puissent être utilisées sans avoir besoin d’aller consulter le code du module.
L'interface peut être décrite comme une abstraction du module :
une description de ce qui caractérise le module, mais faite à un niveau assez haut, ignorant les détails concrets de la réalisation.
La documentation de l'interface peut être vue comme un contrat entre l’auteur d’un module et ses utilisateurs, qui simplifie l(utilisation du module en limitant le nombre
de choses qu’il faille lire, comprendre et mémoriser pour utiliser le module.
Ainsi, pour être utilisable par notre fonction contient_doublon, l’interface d’un module permettant de manipuler des ensembles de dates devra fournir au minimum les trois fonctions décrites dans l'interface 1.
Mettre le résultat ici (code et figure).
On dit qu’un module réalise une interface dès lors qu’il définit (au moins) toutes les fonctions promises par l'interface.
Ainsi, le programme 6 et le programme 9 réalisent tous deux l’interface 1, avec les stratégies de représentation des ensembles utilisées dans le programme 4 et le programme 5.
Dans le programme 9, on a ajouté une fonction enumere() construisant un tableau avec les éléments de l’ensemble s donné en paramètre, qui peut notamment
servir à écrire une boucle for sous la forme
for x in enumere(s):
pour énumérer les éléments de l’ensemble s.
Comme nous venons de le voir, une même interface peut admettre une variété de réalisations radicalement différentes. Nous en étudierons plusieurs exemples dans les séquences consacrés à l’algorithmique et aux structures de données.
Programme 9 -ensemble.py
def cree():
return [[] for _ in range(23)]
def contient(s, x):
return x in s[x % 23]
def ajoute(s, x):
s[x % 23].append(x)
def enumere(s) :
tab = []
for paquet in s:
tab.extend(paquet)
return tab
De la difficulté de définir une bonne interface et un code vraiment réutilisable. Dans notre exemple, nous avons introduit une interface pour une structure représentant un ensemble de dates. Nous connaissions un certain nombre de choses sur les données du problème, et notamment que les données à stocker dans l’ensemble étaient des entiers compris entre 1 et 366. Le programme 6 tire d’ailleurs pleinement parti de cette
information. De même, le programme 9 tire parti du fait que l’on n’attend pas plus de 23 dates.
Que se passerait-il si l’on souhaitait généraliser ces programmes et les utiliser pour représenter d’autres ensembles que ceux prévus initialement?
Pour adapter le programme 6 à un intervalle d’entiers de 0 à n on peut imaginer donner n en paramètre à la fonction cree(). Pour que le programme 9 reste efficace lorsqu'il représente des ensembles de 10000 éléments on peut de même imaginer donner le nombre d'éléments attendu en paramètre à la fonction cree().
Ces deux améliorations impliquent en revanche deux manières différentes de modifier l'interface de notre structure d'ensemble. Le programme 10 montrera à l'inverse une manière de généraliser le programme sans changer l'interface, mais ceci n’est pas toujours possible.
Le contrat qu’une interface établit entre le client et l’auteur d’un module ne porte pas sur les moyens, mais sur les résultats : l’auteur s'engage à ce que les résultats produits par l’utilisation de ses fonctions soient ceux décrits, mais il est libre de s’y prendre comme il le souhaite pour y parvenir.
Ainsi, l'auteur d’un module est libre d'utiliser les structures de données qui lui conviennent, mais aussi de définir toute une panoplie de fonctions ou objets annexes uniquement destinés à un usage interne et qui ne sont pas inclus dans l'interface.
Ces éléments internes, qui sont souvent qualifiés de «détails d’implémentation» mais peuvent constituer une large part du code lui-même, ne doivent pas être utilisés par les modules clients. Tous ces éléments hors de l’interface sont parfois qualifiés de privés, et on parle à leur propos d’encapsulation pour signifier qu’ils sont comme enfermés dans une boîte hermétique, dont l'utilisateur n’a pas à connaître le contenu et qu’il
doit encore moins ouvrir.
Ce principe d’encapsulation réduit le couplage entre les différents modules, en évitant que les modifications du code d’un module ne nécessitent d'adapter le code de ses modules clients (pourvu que l’interface soit toujours respectée). Ainsi, l’auteur d’un module peut mettre à jour son code pour le corriger ou l'améliorer, éventuellement en modifiant ou supprimant
certains de ses éléments internes, sans que les projets dépendant de son module n’en souffrent :
si ces derniers fonctionnaient avant la mise à jour, ils fonctionneront toujours après.
On peut donc par exemple modifier notre module ensemble pour l’adapter à la représentation d’ensembles d’entiers quelconques.
Au lieu de constamment utiliser un tableau de 23 paquets qui deviendront tous très grands en moyenne si l’on doit stocker de nombreux éléments dans l’ensemble, on va permettre au nombre de paquets d'augmenter à mesure que le nombre d'éléments dans l’ensemble augmente lui aussi.
Le programme 10 donne un tel programme dans lequel on commence avec 32 paquets, ce nombre étant doublé à chaque fois que le nombre d’éléments dépasse le nombre de paquets. Pour ne pas avoir besoin de recalculer en permanence la taille de l’ensemble représenté, on conserve en outre cette
information avec la table. Un ensemble est ainsi représenté par une paire nommée, réalisée par un dictionnaire contenant deux clés : ’paquets’ pour
la table des paquets et ’taille’ pour le nombre d'éléments. Dans cette nouvelle version, la fonction ajoute, après avoir augmenté la taille de l’ensemble, étend au besoin le tableau des paquets avec une fonction auxiliaire _etend. Cette fonction crée un nouveau tableau avec deux fois plus de paquets dans lequel elle réinsère tous les éléments, avant de lui faire prendre la place du tableau de paquets d’origine. Dans cette opération, les éléments réinsérés sont à nouveau ventilés dans l’ensemble des nouveaux paquets. Les
fonctions ajoute et _etend font de plus toutes deux appel à une fonctionauxiliaire _ajoute_aux qui ajoute un élément à une table de paquets. Notez également un point que nous avions laissé de côté jusqu'ici : la fonction ajoute prend garde à ne pas ajouter un élément déjà présent, de sorte que la taille enregistrée corresponde bien au cardinal de l’ensemble.
Programme 10 — ensemble.py
def cree():
return { 'taille':0,
'paquets': [[] for __ in range(32)] }
def contient(s, x):
p = x % len(s['paquets'])
return x in s['paquets'][p]
def ajoute(s, x):
if contient(s, x):
return
s['taille'] += 1
if s['taille'] > len(s['paquets']):
etend(s)
_ajoute_aux(s['paquets'], x)
def _ajoute_aux(t, x):
p = x % len(t)
t[p].append(x)
def _etend(s):
tmp = [[] for __ in range(2 * len(s['paquets']))]
for x in enumere(s):
_ajoute_aux(tmp, x)
s['paquets'] = tmp
def enumere(s):
tab = []
for paquet in s['paquets']:
tab.extend(paquet)
return tab
En Python, l’auteur d’un module peut indiquer que certains éléments (variables globales ou fonctions) sont privés en faisant commencer leur nom par le symbole _. Par convention, tous les autres éléments sont «publics» et doivent être compris comme appartenant à l'interface.
Il faut cependant savoir que dans ce langage, l’encapsulation est une pure convention (certains disent, un vœu pieux), et son respect est sous la seule responsabilité des programmeurs des modules clients. Rien dans les mécanismes du langage n’empêche l'accès aux éléments privés, ni leur utilisation, ni leur modification.
De nombreux autres langages de programmation, mieux adaptés aux projets à grande échelle, introduisent en revanche un contrôle strict de l’encapsulation en rendant l’accès aux éléments privés très compliqué voire impossible.
Le programme 10 ébauche la structure de données fondamentale de table de hachage, sous-jacente aux ensembles et aux dictionnaires de Python. Cette structure très polyvalente permet de représenter des ensembles de taille arbitraire, avec des opérations d’accès aux éléments extrêmement rapides.
Elle est considérée comme la plus efficace dans la plus grande variété des cas courants.
Le principal élément manquant pour obtenir une vraie table de hachage est une fonction appelée fonction de hachage, qui prend en paramètre l'élément à stocker et renvoie un nombre entier définissant (modulo le
nombre de paquets) le numéro du paquet dans lequel insérer l'élément.
Via cette fonction de codage de l'élément à stocker, on peut donc utiliser une table de hachage pour représenter des ensembles d'éléments de toutes sortes, et pas seulement des ensembles d’entiers. En outre, une fonction de hachage est souvent utilisée même pour les tables stockant des entiers, afin de mélanger les éléments et éviter que des nombres liés
les uns aux autres (par exemple, des multiples) ne se retrouvent systématiquement dans le même paquet.
Dans le cas des nombres entiers, on pourra par exemple utiliser des multiplications par des grands nombres premiers combinées à des rotations de la représentation binaire. L'équité de la répartition des éléments dans les différents paquets, et donc l’efficacité de cette structure de données, dépend de la qualité du mélange opéré par cette fonction de hachage. Mais avec une fonction de hachage
convenable, on peut en pratique considérer que la recherche ou l'ajout d’un élément dans une table de hachage sont des opérations instantanées.
Manipuler les fonctionnalités d’un module en n’utilisant que les fonctions fournies par son interface permet de ne pas se soucier des détails d’implémentation de ce module. Du moins tant que tout se passe bien.
Erreurs. Considérons le module dates du programme 6, et essayons d'ajouter à un ensemble une date invalide.
>>> import dates
>>> s = dates.cree()
>>> dates.ajoute(s, 421)
Traceback (most recent call last):
File \"<stdin>\", line 1, in <module>
File \"-/lib/dates.py\", line 12, in ajoute
s[paquet] = s{paquet] | (1 << bit)
IndexError: list index out of range
Le message d'erreur est fâcheux pour plusieurs raisons:
- il mentionne une IndexError, alors que nous ne voulions pas savoir que cette structure utilisait en interne un tableau ;
- pire, la ligne de code fournie ne permet en rien de comprendre le dépassement de tableau : elle mentionne un tableau s dont on ne connaît pas la longueur, et un indice paquet dont on ne connaît
pas le lien avec les paramètres s et 421 fournis à ajoute.
Comprendre en détail cette erreur demande d’explorer le code du module dates, ce qui fait perdre une partie des bénéfices de l’encapsulation.
Remarquez que, plus sournoisement, d’autres dates invalides n’auraient pas déclenché d'erreur.
>>> dates.ajoute(s, 377)
>>> dates.ajoute(s, -383)
Mais quelles dates auraient été ainsi ajoutées ?
Les six entiers de notre tableau fournissent au total 384 bits, dont nous n’utilisons que les numéros 1 à 366 (le numéro 0 est ignoré pour simplifier les calculs). L'ajout de 377 se fait sur un des bits inutilisés du dernier entier du tableau, qui ne correspond à aucune date particulière. L’ajout de -383 en revanche touche le bit du premier janvier.
En l’état actuel des modules définis dans cette séquence, une mauvaise utilisation
dae fnnrtinne de l’interfara riens d'ancendrer As srranre an des affatecollatéraux
qui ne peuvent être compris et anticipés sans une connaissance approfondie du code de ces modules. Ceci contredit le principe d’encapsulation.
Une meilleure pratique consiste, lors du développement de nos modules à renvoyer à l'utilisateur des erreurs explicites, qui peuvent être interprétées à l’aide de la seule connaissance de l'interface. Cette pratique approfondit la notion de programmation défensive.
Tester et mettre le résultat ici (code et figure).
Nous avons déjà pu observer à de nombreuses reprises des programmes s’interrompre avec des messages d’erreurs variés.
Erreurs.
>>> t = [1, 1, 2, 5, 14, 42, 132]
>>> t[12]
Traceback (most recent call last):
File \"<stdin>\", line 1, in <module>
IndexError: list index out of range
De telles «erreurs» sont appelées en programmation des exceptions et correspondent à la détection,
ici faite par l'interprète Python lui-même, d’un problème empêchant la bonne exécution du programme. Lorsqu'une exception survient, l’exécution du programme est interrompue sur le champ, à moins d’une prise en charge spécifique que nous verrons plus loin dans cette section.
Le tableau suivant redonne quelques exceptions courantes, observables en utilisant les structures de base de Python.
NameError Description
IndexError accès à un indice invalide d’un tableau
KeyError accès à une clé inexistante d’un dictionnaire
ZeroDivisionError | division par zéro
TypeError opération appliquée à des valeurs incompatibles
Il est possible de déclencher directement toutes ces exceptions (on dit « lever une exception ») avec l'opération raise de Python.
>>> raise IndexError(’indice trop grand’)
Traceback (most recent call last):
File \"<stdin>\", line 1, in <module>
IndexError: indice trop grand
Cette opération s'écrit en faisant suivre le mot-clé raise du nom de l’exception à lever, lui-même suivi entre parenthèses d’une chaîne de caractères donnant des informations sur l’erreur signalée.
On peut ainsi définir par exemple une fonction
ecrit(t, i, v)
destinée à remplacer l'opération primitive t[i] = v de modification de la valeur d’une case d’un tableau pour empêcher tout accès involontaire à un indice négatif?.
def ecrit(t, i, v):
if i < 0:
raise IndexError(\"indice négatif”)
tli] = v
La levée d’une exception avec raise interrompant l'exécution du programme, remarquez que dans le code de cette fonction nous n'avons pas eu besoin de else : l'instruction t[i] = v ne sera exécutée que si le programme n’a pas été interrompu.
Mettre le résultat ici (code et figure).
Le message affiché lorsqu'une exception interrompt un programme donne un aperçu de l’état de la pile d'appels au moment où l'exception à été levée. On y voit donc quelle première fonction a appelé quelle deuxième fonction qui a, à son tour, appelé quelle
autre fonction, etc., jusqu’à arriver au point où l'exception a été levée.
Il s’agit d’une information inestimable pour comprendre le contexte du problème et le corriger.
Mettre le résultat ici (code et figure).
Les exceptions peuvent être utilisées en particulier dans les fonctions formant l'interface d’un module, pour signaler à un utilisateur du module toute utilisation incorrecte de ces fonctions.
L'interface mentionnera dans ce cas quelles exceptions spécifiques sont levées et dans quelles conditions. On
peut ainsi mettre à jour l'interface 1 comme suit.
contient(s, x) : renvoie True si et seulement si l’ensemble s contient l'élément x
ajoute(s, x) ; ajoute l'élément x à l'ensemble s si 1<x<366 et lève une exception ValueError sinon.
Programme 11 — dates.py
def cree():
return [0] * 6
def contient(s, x):
if x < 1 or x > 366:
return False
paquet = x // 64
bit = x % 64
return s[paquet] & (1 << bit) != 0
def ajoute(s, x):
if x < 1 or x > 366 :
raise ValueError(\"date \" + str(x) + \" invalide\")
paquet = x // 64
bit = x % 64
s[paquet] = s[paquet] | (1 << bit)
L’exception ValueError de Python est à utiliser dans les cas où un paramètre inadapté est donné à une fonction. C’est ici le cas lorsque le paramètre x de la fonction ajoute est un nombre qui n’est pas dans la plage représentant une date valide.
Pour se conformer à cette interface, le programme 6 peut être complété sous la forme du programme 11.
La fonction ajoute commence par vérifier la valeur de x, et lève une exception en cas de problème. Le message associé
précise la valeur de x qui a posé problème. Notez que la fonction contient ne lève pas d'exception en cas de date invalide. Elle se contente alors de renvoyer False.
Les exceptions levées par un programme peuvent avoir plusieurs causes.
Certaines traduisent des erreurs du programme : elles sont imprévues et leurs conséquences ne sont par définition pas maîtrisées. Dans ces conditions,
interrompre l'exécution du programme est légitime. D’autre exceptions, en revanche, s'inscrivent dans le fonctionnement normal du programme : elles correspondent à des situations connues, exceptionnelles mais possibles. Dans cette ligne de code, par exemple, il est tout à fait envisageable que la chaîne de caractères entrée par l’utilisateur ne représente pas un entier valide.
x = int(input(\"Entrer un jour\"))
Dans ce cas, la fonction int lève une exception ValueError, de même que notre fonction ajoute du programme 11 lorsque l’entier fourni n'est pas dans la plage de valeurs attendue.
Une telle exception, qui correspond à un événement prévisible, n’est pas forcément fatale. Certes le programme ne peut pas poursuivre son exécution
comme si de rien n’était, puisque certaines choses n’ont pas eu lieu normalement :
- sur cet exemple, la variable x n'aurait pas été définie.
Cependant, en tant que programmeur, on peut anticiper cette éventualité et prévoir un comportement alternatif du programme pour cette situation exceptionnelle.
Dans le cas présent, on pourrait par exemple demander à nouveau un jour à l'utilisateur, après avoir affiché un message précisant le format attendu.
Pour mettre en place ce comportement alternatif, il faut rattraper cette exception, c’est-à-dire l’intercepter avant que l'exécution du programme ne soit définitivement abandonnée, avec la construction suivante :
try :
x = int(input(\"Entrer un jour : \"))
except ValueError:
print(\"Prière d’entrer un entier valide\")
Le mot-clé try suivi du symbole : (deux-points) introduit un premier bloc de code, puis le mot-clé except suivi du nom de l'exception et du symbole :
précède un deuxième bloc de code.
On qualifiera le premier bloc de normal et le second d’alternatif.
L’exécution d’une telle instruction procède comme suit. On exécute d’abord le bloc de code normal. Si l’exécution de ce bloc s'achève normalement, sans lever d'exception, alors le bloc alternatif est ignoré et on passe directement aux instructions suivantes. Si à l’inverse une exception est levée dans l’exécution du bloc normal, alors l’exécution de ce bloc est immédiatement interrompue et le nom de l'exception levée est comparé avec le nom
précisé à la ligne except. Si les noms correspondent, l'exception est rattrapée et on exécute le bloc de code alternatif avant de passer à la suite. Sinon,
l'exception est propagée et le programme s’interrompt, à moins que le fragment de code considéré soit lui-même inclus dans une autre construction try /except qui pourra à son tour tenter de rattraper l’exception.
Un fragment de code ajoutant une date saisie par un utilisateur à un ensemble s pourra ainsi avoir la forme suivante :
while True:
try:
x = int(input(\"Entrer un jour : \"))
dates.ajoute(s, x)
break
except ValueError:
print (\"Il faut un nombre entier entre 1 et 366\")
Notez que int et ajoute sont toutes deux susceptibles de lever une exception ValueError : la première si la saisie n’est pas un nombre entier et la seconde
si l’entier saisi n’est pas dans la bonne plage. Toutes deux sont rattrapées par notre bloc alternatif.
Si en revanche la valeur saisie convient, alors l'exécution du bloc try s'achève avec l'instruction break qui met fin à la boucle infinie while True.
Mettre le résultat ici (code et figure).
Si. l’on prévoit que plusieurs exceptions peuvent être rattrapées, il est possible d'écrire plusieurs blocs alternatifs, chacun associé à sa ligne except.
try:
<bloc normal>
except Exception1:
<bloc alternatif 1>
except Exception2:
<bloc alternatif 2>
Notez que seules les exceptions levées lors de l’exécution du bloc normal peuvent être rattrapées : les exceptions du premier bloc alternatif ne sont jamais rattrapées par les blocs alternatifs suivants. Autrement dit, les exceptions levées par un bloc alternatif ne peuvent être rattrapées que par une autre construction try /except englobante.
Mettre le résultat ici (code et figure).
.Si l’on ne précise pas de nom d’exception après except, alors foutes les exceptions seront rattrapées par ce bloc alternatif.
while True:
try:
x = int(input(\"Entrer un jour : \"))
dates.ajoute(s, x)
break
except :
print (\"Il faut un nombre entier entre 1 et 366\")
C'est généralement une mauvaise idée, car on rattrape alors à la fois les exceptions qu’il est légitime de rattraper et celles qui traduisent des erreurs que l’on ne soupçonnait pas. Ce faisant, on efface donc les traces
de ces éventuelles erreurs et on complique leur diagnostic.
Un cas d'usage légitime du rattrapage indiscriminé consisterait à fournir quelques informations sur le contexte de l'exception, par un affichage ou une écriture dans un fichier journal, avant de relancer la propagation de l'exception. On peut réaliser ce redémarrage de la propagation en utilisant le mot-clé raise sans paramètre dans le bloc alternatif.
","title":"Rattrapage indiscriminé"},{"edit":"Mettre le résultat ici (code et figure).
( n = 1 si n = 0,
fact(n) = (
( n x fact(n-1) si n>0.
def fact(n):
if n == 0 :
return 1
else:
return n * fact(n - 1)
print(fact(5))
Écrire un module réalisant l'interface 1 suivant la stratégie du programme 1.
Mettre le résultat ici (code et figure).
def cree():
return []
def contient(s, x):
return x in s
def ajoute(s, x):
s.append(x)
Écrire un module réalisant l'interface 1 suivant la stratégie du programme 3.
Attention : pour que la fonction ajoute fonctionne, il faut
pouvoir modifier l’ensemble.
Mettre le résultat ici (code et figure).
def cree():
return { 'n': 0 }
def contient(s, x):
return s['n'] & (1 << x) != 0
def ajoute(s, x):
s['n'] = s['n'] | (1 << x)
Supposons que l’on veuille ajouter à l'interface des ensembles la fonction enumere déjà présente par exemple dans le programme 9.
Adapter le module du programme 6 pour qu’il réalise cette interface étendue.
Mettre le résultat ici (code et figure).
Comme dans le programme 9, on construit un tableau
que l’on agrandit à chaque élément trouvé. On teste alors chaque bit de chacun des six entiers du tableau, et on calcule le nombre correspondant lorsque nécessaire.
def enumere(s):
tab = []
for paquet in range(6):
for bit in range(64):
if s[paquet] & (1 << bit) != 0:
tab.append(paquet*64 + bit)
return tab
Supposons que l’on veuille ajouter à l'interface des ensembles les deux fonctions d’union et d’intersection suivantes.
union(s1, s2) renvoie un nouvel ensemble composé de
l’union des éléments de s1 et s2.
intersection(s1, s2) renvoie un nouvel ensemble composé de l'intersection des éléments de s1 et s2.
Précisons que ces fonctions ne doivent pas modifier les ensembles s1 et s2 qui leur sont donnés en paramètres.
Réaliser ces fonctions dans le module de l'exercice 11.
Mettre le résultat ici (code et figure).
def union(s1, s2):
t = [x for x in s1]
for x in s2:
if x not in si:
t.append(x)
return t
def intersection(s1, s2):
t= [0]
for x in s1:
if x in s2:
t.append(x)
return t
Certaines réalisations des ensembles d’entiers vues dans cette séquence représentent plus précisément des ensembles d’entiers compris entre 0 et un certain entier maximum nmax? Lesquelles ? Comment était décidé Nmax ? Que changer à l'interface de ces programmes pour permettre à l’utilisateur de choisir nmax ?
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Les modules décrits par chacun des programmes 6, 9 et 10 réalisent tous l’interface 1 et peuvent donc tous être utilisés par le programme 8.
Pour autant, l'un est-il préférable aux autres pour cette application particulière ?
Mettre le résultat ici (code et figure).
Les trois modules sont corrects et permettront d’obtenir le résultat. On a cependant les différences d'efficacité suivantes.
- Le programme 10 est préférable au programme 9 concernant le temps d’exécution. En effet, l’ensemble manipulé contiendra à terme plus de 360 éléments, soit en moyenne une quinzaine d’éléments par paquet :
l'augmentation du nombre de paquets est utile.
- Le programme 6 est comparable au programme 10 pour le temps d’exécution, mais préférable aux deux autres pour la mémoire utilisée. En effet, l’ensemble manipulé n’est pas quelconque : on sait qu’il contiendra à terme tous les éléments de 1 à 366. La représentation utilisée par ce programme sera donc de loin la plus compacte.
Considérons une structure de table de hachage telle que réalisée par le programme 10 mais avec seulement 8 paquets. On place dedans les entiers 0, 1, 4, 9, 13, 24 et 30.
Donner le contenu de chacun des paquets.
‹
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On place l’entier x dans la table d’indice x % 8. On
obtient le tableau de paquets suivant.
[[0, 24], [1, 9], [ ], [ ],, [4], [13], [30], [ ]]
L'interface des tableaux de Python fournit de nombreuses opérations à l’allure anodine mais cachant une complexité non négligeable. Rien de tel que d’essayer de réaliser soi-même ces fonctions pour s’en rendre compte.
Écrire un module réalisant l'interface suivante
tranche(t, i, j) renvoie un nouveau tableau contenant les
éléments de t de l’indice i inclus à l'indice j exclu (et le tableau vide si j < i)
concatenation(t1, t2) | renvoie un nouveau tableau contenant, dans l’ordre, les éléments de t1 puis les
éléments de t2
Notez qu'aucune de ces fonctions ne doit modifier les tableaux passés en paramètres.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
La tranche est créée dans un nouveau tableau de
longueur adaptée, où on place les éléments prélevés à partir de l’indice i.
La concaténation de même crée dès l’origine un tableau de taille adaptée.
def tranche(t, i, j):
n = j - i
if n <= 0:
return []
else:
tab = [None] * n
for k in range(n):
tab[k] = t[i+k]
return tab
def concatenation(ti, t2):
l1, l2 = len(t1), len(t2)
tab = [Nonel * (l1 + l2)]
for i in range(l1):
tab[i] = t1[i]
for i in range(l2):
tab[l1 + i] = t2[i]
return tab
Voici une interface minimale pour une structure de dictionnaire.
cree() crée et renvoie un dictionnaire vide
cle(d, k) renvoie True si et seulement si le dictionnaire d
contient la clé k
lit(d, k) renvoie la valeur associée à la clé k dans le dictionnaire d, et None si la clé k n’apparaît pas
ecrit(d, k, v) | ajoute au dictionnaire d l'association entre la clé k et la valeur v, en remplaçant une éventuelle valeur si la clé k existe.
On propose de réaliser cette interface de dictionnaire avec un tableau de couples clé-valeur, en faisant en sorte qu'aucune clé n’apparaisse deux fois.
Écrire un module réalisant cela.
Mettre le résultat ici (code et figure).
#Le dictionnaire vide n’est rien d’autre qu’un tableau
def cree():
return []
#Pour chercher une clé, on passe en revue tous les couples clé-valeur jusqu’à
#trouver la clé cherchée ou épuiser le tableau.
def cle(d, k):
for (kv, v) in d:
if hv == k :
return True
else :
return False
def lit(d, k):
for (kv, v) in d:
if kv == k :
return v
return None
#Pour ajouter une nouvelle association, il faut distinguer le cas où la clé est
#déjà présente du cas où elle ne l’est pas. Ici, dans le premier cas on remplace
#le couple correspondant par un nouveau couple, et dans le deuxième cas on
#ajoute le nouveau couple à la fin.
def ecrit(d, k, v):
for i in range(len(d)):
if d[i][0] == k:
d[i] = (k, v)
return
d.append((k, v))