\makeatletter
\@ifundefined{complet}
{\documentclass[10pt]{report}
\title{Python}
\newcommand{\categorie}{Python}
\input{latex_entete_perso}

\begin{document} %Cours

\setcounter{chapter}{14}
% xelatex --shell-escape cours_python
}
{}
\makeatother


\IfFileExists{index_du_tableau.png}{}{\write18{wget https://doc.infoforall.fr/activite/donnees/images/tableau/index_du_tableau.png}}

\IfFileExists{espace_noms.png}{}{\write18{wget https://doc.infoforall.fr/activite/donnees/images/tableau/espace_noms.png}}

\IfFileExists{EdN_tableau.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/tableau/EdN_tableau.png}}




\IfFileExists{type_simple.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/tableau/type_simple.png}}

\IfFileExists{type_construit.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/tableau/type_construit.png}}

\IfFileExists{armoire_de_boites.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/variables/armoire_de_boites.png}}

\IfFileExists{liaison_mot_contenus.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/variables/liaison_mot_contenus.png}}

\IfFileExists{mm_principe.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/dictionnaire/mm_principe.png}}

\IfFileExists{string_principe.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/string/string_principe.png}}

\IfFileExists{tableau_principe.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/tableau/tableau_principe.png}}

\IfFileExists{tuple_principe.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/tuple/tuple_principe.png}}




\chapter{Tableau statique et dynamique}





\section{Tableau statique}

\begin{multicols}{2}

\subsection{Tab. statique \small{voir Construit 5.3.1}}




\subsection{RAM}


\paragraph{Mémoire vive} : La mémoire vive est la zone dans laquelle on place les programmes en cours d'exécution et les données sur lesquelles ils travaillent.


\paragraph{RAM} est l'acronyme de \gras{Random Access Memory}, "mémoire à accès aléatoire" ? L'accès aléatoire veut dire qu'on peut atteindre directement une case mémoire et en lire le contenu pourvu qu'on connaisse son adresse.




\subsection{Principe du tableau}

\paragraph{Propriétés générales d'organisation :} En informatique, un tableau désigne un conteneur de données qui a les propriétés suivantes :

\begin{itemize}

\item Les octets sont consécutifs en mémoire à partir d'une première adresse A.
\item Le tableau occupe une largeur de L octets.
\item Chaque case encode le même type de données, et comporte C octets.

\end{itemize}


\paragraph{Exemple :} pour 1000 integers sur 4 octets.

\begin{itemize}

\item Imaginons que le premier octet du tableau soit stocké à l'adresse A = 500 dans la mémoire.
\item Chaque case contient C = 4 octets.
\item Le tableau occupe donc L = 1000 * 4 = 4000 octets consécutifs allant de l'adresse 500 à l'adresse 4499.
\item Chaque octet est bien entendu représentable comme un entier compris entre 0 et 255.
\item Les 4 octets 500 à 503 représentent collectivement le premier entier.

\end{itemize}


\subsubsection{Indice des cases}

\begin{itemize}

\item On identifie chaque case par un simple numéro qu'on appelle indice. Attention : l'indice de la première case n'est pas 1 mais 0
\item t[0] veut donc dire d'aller décoder le contenu DES CASES qui correspondent à l'indice 0 : les cases 500 - 501 - 502 - 503 ici.
\item t[1] veut donc dire d'aller décoder le contenu DES CASES qui correspondent à l'indice 1 : les cases 504 - 505 - 506 - 507 ici.

\end{itemize}


\paragraph{Espace des noms :}

L'espace des noms fait le lien entre le nom d'une variable (ici t) et les données du tableau mais... la variable ne référence pas les données, uniquement l'adresse à partir de laqulle elles sont stockées (ici 500).

\paragraph{Exemple visuel :} des données, stockées à partir de l'adresse 200, ont toutes une taille de 4 octets.


\begin{figure}[H]
\centering
\includegraphics[width=9.5cm]{index_du_tableau.png}
\caption{Principe du tableau}
\label{Principe-du-tableau}
\end{figure}



\subsection{Accès à coût CONSTANT}

\paragraph{Accès à Coût CONSTANT :} L'accès à \gras{n'importe quelle case du tableau} se fait à coût constant : quelque soit la taille du tableau, atteindre une case particulière prend le même temps. Voyons pourquoi.


\subsubsection{Explications} 

\begin{itemize}

\item \gras{1 - RAM} L'accès à une case-mémoire dont on connait l'adresse est à coût CONSTANT.

\item \gras{2 - Espace des noms} L'espace des noms fait le lien entre le nom d'un tableau et l'adresse A de son premier octet, à coût CONSTANT.

\item \gras{3 - Calcul de l'adresse d'une case du tableau} Connaissant l'adresse A du début du tableau (500 puis 200 sur les exemples), la largeur C des cases du tableau (4 sur les exemples), et l'indice i de la case voulue, on peut calculer à coût CONSTANT l'adresse du premier octet à lire :



\fo{Adresse du 1er octet à lire = A + i * C}

Avec A=500 et C=4 :

\fo{t[0]} : commence à 500 + 0*4 = 500

\fo{t[1]} : commence à 500 + 1*4 = 504

\fo{t[2]} : commence à 500 + 2*4 = 508

\fo{t[3]} : commence à 500 + 0*3 = 512

\columnbreak

\item \gras{4 - Conclusion}  Lorsqu'on tape t[2], Python obtient (via l'espace des noms) l'adresse 500 (action à coût CONSTANT), calcule l'adresse de la case 2 (500 + 2*4 = 508, action à coût CONSTANT), lit le contenu des cases 508, 509, 510 et 511 (4 actions à coût CONSTANT) et décode le contenu et renvoie la réponse (action à coût CONSTANT). L'ensemble forme donc une expression à coût CONSTANT.

\end{itemize}

\

\end{multicols}


\begin{figure}[H]
\centering
\includegraphics[width=15cm]{espace_noms.png}
\caption{Espace des noms et tableau}
\label{espace_noms}
\end{figure}


\begin{multicols}{2}

\subsection{Type \fo{list} de Python : un tableau non homogène}

Le type natif \fo{list} de Python permet de créer des tableaux en apparence non-homogène. 
Comment est-ce possible ?

En réalité, un type list référence un \gras{tableau d'adresses} (8 octets sur les systèmes 64 bits). Dans les cases du tableau, on stocke donc \gras{l'adresse du contenu} qu'on veut mettre à cette position et pas directement le contenu.

Grace à cette stratégie, on obtient des tableaux qui semblent ne pas avoir exactement le même type dans chaque case.


\begin{figure}[H]
\centering
\includegraphics[width=8cm]{EdN_tableau.png}
\caption{Espace des noms et list-Python}
\label{espace_noms_list}
\end{figure}




\end{multicols}






\section{Tableaux dynamiques}

\begin{multicols}{2}



\subsection{Présentation rapide}

\subsubsection{Tableau statique avec le type \fo{list}}

Dans un tableau statique :

\begin{itemize}

\item les cases contiennent le même type de données
\item le nombre de cases est constant : après création, on ne peut pas en supprimer ou en rajouter.

\end{itemize}

Les tableaux statiques s'implémentent en Python à l'aide du type \fo{list}. D'ailleurs, ontrairement à un tableau statique standard, Python accepte des contenus de types différents dans les différentes cases.


\subsubsection{Type \fo{list} : tableau dynamique}

Le type \fo{list} de Python est encore plus flexible que cela : il s'agit d'un \gras{tableau dynamique} (on peut ajouter et supprimer des cases). 

On pourrait donc créer une list Python contenant trois cases comme celle-ci : \gras{\fo{exemple = [1, 2, 5]}}

Et plus tard dans le programme, le tableau pourrait faire référence à 6 cases : \gras{\fo{[1, 2, 5, 10, 20, -10]}}

Ou même simplement 1 case : \gras{\fo{[5]}}





\subsection{
\fo{list.append()} \small{(tab.dyn.)}}


\subsubsection{Principe et syntaxe}

La méthode \fo{append()} rajoute une case contenant la valeur voulue à la fin du tableau. Toujours à la fin. La syntaxe est la suivante :

\small{
\begin{minted}{python}
nom_du_tableau.append(contenu_de_la_nouvelle_case)
\end{minted}
}

Insertion en fin : coût \gras{CONSTANT}, c'est donc une opération efficace qu'on peut utiliser sans dégrader les performances du programme.


\subsubsection{Exemple}

\small{
\begin{minted}{python}
>>> tab = []
>>> tab.append(10)  # Ajout de 10 en fin
>>> tab
[10]
 
>>> tab.append(20)  # Ajout de 20 en fin
>>> tab
[10, 20]
 
>>> tab.append(30)  # Ajout de 30 en fin
>>> tab
[10, 20, 30]
 
>>> tab.append(0)  # Ajout de 0 en fin
>>> tab
[10, 20, 30, 0]
\end{minted}
}

L'élément est toujours ajouté à la fin du tableau.


\subsubsection{Modifie en place, aucune réponse renvoyée}

La méthode ne renvoie aucune réponse : elle modifie en place le tableau sur lequel elle doit agir.

Une \gras{erreur très courante}, qu'il ne faut donc jamais faire : réaliser une affectation de ce type :

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30]
>>> tab = tab.append(100)
>>> tab
\end{minted}
}

Ici, on place dans \fo{tab} le résultat renvoyé par append(), à savoir... rien. On a donc involontairement "vidé" \fo{tab}. Notez que cela ne provoque pas d'erreur, c'est une erreur sémantique.




\subsection{\fo{list.pop()} \small{sans arg. (tab.dyn.)}}


\subsubsection{Principe et syntaxe}

La méthode \fo{pop()} supprime la dernière case d'un tableau ET renvoie la valeur supprimée : cela permet de la stocker si on le désire. La syntaxe est la suivante :

\small{
\begin{minted}{python}
nom_du_tableau.pop()
\end{minted}
}

Suppression en fin : coût \gras{CONSTANT}.


\subsubsection{Exemple}

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30]
>>> tab.pop()      # supprimer sans mémoriser
>>> tab
[10, 20]
 
>>> a = tab.pop()  # on stocke le 20 qu'on va supprimer
>>> tab
[10]
 
>>> tab.pop()   # supprimer sans mémoriser
>>> tab
[]
 
>>> a
20
 
>>> tab.pop()   # supprimer une case d'un tableau vide ?
IndexError: pop from empty list
\end{minted}
}




\subsubsection{Gérer le cas problématique}

Attention : vouloir supprimer une case d'un tableau vide lève une exception. Si vous n'êtes pas certain qu'il reste une case à supprimer, il faut donc tester avant d'agir :

\small{
\begin{minted}{python}
>>> tab = [10]
>>> tab.pop()  # supprimer la case de fin
>>> tab
[]
 
>>> if tab: tab.pop()  # si tab n'est pas vide
 
>>> if len(tab) > 0: tab.pop()  # si tab n'est pas vide
\end{minted}
}

Il n'y aura d'activation de la méthode que si le tableau contient un élément au moins.


\subsubsection{Modifie en place et renvoie la valeur supprimée}

La méthode renvoie la valeur supprimée. C'est le développeur qui décide ce qu'il veut en faire. Ne pas réaliser d'affectation permet donc de supprimer la valeur.





\subsection{\fo{list.pop(i)} \small{avec arg. (tab.dyn.)}}


\subsubsection{Principe et syntaxe}

La méthode \fo{pop(i)} supprime la case d'indice i du tableau ET renvoie la valeur supprimée : cela permet de la stocker si on le désire. La syntaxe est la suivante :

\small{
\begin{minted}{python}
nom_du_tableau.pop(i)
\end{minted}
}

Suppression sur une position quelconque : coût \gras{LINEAIRE}, c'est donc une opération à utiliser avec précaution car elle peut dégrader les performances du programme si le tableau possède beaucoup de cases.


\subsubsection{Exemple}

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30]
>>> tab.pop(1) # supp. la case 1 sans mémoriser
>>> tab
[10, 30]
 
>>> a = tab.pop(0) # on stocke le 10 qu'on supp.
>>> tab
[30]
 
>>> a
10
\end{minted}
}




\subsection{\fo{list.remove(x)} \small{(tab.dyn.)}}


\subsubsection{Principe et syntaxe}

La méthode \fo{remove(x)} supprime la première case contenant \fo{x} dans le tableau. Attention, elle ne renvoie rien. La syntaxe est la suivante :

\small{
\begin{minted}{python}
nom_du_tableau.remove(valeur_a_supprimer)
\end{minted}
}

Suppression d'un élément quelconque : coût \gras{LINEAIRE}.


\subsubsection{Exemple}

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30, 10, 40]
>>> tab.remove(20)  # supp. la case qui réf. 20
>>> tab
[10, 30, 10, 40]
 
>>> tab.remove(10)  # supp. la 1er case qui réf. 10
>>> tab
[30, 10, 40]
 
>>> tab.remove(10)  # supp. la case qui réf. 10
>>> tab
[30, 40]
 
>>> tab.remove(10)  # supp. une case qui réf. 10 ?
ValueError: list.remove(x): x not in list
\end{minted}
}

\subsubsection{Gérer le cas problématique}

Attention, tenter de supprimer une valeur qui n'existe pas lève une exception. Si vous n'êtes pas certain qu'un élément que vous voulez supprimer est présent, il faut donc tester avant d'agir :

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30, 10, 40]
>>> tab.remove(20)  # supp. la case qui réf. 20
>>> tab
[10, 30, 10, 40]
 
>>> if 50 in tab: tab.remove(50)
\end{minted}
}

Il n'y aura pas d'activation de la méthode puisque 50 n'est pas dans le tableau. Et donc pas d'erreur.


\subsubsection{Modifie en place, aucune réponse renvoyée}

La méthode ne renvoie aucune réponse : elle modifie en place le tableau sur lequel elle doit agir. Une \gras{erreur très courante}, qu'il ne faut donc jamais faire : réaliser une affectation de ce type :

\small{
\begin{minted}{python}
>>> tab = [10, 20, 30]
>>> tab = tab.remove(20)
>>> tab
\end{minted}
}

Ici, on place dans \fo{tab} le résultat renvoyé par \fo{remove()}, à savoir... rien. On a donc involontairement vidé \fo{tab} de tout contenu. C'est une erreur sémantique.

\end{multicols}


\section{RECAP des coûts}



\small{

ACCES à la case \fo{î} : CONSTANT.

\fo{append()} : CONSTANT.

\fo{pop()} : CONSTANT.

\fo{pop(i)} : LINEAIRE.

\fo{remove(x)} : LINEAIRE.
}



\input{licence}



\makeatletter
\@ifundefined{complet}
{\end{document}}

{}
\makeatother

