NSI Première
NSI Première
Les tableaux sont des objets très utilisés en informatique, mais pas toujours évidents à manipuler, d'autant plus qu'en Python ( et dans d'autres langages ), il y a quelques subtilités dont il faut avoir conscience...
Il arrivera souvent où l'on aura besoin de recopier un tableau dans un autre.
Pour cela, la première idée qui vient à l'esprit est d'utiliser une opération d'affectation comme on pourrait le faire avec deux variables :
→ pas de problème : on a maintenant deux variables distinctes dont on peut modifier indépendamment le contenu.
Faisons à présent la même chose avec deux tableaux :
→ bizarre ! La modification du tableau b semble s'être "répercutée" dans le tableau a !!
Les deux tableaux ne semblent donc pas être indépendants, et en réalité, c'est exactement ce qu'il se passe...pour mieux comprendre, il faut se plonger un peu dans la manière dont Python gère la mémoire : cette page explique notamment très bien en quoi le modèle de la "boîte dans laquelle on met une donnée" pour les variables est en fait complètement faux en Python ( elle est vraie dans d'autres langages plus bas niveau, comme le C par exemple ).
En résumé, une variable en Python représente en réalité une "étiquette" VERS un emplacement mémoire stockant une donnée; une opération
de "copie" entre deux variables avec l'opérateur d'affectation = ne crée pas un nouvel emplacement mémoire, mais une nouvelle étiquette, un "alias" de la première, les deux pointant donc exactement
vers le même emplacement mémoire.
L'avantage étant qu'on encombre moins la mémoire centrale puisque les données stockées ne figurent qu'en un seul emplacement mémoire.
Dans le cas des types de variable mutables comme les tableaux, modifier une des variables reviendra donc à modifier également l'autre.
Par contre, ce problème n'apparaît pas avec les types non mutables comme les entiers ou les chaînes de caractères, pour lesquels Python crée bien un nouvel emplacement mémoire
dès qu'il "détecte" que l'on veut modifier une copie d'une variable.
Un type est non mutable ( = immuable ) si la valeur d'une variable de ce type ne peut changer que par l'affectation d'une nouvelle valeur à cette variable.
Dans le cas contraire, il sera mutable.
Il faut en réalité copier élément par élément un tableau dans une nouvelle variable pour en réaliser une "vraie" copie, version "indépendante" de la première :
On peut aussi bien sûr ( on doit ! ) faire une copie par compréhension :
b = [element for element in a]
b = [a[i] for i in range(len(a))]
b = a[:] # encore plus simple !
Python fait une copie dite "légère" des éléments du tableau, mais c'est toujours l'adresse mémoire des objets qui est copiée. Aussi, si l'un des éléments du tableau est aussi un tableau ( nous verrons cela au chapitre suivant ), on retombe sur le même problème.
Pour contourner totalement le problème, il faut utiliser la méthode tableau.deepcopy() du module copy qui effectue une copie dite "profonde":
from copy import deepcopy
.....
b = deepcopy(a) # copie "profonde"
Une fonction peut sans problème prendre comme paramètre un tableau ; à l'appel de la fonction, il faudra donc lui passer un tableau comme argument.
Mais là aussi, il y a quelques aspects auxquels il faut bien faire attention.
Voila une fonction qui prend comme paramètre un flottant représentant une température en degré Celsius, et renvoie sa valeur en degré Fahrenheit :
→ le nom de variable temperature est utilisé à deux endroits différents :
Mais à l'exécution, on se rend bien compte qu'il s'agit en réalité de deux variables différentes : la modification de temperature dans la fonction ne modifie pas temperature du programme principal.
En effet, une variable initialisée dans une fonction, ou qui en constitue un paramètre, à une portée locale à cette fonction : elle n'est créée et "n'existe" que pendant que la fonction s’exécute, et est "oubliée" à la sortie de celle-ci; deux variables non mutables ayant le même nom peuvent donc coexister en tant que variable locale à une fonction et globale dans le programme principal sans risque "d'interférence" entre les deux, ce sont en réalité deux objets bien distincts.
Ce problème de portée fait que l'on ne peut donc pas "accéder" à une variable locale depuis le programme principal, et encore moins la modifier.
Python signalera une telle tentative par une erreur "NameError: name 'xxx' is not defined".
Et qu'en est-il avec les tableaux ?
→ la variable temperature a été modifiée dans la fonction, et cette modification "persiste" après la fin de la fonction;
Ben, facile de résoudre le problème : il suffit de donner un autre nom au paramètre :
→ et non, toujours le même problème !!
Quelque soit le nom utilisé pour le désigner, il n'y a donc qu'un unique objet correspondant au tableau dans tout le script, et ce, toujours à cause du caractère mutable d'un tableau.
Le problème dans le cas du script ci-dessus : le tableau a été complètement modifié par la fonction, et on a donc perdu les données initiales. On parle d'effet de bord de la fonction, au sens
"d'effet secondaire" ou "effet indésirable".
Cela ne se serait bien entendu pas produit si l'on avait au préalable pris soin, au début de la fonction, de faire une copie du tableau passé en paramètre, et en ne modifiant que
cette copie :
→ on résout ainsi le problème en créant une nouvelle variable, locale à la fonction, et donc bien distincte de celle du programme principal.
Bien entendu, la variable temp2 étant redéfinie complètement dans la fonction, elle en devient locale, et le programme principal ne peut plus y accéder directement.
D'où cette règle primordiale :
Si dans une fonction on veut modifier les données d'un objet mutable ( comme un tableau ) mais en conserver les données d'origine, on prendra soin d'en faire au préalable une copie et de ne modifier que cette copie.
Attention également au fait que l'on peut donc modifier un tableau dans une fonction, même si on ne l'a pas passé comme argument à cette fonction !!
A titre de documentation, une page pour aller plus loin avec ces histoires de mutable/non mutable...
Dans cet exercice, on cherche à modifier les données stockées dans un tableau, mais sans modifier le tableau d'origine.
On dit qu'on écrête un signal lorsqu'on limite l'amplitude du signal entre deux valeurs a et b.
On peut également appliquer cela à des tableaux de valeurs. Voici par exemple un tableau tab que l'on a écrêté entre - 150 et 150 pour donner le tableau tab_ec :
tab = [34, 56, 89, 134, 152, 250, 87, -34, -187, -310]
tab_ecrete = [34, 56, 89, 134, 150, 150, 87, -34, -150, -150]
Les valeurs dans le tableau sont donc maintenant toutes comprises entre -150 et 150.
ecrete() ci-dessous qui prend en paramètres un tableau d'entiers tab ainsi que deux entiers a et b avec
a <= b, et qui renvoie un nouveau tableau correspondant aux valeurs de tab écrêtées entre a et b.Un algorithme, explicité par Donald Knuth, de mélange uniforme d'un tableau tab de taille N est le suivant :
Pour chacun des éléments du tableau :
permuter l'élément courant avec un des éléments - choisi au hasard - d'indice inférieur ou égal à celui de l'élément courant
En programmation informatique, une permutation consiste à intervertir les valeurs de deux variables. Il s'agit d'une opération courante, mais rarement intégrée aux langages
de programmation et jeu d'instructions des processeurs.
De nombreux algorithmes, en particulier des algorithmes de tri, utilisent des permutations.
Pour un tableau on peut facilement permuter deux valeurs en utilisant la double affectation ( qui utilise sans le montrer des tuples ).
Par exemple pour permuter les valeurs 999999999 et 333 d'indices 2 et 8 dans le tableau suivant :
tab = [1, 22, 999999999, 4444, 55555, 666666, 7777777, 88888888, 333]
C'est à dire effectuer :
_______________________________________________
| |
V |
[1, 22, 999999999, 4444, 55555, 666666, 7777777, 88888888, 333]
| Λ
|_______________________________________________|
Il suffit d'écrire l'instruction suivante :
tab[2], tab[8] = tab[8], tab[2]
Il est primordial de noter qu'une permutation ainsi effectuée est une mutation du tableau qui ne nécessite pas de créer un nouveau tableau.
En conséquence, sur un tableau passé en paramètre à une fonction, une mutation effectuée dans le corps de la fonction mutera le tableau à l'extérieur de la fonction.
melanger() ci-dessous qui prend en paramètre un tableau tab de longueur quelconque et le mute afin de mélanger uniformément toutes ses valeurs
selon l'algorithme proposé ci-dessus. return; afficher le tableau, exécuter la fonction et afficher à nouveau le tableau : celui-ci a-t-il été modifié ? Si oui, comment peut-on l'expliquer ?Il existe de très nombreux algorithmes de tris en informatique, vous verrez bientôt les deux qui sont au programme.
Ces algorithmes ont un coût en temps qui n'est pas très favorable, mais nous allons ici nous intéresser à une situation particulière : le cas d'un tableau constitué d'éléments de
3 valeurs différentes uniquement, par exemple : [2, 0, 2, 1, 2, 0, 1]
Le but est donc de trier ce tableau, en gardant le même nombre d'éléments, de façon à ce que tous les 0 soient au début, suivis de tous les 1 et enfin de tous les 2 :
[0, 0, 1, 1, 2, 2, 2]
Nous allons pour cela suivre un algorithme, appelé algorithme du drapeau hollandais ( cet algorithme a été inventé par E. Dijkstra, célèbre informaticien hollandais, pays dont le drapeau comporte 3 bandes colorées horizontales 🇳🇱 ).
Le principe est le suivant :
tableau_012 qui permet de créer aléatoirement un tableau ne contenant que des 0, des 1 ou des 2, de longueur N quelconque, passée en paramètre.on rappelle l'existence de la fonction randint qui permet de tirer au hasard un nombre entre deux bornes :
from random import randint # en début de script
alea = randint(1,100) # x contient un nombre aléatoire entre 1 et 100
Dans un lycée, il y a 10 classes de seconde. L’effectif par classe est limité à 25 pour que les professeurs puissent assurer un suivi personnalisé, et les élèves travailler dans des conditions satisfaisantes (on peut rêver ).
compte_surplus(L) qui prend en argument le tableau des effectifs, et qui renvoie, sous forme d'un autre tableau, le nombre d’élèves à enlever si l’effectif
dépasse 25.compte_surplus([24, 25, 26]) renvoie [0, 0, 1]repartition_possible(L) qui renvoie :
repartition_possible([24, 25, 26]) renvoie [1, 0, − 1] )repartition_possible([24, 25, 27]) renvoie [24, 25, 25, 2].repartition_possible(L) pour que l’éventuelle classe créée ne soit pas « trop déséquilibrée » par rapport aux autres.