Listes versus tableaux Numpy

La structure de tableau

D'un point de vue algorithmique, un tableau est une structure de données qui permet de stocker une suite ordonnée de valeurs $x_0,x_1,\dots,x_i\,\dots,x_{n-1}$. Chaque valeur est repérée par son indice $i$. Les valeurs sont stockées dans des cases contiguës de la mémoire RAM de sorte que l'accès à une case à partir de son indice $i$ se fait en temps constant, c'est-à-dire qui ne dépend pas de $i$ ou de la longueur $n$ du tableau.

Tableau

Les seules actions possibles sur un tableau sont :

  • Créer un tableau d'une taille donné $n$ en donnant aux éléments une valeur par défaut.
  • Lire une valeur à partir de son indice $i$.
  • Écrire une valeur à partir de son indice $i$.

La création d'un tableau nécessite un coût en temps qui est proportionnel à la taille $n$ : Il faut bien écrire les $n$ valeurs dans les cases. L'intérêt majeur des tableaux est que la lecture et l'écriture d'un élément est très rapide et se fait en temps constant.

Le langage Python possède deux types distincts de tableaux :

  • le type list,
  • le type array Numpy.

Ces deux types ont chacun leurs spécificités. Il convient de les connaître pour choisir le type adapté au problème que l'on a à résoudre.

Le type list

Le type list est un type python built-in. Cela signifie qu'il est disponible dès le lancement de l'interpréteur. Il n'est pas nécessaire d'importer un module. Le type list est une structure plus riche qu'un simple tableau tel que décrit ci-dessus. Une valeur de type list est un tableau redimensionnable. Il est possible de modifier sa taille en ajoutant ou supprimant des cases à la fin du tableau.

Voici les principales opérations que l'on peut effectuer sur une valeur de type list :

Opération Syntaxe Complexité
Création d'une liste vide [] $O(1)$
Création d'une liste de taille $n$ [0] * n $O(n)$
Création d'une liste de taille $n$ [f(i) for i in range(n)] $O(n)$
Lecture d'un élément x = L[i] $O(1)$
Écriture d'un élément L[i] = x $O(1)$
Ajout d'un élément L.append(x) $O(1)$
Suppression d'un élément x = L.pop() $O(1)$
Test d'appartenance x in L $O(n)$
Création d'une sous-liste L[i:j] $O(j-i)$
Copie d'une liste L2 = L1.copy() $O(n)$
Concaténation de deux listes L1 + L2 $O(n_1+n_2)$

Commentaires :

  • 'x in L' est une écriture élégante mais remarquez bien pour vos calculs de complexité que son coût est linéaire : il faut bien parcourir les éléments de la liste.

  • L'ajout d'un élément en fin de tableau peut poser un problème à l'interpréteur Python si la place mémoire dans la RAM est déjà occupée. Python doit alors recopier intégralement le tableau dans une zone mémoire plus grande. Python gère ce problème en réservant plus de place mémoire que nécessaire ce qui permet de considérer le append en $O(1)$.

  • Le pop a deux effets. Il supprime le dernier élément de la liste et retourne cette valeur comme résultat.

  • La syntaxe L[i:j] crée la sous-liste [L[i], ..., L[j-1]]. Si i est omis alors i vaut 0, si j est omis alors j vaut $n$. Ce n'est pas une opération en temps constant puisque Python doit copier ces éléments un à un pour fabriquer cette nouvelle liste. Pensez à cela lors de vos calculs de complexité.

  • Prendre garde que L2 = L1 ne crée pas de copie mais un nom L2 synonyme de L1.

Il existe ainsi trois façons de créer une liste L :

  • Créer une liste de la bonne longueur initialisée à une valeur par défaut, puis modifier les éléments L[i] dans une boucle.

  • Créer une liste vide et ajouter les éléments un à un en utilisant L.append à l'intérieur d'une boucle.

  • Créer la liste par compréhension [f(i) for i in range(n)].

Cette dernière façon est particulièrement claire et élégante. Elle est cependant seulement adaptée aux cas simples. Lorsque la longueur de la liste est connue a priori il est préférable d'utiliser la première façon, sinon il convient de créer une liste vide et d'utiliser le append.

Une liste peut contenir des valeurs de type quelconque. Les éléments d'une liste ne sont pas nécessairement tous du même type : une liste peut être hétérogène :

In [ ]:
L = [23, "bonjour", lambda x : x**2]
L[2](7)
Out[ ]:
49

Cette polyvalence a aussi un coût en terme de performance. Le type list n'est pas bien adapté pour effectuer des calculs numériques lourds sur des tableaux de grande taille. Le type array Numpy a précisément été créé pour les applications de calculs scientifiques.

Liste de listes

Les éléments d'une liste peuvent être eux-même du type list. Une matrice ou tableau 2D peut ainsi être représentée par une liste de listes.

La façon la plus élégante d'initialiser un tableau 2D à $p$ lignes et $n$ colonnes est d'écrire :

T = [[0] * n for i in range(p)]
  • T[i] désigne alors la $i$-ème ligne

  • T[i][j] désigne l'élément de la $i$-ème ligne et $j$-ème colonne.

Voici deux pièges à éviter avec les listes de listes.

Premier piège :

L'instruction «T = [[0] * n] * p» ne produit sans doute pas l'effet que vous attendez :

In [ ]:
T = [[0] * 2] * 3
T[0][0] = 42
print(T)
[[42, 0], [42, 0], [42, 0]]

Ce code est en effet équivalent à

L = [0] * 2
T = [L] * 3

Un seul exemplaire de la liste L est créé en mémoire, et non pas trois : T[0], T[1] et T[2] désignent la même liste en mémoire.

Second piège :

T[0:p][j] n'est pas la liste des éléments de la $j$-ème colonne. En effet T[0:p] n'est ni plus ni moins qu'une copie de T. Ainsi T[0:p][j] est la $j$-ème ligne de T.

Je vous déconseille donc d'utiliser les tranches d'indices i1:i2 avec les listes de listes. Cela est source d'erreurs et introduit des copies sans doute inutiles qui nuisent à l'efficacité de votre code.

Lorsque vous manipulez des tableaux de nombres multidimensionnels le meilleur choix est a priori d'utiliser un array Numpy. Toutefois, dans les sujets de concours, il convient de respecter le type spécifié dans l'énoncé : si on demande de coder une fonction qui retourne une valeur de type list vous devez écrire une fonction qui retourne une valeur de type list et non pas un array Numpy.

Le type array Numpy

In [ ]:
import numpy as np

Contrairement au type list, les éléments d'un array sont tous du même type et ce type est un entier ou un flottant. Par exemple :

  • np.int : Entier signé codé sur 64 bits.
  • np.uint : Entier non signé codé sur 64 bits.
  • nb.int8 : Entier signé codé sur 8 bits (entre -128 et 127).
  • nb.uint8 : Entier non signé codé sur 8 bits (entre 0 et 255).
  • np.float : Flottant codé sur 64 bits.

Les array peuvent être multidimensionnel.

Voici les principales actions que l'on peut effectuer sur un array Numpy. La syntaxe est illustrée pour un tableau 2D :

Opération Syntaxe Complexité
Création d'un array de forme $(n, p)$ np.zeros((n, p), np.int) $O(np)$
Création d'un array à partir d'une liste de listes np.array(L) $O(np)$
Lecture de la forme d'un array n, p = T.shape $O(1)$
Lecture d'un élément x = T[i, j] $O(1)$
Écriture d'un élément T[i, j] = x $O(1)$
Création d'une vue partielle V = T[i1:i2, j1:j2] $O(1)$
Écriture dans une région d'un array T[i1:i2, j1:j2] = R $O((i_2-i_1)(j_2-j_1))$
Création d'une copie T2 = T1.copy() $O(np)$
Multiplication scalaire c * T $O(np)$
Addition terme à terme T1 + T2 $O(np)$
Multiplication terme à terme T1 * T2 $O(np)$
Application d'une fonction f(T) $O(np)$

Commentaires :

  • Le type par défaut des éléments est np.float lorsque le second argument de np.zeros est omis.

  • L'indice d'un array Numpy 2D est un couple (T[i, j]). Cette notation est incorrecte dans le cas d'une valeur de type list.

  • Contrairement au type list, l'écriture V = T[i1:i2, j1:j2] ne génère pas de copie des éléments. La valeur retournée est une vue partielle du tableau T. Par conséquent une modification de V modifie T et réciproquement. Une autre conséquence est que cette instruction s'exécute en temps constant. Remarquez ainsi que la syntaxe tranche d'indices i1:i2 produit un effet totalement différent quand elle est appliquée à une valeur de type list ou de type array Numpy.

  • Dans l'écriture T[i1:i2, j1:j2] = R, la valeur R peut être un scalaire ou un tableau dont la forme est compatible avec la région de T. Cette instruction génère une copie des éléments et a donc un coût proportionnel au nombre de valeurs copiées.

  • T[i] est un raccourci pour T[i, :]. Il s'agit donc d'une vue partielle 1D de T qui correspond à la $i$-ème ligne.

  • Les array permettent d'effecter du calcul vectorialisé. Il n'est pas nécessaire par exemple d'écrire une boucle pour ajouter ou multiplier deux array termes à termes. L'écriture est concise et l'exécution est efficace. Notez cependant que la complexité demeure linéaire par rapport au nombre de termes.

Nous avons mentionner trois façons différentes de créer une valeur de type list. Dans le cas d'un array Numpy la seule façon est d'initialiser le tableau avec une valeur par défaut puis de modifier les éléments T[i, j] à l'aide de deux boucles imbriquées.

N'utilisez pas append sur un array Numpy. Cette action existe bien mais a une utilité très marginale car elle crée un nouveau array en mémoire ce qui est très coûteux.

Encore un piège pour terminer :

Vous risquez d'être confronté à ce piège lorsque vous codez par exemple l'algorithme du pivot de Gauss. On pourrait s'attendre à ce que le code ci-dessous échange les deux lignes de T.

In [ ]:
T = np.array([[1, 2, 3], [4, 5, 6]])
T[0], T[1] = T[1], T[0]
print(T)
[[4 5 6]
 [4 5 6]]

Mais les choses ne se passent pas comme prévues. L'erreur persiste même en écrivant :

In [ ]:
T = np.array([[1, 2, 3], [4, 5, 6]])
R = T[0]
T[0] = T[1]
T[1] = R
print(T)
[[4 5 6]
 [4 5 6]]

L'explication est la suivante :

  • L'instruction R = T[0] crée une vue R de la première ligne (pas de copie !).

  • L'instruction T[0] = T[1] copie la vue T[1] dans T[0]. La vue R, alias de T[0] est donc elle-aussi changée !

  • L'instruction T[1] = R copie la vue R dans T[1]. Mais R à ce stade, ne contient plus les éléments de la première ligne !

Pour échanger les deux lignes d'un tableau 2D il est nécessaire de copier l'une des lignes à l'extérieur du tableau 2D. La solution est donc :

In [ ]:
T = np.array([[1, 2, 3], [4, 5, 6]])
R = T[0].copy()
T[0] = T[1]
T[1] = R
print(T)
[[4 5 6]
 [1 2 3]]